- 9 名前：デフォルトの名無しさん [2008/04/16(水) 07:43:14 ]
- nodeinfo_t infoary[NODENUM]の説明
ノードのラベルと親ノードを、ノード-1の位置に記憶する
ex. ノード３のラベルと親ノードは、infoary[2].label, infoary[2].parent
infoary[x-1].label == 0 の場合、xは通過していないことになる
analyze_depth：
①空のスタック（stack_t stack={0}）、初期化されたノード情報配列（nodeinfo_t infoary[NODENUM] = {{0}}）を宣言
②スタックにルートノード（start)をプッシュ ： pushstack(&stack, start);
③ルートノードを通過済みする ： flags[start-1] = 1;
④ルートノードのラベルを1に設定 ： infoary[start-1].label = 1;
ルートノードの親ノードを自分に設定 ： infoary[start-1].parent = start;
⑤ラベルを２に設定 ： label = 2;
⑥スタックにデータ（親ノード）がある→⑦、 スタックが空→⑮
⑦スタックからノードを取り出す（親ノード） ： parent = popstack(&stack);
⑧親ノードから到達可能なノード（子ノード）が、ある→⑨、ない→⑥ ： for(i=0; adj[parent-1][i] != 0; ++i){
⑨子ノードが未通過→⑩、通過済み→⑧ ： if( flags[ adj[parent-1][i]-1 ] == 0){
⑩子ノードを通過済みにする ： flags[ adj[parent-1][i]-1 ] = 1;
⑩スタックに親ノードをプッシュ ： pushstack(&stack, parent);
⑪スタックに子ノードをプッシュ ： pushstack(&stack, adj[parent-1][i]);
⑫子ノードのラベルを設定 ： infoary[ adj[parent-1][i]-1 ].label = label;
子ノードの親ノードを設定 ： infoary[ adj[parent-1][i]-1 ].parent = parent;
⑬ラベルを＋１する ： ++label;
⑭⑥に戻る ： break;
⑮ラベルが０以外のノードを表示する
printf(" v_label parent\n");
for(i=0; i < NODENUM; ++i){
if(infoary[i].label != 0){
printf("%2d : %7d %6d\n", i+1, infoary[i].label, infoary[i].parent);
}
}
上記間違いがあっても、当方は責任を負いかねます
これで分からないなら、まずwikiで深さ優先探索、スタックをじっくり勉強してください
|
 |
