ryamadaのコンピュータ日記

■[Java関連事項]グラフの縦型探索と横型探索 18:42

苦労して、グラフにおける縦型探索と横型探索をコードしたのに、ただでJavaコードをダウンロードできるとは・・・。技術評論社のJavaによるアルゴリズム事典(奥村晴彦　著)のサイトはこちら->『Javaによるアルゴリズム事典』サポートページ

縦型探索

/**
 *  深さ優先探索
 *
 *  @version $Revision: 1.5 $, $Date: 2003/04/28 23:23:15 $
 */

public class DepthFirstSearch {
    static int n;  // 点の数
    static int[][] adjacent;  // 隣接行列
    static boolean[] visited;  // 訪れたなら \texttt{true}

    public static void readGraph() { // グラフ入力
        n = 7;  // 点の数 (例)
        int data[] = { 1, 2, 2, 3, 1, 3, 2, 4, 5, 7 };  // 隣接リストによる
                                                        // データ (例)
        adjacent = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) adjacent[i][j] = 0;

        for (int k = 0; k + 1 < data.length; k += 2) {
            int i = data[k],  j = data[k + 1];
            adjacent[i][j] = adjacent[j][i] = 1;
        }
        System.out.println("隣接行列:");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                System.out.print(" " + adjacent[i][j]);
            System.out.println();
        }
    }

    public static void visit(int i) {  // 点 \texttt{i} を訪れる (再帰的)
        System.out.print(" " + i);  visited[i] = true;
        for (int j = 1; j <= n; j++)
            if (adjacent[i][j] != 0 && !visited[j]) visit(j);
    }

    public static void main(String[] args) {
        readGraph();  // 隣接行列を読む
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) visited[i] = false;  // まだ訪れていない

        System.out.println("連結成分:");
        int count = 0;  // 連結成分を数える
        for (int i = 1; i <= n; i++)
            if (!visited[i]) {
                System.out.print((++count) + ":");
                visit(i);  System.out.println();
            }
    }
}

横型探索

/**
 *  幅優先探索
 *
 *  @version $Revision: 1.7 $, $Date: 2003/04/28 23:23:14 $
 */

public class BreadthFirstSearch {
    static int n;  // 点の数
    static int[][] adjacent;  // 隣接行列

    public static void readGraph() { // グラフ入力
        n = 7;  // 点の数 (例)
        int data[] = { 1, 2, 2, 3, 1, 3, 2, 4, 5, 7 };  // 隣接リストによる
                                                        // データ (例)
        adjacent = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) adjacent[i][j] = 0;

        for (int k = 0; k + 1 < data.length; k += 2) {
            int i = data[k],  j = data[k + 1];
            adjacent[i][j] = adjacent[j][i] = 1;
        }
        System.out.println("隣接行列:");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                System.out.print(" " + adjacent[i][j]);
            System.out.println();
        }
    }

    public static void main(String[] args) {
        readGraph();
        int[] distance = new int[n + 1],  prev = new int[n + 1];
        for (int i = 1; i <= n; i++) distance[i] = -1;  // 未訪問
        int[] fifo = new int[n];  // 待ち行列(FIFO)
        int in = 0,  out = 0;  // FIFOバッファ上のポインタ

        final int START =  1;
        fifo[in++] = START;  distance[START] = 0;
        do {
            int i = fifo[out++];  // 待ち行列からの取り出し
            for (int j = 1; j <= n; j++)
                if (adjacent[i][j] != 0 && distance[j] < 0) {
                    fifo[in++] = j;  // 待ち行列への挿入
                    distance[j] = distance[i] + 1;  prev[j] = i;
                }
        } while (in != out);  // 待ち行列が空なら終了

        System.out.println("点  直前の点  最短距離");
        for (int i = 1; i <= n; i++)
            if (distance[i] > 0)
                System.out.println(" " + i + "         "
                    + prev[i] + "         " + distance[i]);
    }
}

ついでにDijkstraの最短路探索

/**
 *  最短路問題
 *  使用例: java Dijkstra <Dijkstra.dat
 *
 *  @version $Revision: 1.8 $, $Date: 2003/03/02 14:10:24 $
 */

import java.io.*;
import java.util.*;

public class Dijkstra {
    // データ入力
    private static int[][] readWeight() throws IOException {
        BufferedReader in = new
            BufferedReader(new InputStreamReader(System.in));
        String s = in.readLine();
        StringTokenizer t = new StringTokenizer(s);
        final int n = Integer.parseInt(t.nextToken());

        int[][] weight = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                weight[i][j] = Integer.MAX_VALUE;

        while ((s = in.readLine()) != null) {
            t = new StringTokenizer(s);
            int i = Integer.parseInt(t.nextToken());
            int j = Integer.parseInt(t.nextToken());
            weight[i][j] = weight[j][i] =
                Integer.parseInt(t.nextToken());
        }

        System.out.println("データ weight(i,j)");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (weight[i][j] < Integer.MAX_VALUE) {
                    s = "   " + weight[i][j];
                    s = s.substring(s.length() - 4);
                } else {
                    s = "  ∞";
                }
                System.out.print(s);
            }
            System.out.println();
        }
        return weight;
    }

    static final int START = 0; // 出発点

    public static void main(String[] args) throws IOException {
        int[][] weight = readWeight(); // 距離 weight[0..n-1][0..n-1] を読む
        final int n = weight.length;
        boolean[] visited = new boolean[n];
        int[] distance = new int[n];
        int[] prev = new int[n];
        for (int i = 0; i < n; i++) {
            visited[i] = false;  distance[i] = Integer.MAX_VALUE;
        }

        distance[START] = 0;
        int next = START;
        int min;
        do {
            final int i = next;
            visited[i] = true;
            min = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (visited[j]) continue;
                if (weight[i][j] < Integer.MAX_VALUE &&
                    distance[i] + weight[i][j] < distance[j]) {
                    distance[j] = distance[i] + weight[i][j];
                    prev[j] = i;
                }
                if (distance[j] < min) {
                    min = distance[j];  next = j;
                }
            }
        } while (min < Integer.MAX_VALUE);

        System.out.println("点  直前の点  最短距離");
        for (int i = 0; i < n; i++) {
            if (i == START || !visited[i]) continue;
            System.out.println(i + " " + prev[i] + " " + distance[i]);
        }
    }
}