-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBFS.java
More file actions
76 lines (67 loc) · 1.77 KB
/
Copy pathBFS.java
File metadata and controls
76 lines (67 loc) · 1.77 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package CodeJam2008;
import java.util.ArrayDeque;
import java.util.Deque;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;
public class BFS {
enum COLOR { WHITE,GRAY,BLACK};
static class GraphNode{
int d;
String name;
GraphNode pie=null;
COLOR color;
GraphNode(String name,COLOR c)
{
this.name=name;
this.color=c;
}
public String toString()
{
return name + "[distance from source :"+d+"]";
}
}
public MutableValueGraph<GraphNode,Integer> bfs(MutableValueGraph<GraphNode,Integer> graph,GraphNode s)
{
Deque<GraphNode>deque=new ArrayDeque<GraphNode>();
s.color=COLOR.GRAY;
s.d=0;
deque.add(s);
while(!deque.isEmpty())
{
GraphNode node=deque.poll();
for(GraphNode adj:graph.adjacentNodes(node))
{
if(adj.color==COLOR.WHITE)
{
adj.color=COLOR.GRAY;
adj.d=node.d+1;
adj.pie=node;
deque.offer(adj);
}
}
node.color=COLOR.BLACK;
}
return graph;
}
public static void main(String[] args)
{
MutableValueGraph<GraphNode,Integer> graph=ValueGraphBuilder.directed().allowsSelfLoops(true).build();
GraphNode A= new GraphNode("A",COLOR.WHITE);
GraphNode B= new GraphNode("B",COLOR.WHITE);
GraphNode C= new GraphNode("C",COLOR.WHITE);
GraphNode D= new GraphNode("D",COLOR.WHITE);
GraphNode E= new GraphNode("E",COLOR.WHITE);
graph.putEdgeValue(A,B,1);
graph.putEdgeValue(A,C,1);
graph.putEdgeValue(B,C,1);
graph.putEdgeValue(C,B,1);
graph.putEdgeValue(C,D,1);
graph.putEdgeValue(B,D,1);
graph.putEdgeValue(C,E,1);
graph.putEdgeValue(D,E,1);
graph.putEdgeValue(E,D,1);
BFS bfs= new BFS();
graph=bfs.bfs(graph,A);
System.out.println(graph.nodes());
}
}