Skip to content

Commit 392c1ec

Browse files
OneCodeMonkeyOneCodeMonkey
committed
graph: BreadthFirstPaths
1 parent b606918 commit 392c1ec

1 file changed

Lines changed: 198 additions & 0 deletions

File tree

‎Algorithm_full_features/graph/BreadthFirstPaths.java‎

Lines changed: 198 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,198 @@
1+
/**
2+
* Run breadth first search on an undirected graph.
3+
* Runs in O(E + V) time.
4+
*
5+
* The `BreadthFirstPaths` class represents a data type for finding shortest paths(number
6+
* of edges) from a source vertex `s` (or a set of source vertices) to every other vertex
7+
* in an undirected graph.
8+
* This implementation uses BFS search thoughts.
9+
*
10+
*/
11+
public class BreadthFirstPaths {
12+
private static final int INFINITY = Integer.MAX_VALUE;
13+
private boolean[] marked; // marked[v] = is there an s-v path
14+
private int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path
15+
private int[] distTo; // distTo[v] = number of edges shortest s-v path
16+
17+
// Computes the shortest path between the source vertex `s` and every other vertex in the
18+
// graph `G`
19+
public BreadthFirstPaths(Graph G, int s) {
20+
marked = new boolean[G.V()];
21+
distTo = new int[G.V()];
22+
edgeTo = new int[G.V()];
23+
validateVertex(s);
24+
bfs(G, s);
25+
26+
assert check(G, s);
27+
}
28+
29+
// Computes the shortest path between any one of the source vertices in `sources` and
30+
// every other vertex in graph `G`
31+
public BreadthFirstPaths(Graph G, Iterable<Integer>sources) {
32+
marked = new boolean[G.V()];
33+
distTo = new int[G.V()];
34+
edgeTo = new int[G.V()];
35+
for(int v = 0; v < G.V(); v++) {
36+
distTo[v] = INFINITY;
37+
}
38+
validateVertices(sources);
39+
bfs(G, sources);
40+
}
41+
42+
// breadth-first search from a single source
43+
private void bfs(Graph G, int s) {
44+
Queue<Integer> q = new Queue<Integer>();
45+
for(int v = 0; v < G.V(); v++)
46+
distTo[v] = INFINITY;
47+
distTo[s] = 0;
48+
marked[s] = true;
49+
q.enqueue(s);
50+
51+
while(!q.isEmpty()) {
52+
int v = q.dequeue();
53+
for(int w:G.adj(v)) {
54+
if(!marked[w]) {
55+
edgeTo[w] = v;
56+
distTo[w] = distTo[v] + 1;
57+
marked[w] = true;
58+
q.enqueue(w);
59+
}
60+
}
61+
}
62+
}
63+
64+
// breadth-first search from multiple sources
65+
private void bfs(Graph G, Iterable<Integer> sources) {
66+
Queue<Integer> q = new Queue<Integer>();
67+
for(int s:sources) {
68+
marked[s] = true;
69+
distTo[s] = 0;
70+
q.enqueue(s);
71+
}
72+
while(!q.isEmpty()) {
73+
int v = q.dequeue();
74+
for(int w:G.adj(v)) {
75+
if(!marked[w]) {
76+
edgeTo[w] = v;
77+
distTo[w] = distTo[v] + 1;
78+
marked[w] = true;
79+
q.enqueue(w);
80+
}
81+
}
82+
}
83+
}
84+
85+
// is there a path between the source vertex `s`(or sources) and vertex `v` ?
86+
public boolean hasPathTo(int v) {
87+
validateVertex(v);
88+
return marked[v];
89+
}
90+
91+
// Returns the number of edges in a shortest path between the source vertex `s`(or sources) and
92+
// vertex `v`
93+
public int distTo(int v) {
94+
validateVertex(v);
95+
return distTo[v];
96+
}
97+
98+
// Returns a shortest path between the source vertex `s`(or sources) and `v`, or `null`
99+
// if no such path.
100+
public Iterable<Integer> pathTo(int v) {
101+
validateVertex(v);
102+
if(!hasPathTo(v))
103+
return null;
104+
Stack<Integer> path = new Stack<Integer>();
105+
int x;
106+
for(x = v; distTo[x] != 0; x = edgeTo[x])
107+
path.push(x);
108+
path.push(x);
109+
return path;
110+
}
111+
112+
// check optimality conditions for single soruce
113+
private boolean check(Graph G, int s) {
114+
// check that the distance of s = 0
115+
if(distTo[s] != 0) {
116+
StdOut.println("distance of source " + s + " to itself = " + distTo[s]);
117+
return false;
118+
}
119+
120+
// check that for each edge v-w dist[w] <= dist[v] + 1
121+
// provided v is reachable from s
122+
for(int v = 0; v < G.V(); v++) {
123+
for(int w:G.adj(v)) {
124+
if(hasPathTo(v) != hasPathTo(w)) {
125+
StdOut.println("edge " + v + "-" + w);
126+
StdOut.println("hasPathTo(" + v + ") = " + hasPathTo(v));
127+
StdOut.println("hasPathTo(" + w + ") = " + hasPathTo(w));
128+
return false;
129+
}
130+
if(hasPathTo(v) && (distTo[w] > distTo[v] + 1)) {
131+
StdOut.println("edge " + v + "-" + w);
132+
StdOut.println("distTo[" + v + " ] = " + distTo[v]);
133+
StdOut.println("distTo[" + w + " ] = " + distTo[w]);
134+
return false;
135+
}
136+
}
137+
}
138+
139+
// check that v = edgeTo[w] satisfies distTo[w] = distTo[v] + 1
140+
// provided v is reachable from s
141+
for(int w = 0; w < G.V(); w++) {
142+
if(!hasPathTo(w) || w == s)
143+
continue;
144+
int v = edgeTo[w];
145+
if(distTo[w] != distTo[v] + 1) {
146+
StdOut.println("shortest path edge " + v + "-" + w);
147+
StdOut.println("distTo[" + v + "] = " + distTo[v]);
148+
StdOut.println("distTo[" + w + "] = " + distTo[w]);
149+
return false;
150+
}
151+
}
152+
153+
return true;
154+
}
155+
156+
// throw an IllegalArgumentException unless `0 <= v < V`
157+
private void validateVertex(int v) {
158+
int V = marked.length;
159+
if(v < 0 || v >= V)
160+
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
161+
}
162+
163+
// throw an IllegalArgumentException unless `0 <= v < V`
164+
private void validateVertex(Iterable<Integer> vertices) {
165+
if(vertices == null)
166+
throw new IllegalArgumentException("argument is null");
167+
int V = marked.length;
168+
for(int V:vertices) {
169+
if(v < 0 || v >= V) {
170+
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
171+
}
172+
}
173+
}
174+
175+
// test
176+
public static void main(String[] args) {
177+
In in = new In(args[0]);
178+
Graph G = new Graph(in);
179+
180+
int s = Integer.parseInt(args[1]);
181+
BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);
182+
for(int v = 0; v < G.V(); v++) {
183+
if(bfs.hasPathTo(v)) {
184+
StdOut.printf("%d to %d (%d): ", s, v, bfs.distTo(v));
185+
for(int x:bfs.pathTo(v)) {
186+
if(x == s)
187+
StdOut.print(x);
188+
else
189+
StdOut.print("-" + x);
190+
}
191+
StdOut.println();
192+
} else {
193+
StdOut.printf("%d to %d (-): not connected\n", s, v);
194+
}
195+
}
196+
}
197+
}
198+

0 commit comments

Comments
 (0)