Next Sec.: 最短路問題 Upper Sec.: グラフに関するアルゴリズム Prev. Sec.: グラフとその表現

パスの数え上げ

「グラフ内の与えられた２つの頂点s, tのあいだのパスをすべて数えよ．」

方法：

頂点sからスタートしてバックトラッキングによりtへのパスをすべて見いだす．
（2-3のフローチャートに基本的に従う．）

メインプログラム

• A[i,j]の読み込み（i = 1..n , j = 1..k ）
• s, tの読み込み
• P[i]の初期化
  P[t]= -1,P[i] = 0 (i != t)
• search(t)
  t --> sの全パスを探索 （出力をs --> t のパスとするため逆転）

#include <stdio.h>

#define N 5

int s, t, p[N];
int a[][N] = {
        { 2, 3, 0, 0, 0 },
        { 1, 3, 4, 0, 0 },
        { 1, 2, 4, 5, 0 },
        { 2, 3, 5, 0, 0 },
        { 3, 4, 0, 0, 0 }
};

void main(void)
{
        int i;

        for (i = 0; i < N; i++)
                p[i] = 0;
        scanf("%d%d", &s, &t);
        p[t-1] = -1;

        search(t);
}

パス探索プロシージャ

void search(int x)
{
        int j, y;

        for (j = 0; a[x-1][j] != 0 && j < N; j++) {
                y = a[x-1][j];
                if (p[y-1] == 0) {
                        p[y-1] = x;
                        if (y == s)
                                outputpath();
                        else
                                search(y);
                        p[y-1] = 0;
                }
        }
}

パス出力プロシージャ

void outputpath(void)
{
        int x;

        for (x = s; x > 0; x = p[x-1])
                printf("%5d", x);
        putchar('\n');
}