标签: undirected-graph

所以我面临这个问题，我希望有人可以帮助我。

给定一个无向图 G = (V, E)、2 个顶点 x,y 和一条边 e = (v,u)。

提出一种算法来查找是否存在从 x 到 y 且包含边 e 的简单路径。

所以这里的重点是简单路径而不是常规路径，对于常规路径来说，使用 BFS 搜索从 x 到 v 的路径和从 u 到 y 的路径是一个简单的问题。

我知道可以使用最大流方法解决问题，但我只是不知道如何构建一个可以在其上实现最大流算法的新图，以便它告诉是否达到上述标准，我希望得到帮助。

提前致谢。

输入
具有 n 个顶点和一个整数 k 的无向图 G，使得 k 整除 n。
所有顶点的集合将由 V 表示。

OUTPUT
一组 S 的顶点集，使得：

1. S 有 k 个元素
2. S 的每个元素都是 G 中的一个完全子图（每个元素中的所有顶点在 G 中彼此共享一条边）
3. S 的所有元素都是互斥的（元素之间没有共同的顶点）
4. S 的所有元素的并集等于 V
5. S 的所有元素都有基数 n / k

背景
我经营一个小型剧本阅读小组，我们有时喜欢阅读大型剧本。我想以这样的方式为一小群人演一场大型戏剧，这样一个人就不会扮演一组彼此共享场景的角色。我意识到这个问题可以用图论来表述，我很好奇一个好的解决方案是什么样的。

我是 C++ STL 的新手，最近开始学习图论。参考https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/ 后，我可以使用 DFS 计算无向、未加权图中的连通分量数为：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
int connected=0, temp1, temp2,n, p;

void DFS(int start, vector<int> v[],vector<int> &visited) {
    visited[start] = 1;
    for(int i= 0; i<v[start].size(); ++i) {        
        if(visited[v[start][i]] == 0)
            DFS(v[start][i], v, visited);        
    }    
}

int main() {
    cin>>n>>p; // number of vertices and edges
    vector<int> v[n+1], visited(n+1,0);
    for(int i=0; i<p; ++i) {
        cin>>temp1>>temp2;
        v[temp1].push_back(temp2);
        v[temp2].push_back(temp1);
    }     
    connected = 0;
    for(int i=1;i<=n;++i) {
        if(visited[i] == 0 ) { …

给定一个无向图,我怎样才能找到所有的桥？我只发现Tarjan的算法看起来相当复杂.

似乎应该有多个线性时间解决方案,但我找不到任何东西.

我使用无向图，G我的目标是找到比N 一对一关系中的节点最长的所有可能的链。

例如：

在下一张图中，一对一关系中长度超过 2 个节点的“链”是：

- d -> e -> f -> g
- c -> k -> l -> m

那么解决这个问题的最佳方法或算法是什么？

我正在寻找一种算法，当一个给定的两个节点 's' 和 't' 在一个无向图中，找到最小切割边，将图分成两个 A 和 B，'s' 将在 A 和 't ' 将在 B.

我看到大多数人建议使用 Ford-Fulkerson 算法来完成这项任务，在这里。我在想是否可以使用 Dinic 的算法。由于 Dinic 的算法可以通过动态树加速。因为我想以最快的方式找到最小切割边缘。

哪种算法在巨大的无向图中找到最小切割边更快？

在研究这些算法的细节时，我想听听一些建议。

提前致谢

我必须给出一个算法如下：

给定一个无向连通图 G，给出一个算法，找到两个节点 x,y，使得它们的距离至少是图直径的一半。证明任何主张。

我假设我必须从任意节点运行 BFS 并找到最远的节点来找到直径。然后找到两个探索的节点，其距离大于直径的一半。但我怀疑这是最佳的并要求解决方案。有没有其他方法可以在运行 BFS 时找到直径，同时找到这两个所需的节点？这样复杂度仍然是多项式。任何指导或提示将不胜感激！

给定一个二叉树的表示,它可以有最多n个节点:

typedef struct node
{
  int info,n;
  struct node *left,*right;
}tree_node;

从二叉树构造一个无向图,该二叉树最多可以有n个节点.

图表表示为结构:

typedef struct
{
  int n;
  tree_node *nodes[];
  int adjacency_m[][];
}graph;

我们可以使用Prim,Kruskal或DFS等算法从图中获取树.

问题:是否存在从二叉树创建图形的算法？例如,如果以顺序方式遍历二叉树,那么如何从中创建无向图？

我已经编写了一个用于无向图的类和一个符号表来将字符串转换为数字,反之亦然但是这两个字符串方法不起作用,因为我得到了堆栈溢出错误.我实现了一个LinkedStack,它与java库中的堆栈相同.我没有收到编译错误,如果能查看toString方法,我将不胜感激.其他方法工作正常.这是下面的代码.我认为问题是当我调用迭代器时

public class EdgeWeightedGraph {
private final int V;
private int E;
private LinkedStack<Edge>[] adj;

public EdgeWeightedGraph(int V){
    this.V = V;
    this.E = 0;
    adj = new LinkedStack[V];
    for (int v = 0; v < V; v++)
    {
        adj[v] = new LinkedStack<Edge>();
    }
}

public int V(){
    return V(); // This was the error. thank you for spotting it :)
}

public int E(){
    return E;
}

public int degree(int v){
    return adj[v].size();
}

public void addEdge(Edge e){
    int v …