CS 3343/3341 Analysis of Algorithms Spring 2012 |
Breadth-first Search
|
| Graph construction: 48 mainland US capitals. Data from file: capsdistnum.txt | |||||||||
|---|---|---|---|---|---|---|---|---|---|
// Graph.java: set up data structure for graph
// Uses adjacency list representation
import java.io.*;
import java.util.Scanner;
public class Graph {
private int count; // number of nodes
private Scanner sc; // input file name
private GraphNode[] graph;
private Queue queue;
private void err(int code) {
System.exit(code);
}
public Graph(String fileName, int ct) {
count = ct;
int num1 = 0, num2 = 0, num = 0;
queue = new Queue(100);
graph = new GraphNode[count];
for (int i = 0; i < count; i++)
graph[i] = null;
try {
sc = new Scanner(new
File("capsdistnum.txt"));
}
catch (Exception exception ) { err(1); }
while (sc.hasNextInt()) {
num1 = sc.nextInt();
if (sc.hasNextInt())
num2 = sc.nextInt();
else err(2);
if (sc.hasNextInt())
num = sc.nextInt();
else err(3);
// carry out insertions, both directions
insert(num1, num2, num);
insert(num2, num1, num);
}
}
private void insert(int num1, int num2,
int dist) {
// patch the new node in at the start
GraphNode node = graph[num1];
if (node == null) {
GraphNode gnode = new GraphNode();
graph[num1] = gnode;
EdgeNode enode = new EdgeNode(num2, null,
dist);
graph[num1].firstEdgeNode = enode;
}
else {
EdgeNode enode = new EdgeNode(num2,
graph[num1].firstEdgeNode, dist);
graph[num1].firstEdgeNode = enode;
}
}
public void breadthSearch(int s) { // 0 <= s <= 47
int u, v; // vertices used in loop
graph[s].color = 1; // gray
graph[s].d = 0;
graph[s].pi = -1;
queue.enqueue(s);
System.out.println("add vertex:" + s);
while (!queue.isEmpty()) {
u = queue.dequeue();
System.out.println("remove vertex:" + u);
EdgeNode vnode = graph[u].firstEdgeNode;
v = vnode.vertexNum;
while(true) {
System.out.println("edge: (" + u +
"," + v + ")");
if (graph[v].color == 0) { // white
graph[v].color = 1; // gray
graph[v].d = graph[u].d + 1;
graph[v].pi = u;
queue.enqueue(v);
}
vnode = vnode.nextEdgeNode;
if (vnode == null) break;
else v = vnode.vertexNum;
}
graph[u].color = 2; // black
}
System.out.println("*********************");
for (int i = 0; i < count; i++) {
if (i < 10) System.out.print(" ");
System.out.println(i + ": color:" +
graph[i].color + ", d:" +
graph[i].d + ", pi:" +
graph[i].pi + "\tEdge: (" +
graph[i].pi + "," +
i + ")");
}
}
public void printGraph() {
for (int i = 0; i < count; i++) {
System.out.print(i + ": ");
EdgeNode node = graph[i].firstEdgeNode;
while (node != null) {
System.out.print("[" + node.vertexNum +
"," + node.edgeDist + "]");
node = node.nextEdgeNode;
if (node != null)System.out.print(",");
else System.out.print("\n");
}
}
}
}
| // GraphNode.java: node for graph's vertex
// Holds vertex info, link to adj. list
public class GraphNode {
public EdgeNode firstEdgeNode;
// other vertex info here
public int color; // 0, 1, 2 = white, gray, black
public int d;
public int pi;
public GraphNode() {
firstEdgeNode = null;
// initialize other vertex info here
color = 0; // white
d = 100000000;
pi = -1;
}
}
| ||||||||
| Dump of information about each vertex, including vertex, distance to it (d), predecessor vertex (pi), and the directed edges in the breadth-first tree | |
|---|---|
0: color:2, d:2, pi:2 Edge: (2,0) 1: color:2, d:2, pi:6 Edge: (6,1) 2: color:2, d:1, pi:3 Edge: (3,2) 3: color:2, d:0, pi:-1 Edge: (-1,3) 4: color:2, d:3, pi:5 Edge: (5,4) 5: color:2, d:2, pi:6 Edge: (6,5) 6: color:2, d:1, pi:3 Edge: (3,6) 7: color:2, d:4, pi:8 Edge: (8,7) 8: color:2, d:3, pi:9 Edge: (9,8) 9: color:2, d:2, pi:6 Edge: (6,9) 10: color:2, d:2, pi:6 Edge: (6,10) 11: color:2, d:5, pi:12 Edge: (12,11) 12: color:2, d:4, pi:8 Edge: (8,12) 13: color:2, d:4, pi:14 Edge: (14,13) 14: color:2, d:3, pi:9 Edge: (9,14) 15: color:2, d:3, pi:10 Edge: (10,15) 16: color:2, d:3, pi:10 Edge: (10,16) 17: color:2, d:6, pi:18 Edge: (18,17) 18: color:2, d:5, pi:19 Edge: (19,18) 19: color:2, d:4, pi:14 Edge: (14,19) 20: color:2, d:4, pi:15 Edge: (15,20) 21: color:2, d:4, pi:16 Edge: (16,21) 22: color:2, d:6, pi:26 Edge: (26,22) 23: color:2, d:5, pi:20 Edge: (20,23) | 24: color:2, d:5, pi:21 Edge: (21,24) 25: color:2, d:6, pi:26 Edge: (26,25) 26: color:2, d:5, pi:19 Edge: (19,26) 27: color:2, d:5, pi:19 Edge: (19,27) 28: color:2, d:6, pi:23 Edge: (23,28) 29: color:2, d:6, pi:24 Edge: (24,29) 30: color:2, d:7, pi:31 Edge: (31,30) 31: color:2, d:6, pi:26 Edge: (26,31) 32: color:2, d:6, pi:27 Edge: (27,32) 33: color:2, d:6, pi:27 Edge: (27,33) 34: color:2, d:6, pi:27 Edge: (27,34) 35: color:2, d:7, pi:36 Edge: (36,35) 36: color:2, d:6, pi:26 Edge: (26,36) 37: color:2, d:7, pi:33 Edge: (33,37) 38: color:2, d:7, pi:34 Edge: (34,38) 39: color:2, d:8, pi:38 Edge: (38,39) 40: color:2, d:8, pi:38 Edge: (38,40) 41: color:2, d:8, pi:38 Edge: (38,41) 42: color:2, d:9, pi:41 Edge: (41,42) 43: color:2, d:9, pi:41 Edge: (41,43) 44: color:2, d:9, pi:41 Edge: (41,44) 45: color:2, d:10,pi:42 Edge: (42,45) 46: color:2, d:10,pi:44 Edge: (44,46) 47: color:2, d:11,pi:45 Edge: (45,47) |