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
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
140
141
142
143
144
145
146
147
148
149
150
|
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
public class SpecializedBFS
{
private static final int MAXINT = Integer.MAX_VALUE;
private boolean[] marked;
private int[] edgeTo;
private int[] distTo;
public SpecializedBFS(Digraph G, int s, ResizingArrayQueue<Integer> c)
{
init(G);
Queue<Integer> q = new Queue<Integer>();
marked[s] = true;
distTo[s] = 0;
q.enqueue(s);
if (c != null) c.enqueue(s);
bfs(G, q, c);
}
public SpecializedBFS(Digraph G, Iterable<Integer> ss,
ResizingArrayQueue<Integer> c)
{
init(G);
Queue<Integer> q = new Queue<Integer>();
for (int s : ss) {
marked[s] = true;
distTo[s] = 0;
q.enqueue(s);
if (c != null) c.enqueue(s);
}
bfs(G, q, c);
}
private void init(Digraph g)
{
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
distTo = new int[g.V()];
for (int v = 0; v < g.V(); v++)
distTo[v] = MAXINT;
}
public int distTo(int v)
{
return distTo[v];
}
public boolean hasPathTo(int v)
{
return marked[v];
}
private void bfs(Digraph G, Queue<Integer> q, ResizingArrayQueue<Integer> c)
{
while (!q.isEmpty()) {
int v = q.dequeue();
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
distTo[w] = distTo[v] + 1;
marked[w] = true;
q.enqueue(w);
if (c != null) c.enqueue(w);
}
}
}
}
// change this to an iterator if efficiency is needed
public Iterable<Integer> pathTo(int v)
{
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<Integer>();
int x;
for (x = v; distTo[x] != 0; x = edgeTo[x])
path.push(x);
path.push(x);
return path;
}
public int pathToCount(int v)
{
if (!hasPathTo(v)) return MAXINT;
int count = 0;
for (int x = v; distTo[x] != 0; x = edgeTo[x])
count++;
return count;
}
public static void main(String[] args)
{
In in = new In("./data/digraph3.txt");
Digraph G = new Digraph(in);
StdOut.println(G);
int s = 7;
ResizingArrayQueue<Integer> components = new ResizingArrayQueue<Integer>();
SpecializedBFS bfs = new SpecializedBFS(G, s, components);
for (int v = 0; v < G.V(); v++) {
if (bfs.hasPathTo(v)) {
StdOut.printf("%2d -> %2d: [%d] ", s, v, bfs.distTo(v));
for (int x : bfs.pathTo(v)) {
if (x == s) StdOut.print(x);
else StdOut.print("->" + x);
}
StdOut.println();
} else {
StdOut.printf("%2d -> %2d: [-]\n", s, v);
}
}
StdOut.printf("components : ");
for (int c : components) {
if (c == s) StdOut.print(c);
else StdOut.print("->" + c);
}
StdOut.print("\n");
StdOut.printf("pathToCount(%d) : %2d\n", 4, bfs.pathToCount(4));
StdOut.printf("pathToCount(%d) : %2d\n", 9, bfs.pathToCount(9));
int s2 = 11;
SpecializedBFS bfs2 = new SpecializedBFS(G, s2, null);
for (int v = 0; v < G.V(); v++) {
if (bfs2.hasPathTo(v)) {
StdOut.printf("%2d -> %2d: [%d] ", s2, v, bfs2.distTo(v));
for (int x : bfs2.pathTo(v)) {
if (x == s2) StdOut.print(x);
else StdOut.print("->" + x);
}
StdOut.println();
} else {
StdOut.printf("%2d -> %2d: [-]\n", s2, v);
}
}
StdOut.printf("intersection : ");
for (int c : components) {
if (bfs2.hasPathTo(c))
StdOut.print(c+" ");
}
StdOut.print("\n");
}
}
|
