グラフの縦型探索と横型探索
苦労して、グラフにおける縦型探索と横型探索をコードしたのに、ただで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]);
}
}
}
