2 
int dfs(int graph[MAXNODES][MAXNODES],int visited[],int start) {
int stack[MAXNODES];
    int top=-1,i;
    visited[start]=1;
    stack[++top]=start;
    while(top!=-1)
    {
  start=stack[top];
        for(i=0;i<MAXNODES;i++) {
   if(graph[start][i]&&visited[i]==0) {
                stack[++top]=i;
                printf("%d-",i);
                visited[i]=1;
                break;
            }
        }
  if(i==MAXNODES)
            top--;
    }
    return 0;
}

上面的代码在存储为邻接矩阵的图上实现了 dfs，我请求一个建议，我应该做些什么改变才能知道生成的图是否连接。

4

3 回答 3

2

请参阅我对先前关于强连接组件的问题的 回答。

您的 dfs 在编写时也非常低效，因为您从 i=0 开始重复扫描；你的堆栈应该记住你离开的地方并从那里继续。递归更自然，但如果您有有限的调用堆栈大小，那么显式堆栈是最好的（仅适用于巨大的树）。

这是一个递归的dfs。如果您对存储 dfs 树不感兴趣，则可以将 1 存储在前任[] 中，而不是您从中到达它的节点）：

const unsigned MAXNODES=100;

/* predecessor must be 0-initialized by the caller; nodes graph[n] that are
 reached from start will have predecessor[n]=p+1, where graph[pred] is the
 predecessor via which n was reached from graph[start].
 predecessor[start]=MAXNODES+1 (this is the root of the tree; there is NO
 predecessor, but instead of 0, I put a positive value to show that it's
 reached).

 graph[a][b] is true iff there is a directed arc from a->b

 */

void dfs(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
         ,unsigned start,unsigned pred=MAXNODES) 
{
    if (predecessor[start]) return;
    predecessor[start]=pred+1;
    for (unsigned i=0;i<MAXNODES;++i)
        if (graph[start][i])
            dfs(graph,predecessor,i,start);
}

这是一个基于上述模式的非递归 dfs，但对predand使用相同的堆栈变量i（通常，对于可以在递归中更改的每个局部变量和参数，您都有一个堆栈变量）：

void dfs_iter(bool graph[MAXNODES][MAXNODES],unsigned predecessor[]
              ,unsigned start)
{
    unsigned stack[MAXNODES]; // node indices
    unsigned n,pred;
    int top=0;
    stack[top]=start;
    for(;;) {
    recurse:
        // invariant: stack[top] is the next (maybe reached) node
        n=stack[top];
        if (!predecessor[n]) { // not started yet
            pred=top>0?stack[top-1]:MAXNODES;
            //show(n,pred);
            predecessor[n]=pred+1;
            // the first thing we can reach from n
            for (unsigned i=0;i<MAXNODES;++i)
                if (graph[n][i] && !predecessor[i]) {
                    stack[++top]=i; goto recurse; // push
                }
        }
        if (top>0) {
            pred=stack[top-1];
            // the next thing we can reach from pred after n
            for (unsigned i=n+1;i<MAXNODES;++i)
                if (graph[pred][i]) {
                    stack[top]=i; goto recurse; // replace top
                }
            --top;
        } else
            return;
    }
}

这可以在没有 goto 的情况下构建（它只是一个命名的 continue 到最外层循环），但在我看来没有任何更真正的清晰性。

无论如何，递归调用要简单得多。Tarjan 的强连接组件算法有递归伪代码，您可以直接转录。如果您需要帮助使其成为非递归（显式堆栈），请询问。

于 2009-12-03T01:28:55.840 回答
1

您需要存储从一个节点到下一个节点所生成的边。然后您可以验证图中的所有节点是否由边连接。

于 2009-12-03T00:55:08.647 回答
0

运行 Dijkstra 算法。如果最后您的队列为空并且某些顶点没有着色，则您的图形未连接。这是保证线性时间，dfs 方法具有二次的最坏情况分析。

于 2009-12-03T03:03:48.630 回答