Graph: BFS and DFS

GraphSearchAlgorithm.java

package org.metareal.graph;

import org.metareal.LinkedList;
import org.metareal.Queue;
import org.metareal.Stack;

public class GraphSearchAlgorithm {
	
	private final LinkedList<Integer>[] vertices;
	
	public GraphSearchAlgorithm() {
		// 隣接リストの準備
		vertices = new LinkedList[8];
		for (int i = 0; i < vertices.length; i++) {
			vertices[i] = new LinkedList<Integer>();
		}
		
		// 辺の追加
		vertices[0].add(1); // 1 --> 2
		vertices[0].add(2); // 1 --> 3
		
		vertices[1].add(0);
		vertices[1].add(2);
		vertices[1].add(3);
		vertices[1].add(4);

		vertices[2].add(0);
		vertices[2].add(1);
		vertices[2].add(4);
		vertices[2].add(6);
		vertices[2].add(7);

		vertices[3].add(1);
		vertices[3].add(4);

		vertices[4].add(1);
		vertices[4].add(2);
		vertices[4].add(3);
		vertices[4].add(5);

		vertices[5].add(4);

		vertices[6].add(2);
		vertices[6].add(7);
		
		vertices[7].add(2);
		vertices[7].add(6);
	}

	public void bfs(int start) {
		System.out.println("Breadth-first- search:");
		boolean discovered[] = new boolean[vertices.length];
		Queue<Integer> L = new Queue<Integer>();
		
		discovered[start] = true;
		L.push(start);
		System.out.print(start + 1);
		System.out.print(" ");
		while (!L.isEmpty()) {
			int u = L.pop();
			LinkedList<Integer> edges = vertices[u];
			int length = edges.size();
			for (int i = 0; i < length; i++) {
				int v = edges.get(i);
				if (!discovered[v]) {
					discovered[v] = true;
					L.push(v);
					System.out.print(v + 1);
					System.out.print(" ");
				}
			}
		}
		System.out.print("\n");
	}
	
	public void dfs(int start) {
		System.out.println("Depth-first search");
		boolean explored[] = new boolean[vertices.length];
		Stack<Integer> S = new Stack<Integer>();
		
		S.push(start);
		while (!S.isEmpty()) {
			int u = S.pop();
			if (!explored[u]) {
				explored[u] = true;
				System.out.print(u + 1);
				System.out.print(" ");
				LinkedList<Integer> edges = vertices[u];
				int length = edges.size();
				for (int i = length - 1; i >= 0; i--) {
					int v = edges.get(i);
					S.push(v);
				}
			}
		}
		System.out.print("\n");
	}
	
	public static void main(String[] args) {
		GraphSearchAlgorithm graph = new GraphSearchAlgorithm();
		graph.bfs(0);
		graph.dfs(0);
	}

}