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

強連結成分に関する以前の質問 に対する私の回答を参照してください。

i=0 で繰り返しスキャンを開始するため、書かれているように dfs も非常に非効率的です。スタックは中断した場所を記憶し、そこから続行する必要があります。再帰の方がより自然ですが、呼び出しスタックのサイズが制限されている場合は、明示的なスタックが最適です (巨大なツリーの場合のみ)。

これが再帰的な dfs です。dfs ツリーを保存することに興味がない場合は、到達したノードの代わりに predecessor[] に 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 なしで構造化できます (これは名前付きの一番外側のループへの継続です) が、私の意見ではこれ以上の明確さはありません。

とにかく、再帰呼び出しははるかに簡単です。Tarjan の強連結成分アルゴリズムの再帰的擬似コードがあり、かなり直接的に転記できます。非再帰的 (明示的なスタック) にするのに助けが必要な場合は、尋ねてください。

于 2009-12-03T01:28:55.840 に答える
1

あるノードから次のノードに移動することによって生成されたエッジを保存する必要があります。次に、グラフ内のすべてのノードがエッジで接続されていることを確認できます。

于 2009-12-03T00:55:08.647 に答える
0

ダイクストラのアルゴリズムを実行します。最後にキューが空で、いくつかの頂点が色付けされていない場合、グラフは接続されていません。これは保証された線形時間であり、dfs アプローチには 2 次の最悪のケースの分析があります。

于 2009-12-03T03:03:48.630 に答える