C/C++の宿題を片付けます 105代目

C/C++の宿題を片付け� ..

9:デフォルトの名無しさん
08/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で深さ優先探索、スタックをじっくり勉強してください

次ページ

続きを表示

1を表示