Newer
Older
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
/**
* Consider this class, BreadthFirstShortestPaths, which computes the shortest path between
* multiple node sources and any node in an undirected graph using a BFS path.
* The Graph class is already implemented and here it is:
* <p>
* public class Graph {
* // @return the number of vertices
* public int V() { }
* <p>
* // @return the number of edges
* public int E() { }
* <p>
* // Add edge v-w to this graph
* public void addEdge(int v, int w) { }
* <p>
* // @return the vertices adjacent to v
* public Iterable<Integer> adj(int v) { }
* <p>
* // @return a string representation
* public String toString() { }
* }
* <p>
* You are asked to implement all the TODOs of the BreadthFirstShortestPaths class.
*/
public class BreadthFirstShortestPaths {
private static final int INFINITY = Integer.MAX_VALUE;
private boolean[] marked; // marked[v] = is there an s-v path
private int[] distTo; // distTo[v] = number of edges shortest s-v path
/**
* Computes the shortest path between any
* one of the sources and very other vertex
*
* @param G the graph
* @param sources the source vertices
*/
public BreadthFirstShortestPaths(Graph G, Iterable<Integer> sources) {
marked = new boolean[G.V()];
distTo = new int[G.V()];
for (int v = 0; v < G.V(); v++) {
distTo[v] = INFINITY;
}
bfs(G, sources);
}
// Breadth-first search from multiple sources
private void bfs(Graph G, Iterable<Integer> sources) {
Queue<Integer> queue = new LinkedList<>();
while (!queue.isEmpty()) {
int c = queue.poll();
for (int v: G.adj(c)) {
if (!marked[v]) {
marked[v] = true;
distTo[v] = distTo[c] + 1;
queue.add(v);
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
}
}
}
}
/**
* Is there a path between (at least one of) the sources and vertex v?
*
* @param v the vertex
* @return true if there is a path, and false otherwise
*/
public boolean hasPathTo(int v) {
return marked[v];
}
/**
* Returns the number of edges in a shortest path
* between one of the sources and vertex v?
*
* @param v the vertex
* @return the number of edges in a shortest path
*/
public int distTo(int v) {
return distTo[v];
}
static class Graph {
private List<Integer>[] edges;
public Graph(int nbNodes)
{
this.edges = (ArrayList<Integer>[]) new ArrayList[nbNodes];
for (int i = 0;i < edges.length;i++)
{
edges[i] = new ArrayList<>();
}
}
/**
* @return the number of vertices
*/
public int V() {
return edges.length;
}
/**
* @return the number of edges
*/
public int E() {
int count = 0;
for (List<Integer> bag : edges) {
count += bag.size();
}
return count/2;
}
/**
* Add edge v-w to this graph
*/
public void addEdge(int v, int w) {
edges[v].add(w);
edges[w].add(v);
}
/**
* @return the vertices adjacent to v
*/
public Iterable<Integer> adj(int v) {
return edges[v];
}
}
}