代码之家  ›  专栏  ›  技术社区  ›  Chaitanya

图的连通性

  •  2
  • Chaitanya  · 技术社区  · 14 年前
    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,我请求一个建议,我应该做什么更改来知道生成的图是否连接。

    3 回复  |  直到 13 年前
        1
  •  2
  •   Community Egal    7 年前

    看到我 answer 关于强连接组件的早期问题。

    您的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模式,但是使用相同的堆栈变量 pred 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-to-outmost循环),但在我看来没有任何真正的清晰性。

    无论如何,递归调用要简单得多。有递归伪代码 Tarjan's strongly connected components algorithm 你可以相当直接地转录。如果需要帮助使其非递归(显式堆栈),请询问。

        2
  •  1
  •   John Weldon    14 年前

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

        3
  •  0
  •   aterrel    14 年前

    运行Dijkstra的算法。如果在末尾,您的队列是空的,并且一些顶点没有着色,则您的图形没有连接。这是保证线性时间的,DFS方法有一个最坏情况下的二次分析。