算法-图

发表于 更新于 分类于
本文字数： 83k 阅读时长 ≈ 1:15

无向图|有向图|最小生成树|最短路径

无向图

问题 解决方法
单点连通性 DepthFirstSearch
单点路径 DepthFirstPaths
单点最短路径 BreadthFirstPaths
连通性 CC
检测环 Cycle
双色问题（图的二分性） TwoColor

Graph数据类型

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
import java.util.NoSuchElementException;

public class Graph
{
    private static final String NEWLINE = System.getProperty("line.separator");

    private final int V;
    private int E;
    private Bag<Integer>[] adj;

    //Initializes an empty graph with V vertices and 0 edges.
    public Graph(int V)
    {
        if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<Integer>();
    }

    //Initializes a graph from the specified input stream.
    public Graph(In in)
    {
        if (in == null) throw new IllegalArgumentException("argument is null");
        try
        {
            this.V = in.readInt();
            if (V < 0) throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative");
            adj = (Bag<Integer>[]) new Bag[V];
            for (int v = 0; v < V; v++)
                adj[v] = new Bag<Integer>();
            int E = in.readInt();
            if (E < 0) throw new IllegalArgumentException("number of edges in a Graph must be nonnegative");
            for (int i = 0; i < E; i++)
            {
                int v = in.readInt();
                int w = in.readInt();
                validateVertex(v);
                validateVertex(w);
                addEdge(v, w);
            }
        }
        catch (NoSuchElementException e)
        {
            throw new IllegalArgumentException("invalid input format in Graph constructor", e);
        }
    }


    //Initializes a new graph that is a deep copy of G.
    public Graph(Graph G)
    {
        this.V = G.V();
        this.E = G.E();
        if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");

        // update adjacency lists
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<Integer>();

        for (int v = 0; v < G.V(); v++)
        {
            // reverse so that adjacency list is in same order as original
            Stack<Integer> reverse = new Stack<Integer>();
            for (int w : G.adj[v])
                reverse.push(w);
            for (int w : reverse)
                adj[v].add(w);
        }
    }

    //Returns the number of vertices in this graph.
    public int V()
    {
        return V;
    }

    //Returns the number of edges in this graph.
    public int E()
    {
        return E;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v)
    {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    //Adds the undirected edge v-w to this graph.
    public void addEdge(int v, int w)
    {
        validateVertex(v);
        validateVertex(w);
        E++;
        adj[v].add(w);
        adj[w].add(v);
    }

    //Returns the vertices adjacent to vertex {@code v}.
    public Iterable<Integer> adj(int v)
    {
        validateVertex(v);
        return adj[v];
    }

    //Returns the degree of vertex {@code v}.
    public int degree(int v)
    {
        validateVertex(v);
        return adj[v].size();
    }

    //Returns a string representation of this graph.
    public String toString()
    {
        StringBuilder s = new StringBuilder();
        s.append(V + " vertices, " + E + " edges " + NEWLINE);
        for (int v = 0; v < V; v++)
        {
            s.append(v + ": ");
            for (int w : adj[v])
            {
                s.append(w + " ");
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }


    /**
     * Unit tests the {@code Graph} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args)
    {
        In in = new In(args[0]);
        Graph G = new Graph(in);
        StdOut.println(G);
    }

}

深度优先搜索

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
public class DepthFirstSearch 
{
    private boolean[] marked;    // marked[v] = is there an s-v path?
    private int count;           // number of vertices connected to s

    /**
     * Computes the vertices in graph {@code G} that are
     * connected to the source vertex {@code s}.
     */
    public DepthFirstSearch(Graph G, int s) 
    {
        marked = new boolean[G.V()];
        validateVertex(s);
        dfs(G, s);
    }

    // depth first search from v
    private void dfs(Graph G, int v) 
    {
        count++;
        marked[v] = true;
        for (int w : G.adj(v)) 
        {
            if (!marked[w]) 
            {
                dfs(G, w);
            }
        }
    }
    
    //Is there a path between the source vertex {@code s} and vertex {@code v}?
    public boolean marked(int v) 
    {
        validateVertex(v);
        return marked[v];
    }
    
    //Returns the number of vertices connected to the source vertex {@code s}.
    public int count() 
    {
        return count;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
    }

    /**
     * Unit tests the {@code DepthFirstSearch} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        Graph G = new Graph(in);
        int s = Integer.parseInt(args[1]);
        DepthFirstSearch search = new DepthFirstSearch(G, s);
        for (int v = 0; v < G.V(); v++) 
        {
            if (search.marked(v))
                StdOut.print(v + " ");
        }

        StdOut.println();
        if (search.count() != G.V()) StdOut.println("NOT connected");
        else                         StdOut.println("connected");
    }
}

使用深度优先搜索处理图的其他示例

判断G是否为无环图（假设不存在自环或平行边）
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
public class Cycle
{
    private boolean[] marked;
    private boolean hasCycle;
    
    public Cycle(Graph G)
    {
        marked = new boolean[G.V()];
        for (int s = 0; s < G.V(); s++)
            if (!marked[s])
                dfs(G, s, s);
    }
    
    private void dfs(Graph G, int v, int u)
    {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w, v);
            else if (w != u) hasCycle = true;
    }
    
    public boolean isHasCycle()
    {
        return hasCycle;
    }
}
判断G是否为二分图（双色问题）
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
public class TwoColor
{
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColorable = true;
    
    public TwoColor(Graph G)
    {
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for (int s = 0; s < G.V(); s++)
            if (!marked[s])
                dfs(G, s);
    }
    
    private void dfs(Graph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj[v])
            if (!marked[w])
            {
                color[w] = !color[v];
                dfs(G, w);
            }
        	else if (color[w] == color[v]) isTwoColorable = false;
    }
    
    public boolean isBipartite()
    {
        return isTwoColorable;
    }
}

使用深度优先搜索查找图中的路径

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
public class DepthFirstPaths {
    private boolean[] marked;    // marked[v] = is there an s-v path?
    private int[] edgeTo;        // edgeTo[v] = last edge on s-v path
    private final int s;         // source vertex

    //Computes a path between {@code s} and every other vertex in graph {@code G}.
    public DepthFirstPaths(Graph G, int s)
    {
        this.s = s;
        edgeTo = new int[G.V()];
        marked = new boolean[G.V()];
        validateVertex(s);
        dfs(G, s);
    }

    // depth first search from v
    private void dfs(Graph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj(v))
        {
            if (!marked[w])
            {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    //Is there a path between the source vertex {@code s} and vertex {@code v}?
    public boolean hasPathTo(int v)
    {
        validateVertex(v);
        return marked[v];
    }

    //Returns a path between the source vertex {@code s} and vertex {@code v}, or
    public Iterable<Integer> pathTo(int v)
    {
        validateVertex(v);
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v)
    {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code DepthFirstPaths} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args)
    {
        In in = new In(args[0]);
        Graph G = new Graph(in);
        int s = Integer.parseInt(args[1]);
        DepthFirstPaths dfs = new DepthFirstPaths(G, s);

        for (int v = 0; v < G.V(); v++)
        {
            if (dfs.hasPathTo(v))
            {
                StdOut.printf("%d to %d:  ", s, v);
                for (int x : dfs.pathTo(v))
                {
                    if (x == s) StdOut.print(x);
                    else        StdOut.print("-" + x);
                }
                StdOut.println();
            }
            else
            {
                StdOut.printf("%d to %d:  not connected\n", s, v);
            }

        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
%more tinyCG.txt
6
8
0 5
2 4
2 3
1 2
0 1
3 4
3 5
0 2

%java DepthFirstPaths tinyCG.txt 0
0 to 0: 0
0 to 1: 0-2-1
0 to 2: 0-2
0 to 3: 0-2-3
0 to 4: 0-2-3-4
0 to 5: 0-2-3-5

使用广度优先搜索查找图中的路径

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
public class BreadthFirstPaths
{
    private static final int INFINITY = Integer.MAX_VALUE;
    private boolean[] marked;  // marked[v] = is there an s-v path
    private int[] edgeTo;      // edgeTo[v] = previous edge on shortest s-v path
    private int[] distTo;      // distTo[v] = number of edges shortest s-v path

    //Computes the shortest path between the source vertex {@code s}
    public BreadthFirstPaths(Graph G, int s)
    {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        validateVertex(s);
        bfs(G, s);

        assert check(G, s);
    }

    //Computes the shortest path between any one of the source vertices in {@code sources}
    public BreadthFirstPaths(Graph G, Iterable<Integer> sources)
    {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = INFINITY;
        validateVertices(sources);
        bfs(G, sources);
    }


    // breadth-first search from a single source
    private void bfs(Graph G, int s)
    {
        Queue<Integer> q = new Queue<Integer>();
        for (int v = 0; v < G.V(); v++)
            distTo[v] = INFINITY;
        distTo[s] = 0;
        marked[s] = true;
        q.enqueue(s);

        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);
                }
            }
        }
    }

    // breadth-first search from multiple sources
    private void bfs(Graph G, Iterable<Integer> sources)
    {
        Queue<Integer> q = new Queue<Integer>();
        for (int s : sources) {
            marked[s] = true;
            distTo[s] = 0;
            q.enqueue(s);
        }
        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);
                }
            }
        }
    }

    //Is there a path between the source vertex {@code s} (or sources) and vertex {@code v}?
    public boolean hasPathTo(int v)
    {
        validateVertex(v);
        return marked[v];
    }

    //Returns the number of edges in a shortest path between the source vertex {@code s}
    public int distTo(int v)
    {
        validateVertex(v);
        return distTo[v];
    }

    //Returns a shortest path between the source vertex {@code s} (or sources)
    public Iterable<Integer> pathTo(int v)
    {
        validateVertex(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;
    }


    // check optimality conditions for single source
    private boolean check(Graph G, int s)
    {

        // check that the distance of s = 0
        if (distTo[s] != 0)
        {
            StdOut.println("distance of source " + s + " to itself = " + distTo[s]);
            return false;
        }

        // check that for each edge v-w dist[w] <= dist[v] + 1
        // provided v is reachable from s
        for (int v = 0; v < G.V(); v++)
        {
            for (int w : G.adj(v))
            {
                if (hasPathTo(v) != hasPathTo(w))
                {
                    StdOut.println("edge " + v + "-" + w);
                    StdOut.println("hasPathTo(" + v + ") = " + hasPathTo(v));
                    StdOut.println("hasPathTo(" + w + ") = " + hasPathTo(w));
                    return false;
                }
                if (hasPathTo(v) && (distTo[w] > distTo[v] + 1))
                {
                    StdOut.println("edge " + v + "-" + w);
                    StdOut.println("distTo[" + v + "] = " + distTo[v]);
                    StdOut.println("distTo[" + w + "] = " + distTo[w]);
                    return false;
                }
            }
        }

        // check that v = edgeTo[w] satisfies distTo[w] = distTo[v] + 1
        // provided v is reachable from s
        for (int w = 0; w < G.V(); w++) {
            if (!hasPathTo(w) || w == s) continue;
            int v = edgeTo[w];
            if (distTo[w] != distTo[v] + 1) {
                StdOut.println("shortest path edge " + v + "-" + w);
                StdOut.println("distTo[" + v + "] = " + distTo[v]);
                StdOut.println("distTo[" + w + "] = " + distTo[w]);
                return false;
            }
        }

        return true;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v)
    {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertices(Iterable<Integer> vertices)
    {
        if (vertices == null)
        {
            throw new IllegalArgumentException("argument is null");
        }
        for (Integer v : vertices)
        {
            if (v == null)
            {
                throw new IllegalArgumentException("vertex is null");
            }
            validateVertex(v);
        }
    }

    /**
     * Unit tests the {@code BreadthFirstPaths} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args)
    {
        In in = new In(args[0]);
        Graph G = new Graph(in);
        // StdOut.println(G);

        int s = Integer.parseInt(args[1]);
        BreadthFirstPaths bfs = new BreadthFirstPaths(G, s);

        for (int v = 0; v < G.V(); v++)
        {
            if (bfs.hasPathTo(v)) {
                StdOut.printf("%d to %d (%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("%d to %d (-):  not connected\n", s, v);
            }

        }
    }
}

测试

1
2
3
4
5
6
7
%java BreadthFirstPaths tinyCG.txt 0
0 to 0: 0
0 to 1: 0-1
0 to 2: 0-2
0 to 3: 0-2-3
0 to 4: 0-2-4
0 to 5: 0-5

连通分量

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
public class CC 
{
    private boolean[] marked;   // marked[v] = has vertex v been marked?
    private int[] id;           // id[v] = id of connected component containing v
    private int[] size;         // size[id] = number of vertices in given component
    private int count;          // number of connected components
    
    //Computes the connected components of the undirected graph {@code G}.
    public CC(Graph G) 
    {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        size = new int[G.V()];
        for (int v = 0; v < G.V(); v++) 
        {
            if (!marked[v]) 
            {
                dfs(G, v);
                count++;
            }
        }
    }
    
    //Computes the connected components of the edge-weighted graph {@code G}.
    public CC(EdgeWeightedGraph G) 
    {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        size = new int[G.V()];
        for (int v = 0; v < G.V(); v++) 
        {
            if (!marked[v]) 
            {
                dfs(G, v);
                count++;
            }
        }
    }

    // depth-first search for a Graph
    private void dfs(Graph G, int v) 
    {
        marked[v] = true;
        id[v] = count;
        size[count]++;
        for (int w : G.adj(v)) 
        {
            if (!marked[w]) 
            {
                dfs(G, w);
            }
        }
    }

    // depth-first search for an EdgeWeightedGraph
    private void dfs(EdgeWeightedGraph G, int v) 
    {
        marked[v] = true;
        id[v] = count;
        size[count]++;
        for (Edge e : G.adj(v)) 
        {
            int w = e.other(v);
            if (!marked[w]) 
            {
                dfs(G, w);
            }
        }
    }


    //Returns the component id of the connected component containing vertex {@code v}.
    public int id(int v) 
    {
        validateVertex(v);
        return id[v];
    }
    
    //Returns the number of vertices in the connected component containing vertex {@code v}.
    public int size(int v) 
    {
        validateVertex(v);
        return size[id[v]];
    }
    
    //Returns the number of connected components in the graph {@code G}.
    public int count() 
    {
        return count;
    }
    
    //Returns true if vertices {@code v} and {@code w} are in the same
    public boolean connected(int v, int w) 
    {
        validateVertex(v);
        validateVertex(w);
        return id(v) == id(w);
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code CC} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        Graph G = new Graph(in);
        CC cc = new CC(G);

        // number of connected components
        int m = cc.count();
        StdOut.println(m + " components");

        // compute list of vertices in each connected component
        Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
        for (int i = 0; i < m; i++) {
            components[i] = new Queue<Integer>();
        }
        for (int v = 0; v < G.V(); v++) {
            components[cc.id(v)].enqueue(v);
        }

        // print results
        for (int i = 0; i < m; i++) {
            for (int v : components[i]) {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ java Graph test.txt
13 vertices, 13 edges
0: 6 2 1 5
1: 0
2: 0
3: 5 4
4: 5 6 3
5: 3 4 0
6: 0 4
7: 8
8: 7
9: 11 10 12
10: 9
11: 9 12
12: 11 9

$ java CC test.txt
3 components
0 1 2 3 4 5 6
7 8
9 10 11 12

符号图的数据类型

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
public class SymbolGraph
{
    private ST<String, Integer> st;  // string -> index
    private String[] keys;           // index  -> string
    private Graph graph;             // the underlying graph
    
    //Initializes a graph from a file using the specified delimiter.
    public SymbolGraph(String filename, String delimiter)
    {
        st = new ST<String, Integer>();

        // First pass builds the index by reading strings to associate
        // distinct strings with an index
        In in = new In(filename);
        while (!in.isEmpty()) 
        {
            String[] a = in.readLine().split(delimiter);
            for (int i = 0; i < a.length; i++) 
            {
                if (!st.contains(a[i]))
                    st.put(a[i], st.size());
            }
        }

        // inverted index to get string keys in an array
        keys = new String[st.size()];
        for (String name : st.keys())
            keys[st.get(name)] = name;

        // second pass builds the graph by connecting first vertex on each
        // line to all others
        graph = new Graph(st.size());
        in = new In(filename);
        while (in.hasNextLine())
        {
            String[] a = in.readLine().split(delimiter);
            int v = st.get(a[0]);
            for (int i = 1; i < a.length; i++)
            {
                int w = st.get(a[i]);
                graph.addEdge(v, w);
            }
        }
    }
    
    //Does the graph contain the vertex named {@code s}?
    public boolean contains(String s)
    {
        return st.contains(s);
    }

    //Returns the integer associated with the vertex named {@code s}.
    public int indexOf(String s)
    {
        return st.get(s);
    }

    //Returns the name of the vertex associated with the integer {@code v}.
    public String nameOf(int v)
    {
        validateVertex(v);
        return keys[v];
    }

    //Returns the graph assoicated with the symbol graph. It is the client's responsibility
    public Graph graph()
    {
        return graph;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v)
    {
        int V = graph.V();
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
    }


    /**
     * Unit tests the {@code SymbolGraph} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args)
    {
        String filename = args[0];
        String delimiter = args[1];
        SymbolGraph sg = new SymbolGraph(filename, delimiter);
        Graph graph = sg.graph();
        while (StdIn.hasNextLine()) 
        {
            String source = StdIn.readLine();
            if (sg.contains(source))
            {
                int s = sg.indexOf(source);
                for (int v : graph.adj(s)) {
                    StdOut.println("   " + sg.nameOf(v));
                }
            } else {
                StdOut.println("input not contain '" + source + "'");
            }
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
% java SymbolGraph movies.txt "/"
Tin Men (1987)
   Hershey, Barbara
   Geppi, Cindy
   Jones, Kathy (II)
   Herr, Marcia
   ...
   Blumenfeld, Alan
   DeBoy, David
Bacon, Kevin
   Woodsman, The (2004)
   Wild Things (1998)
   Where the Truth Lies (2005)
   Tremors (1990)
   ...
   Apollo 13 (1995)
   Animal House (1978)

有向图

问题 解决方法
单点和多点的可达性 DirectedDFS
单点有向路径 DepthFirstDirectedPaths
单点最短有向路径 BreadthFirstDirectedPaths
有向环检测 DirectedCycle
深度优先的顶点排序 DepthFirstOrder
优先级限制下的调度问题 Topological
拓扑排序 Topological
强连通性 KosarajuSharirCC
顶点对的可达性 TransitiveClosure

Digraph数据类型

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
151
152
153
154
155
156
157
158
import java.util.NoSuchElementException;

public class Digraph 
{
    private static final String NEWLINE = System.getProperty("line.separator");

    private final int V;           // number of vertices in this digraph
    private int E;                 // number of edges in this digraph
    private Bag<Integer>[] adj;    // adj[v] = adjacency list for vertex v
    private int[] indegree;        // indegree[v] = indegree of vertex v

    //Initializes an empty digraph with V vertices.
    public Digraph(int V) 
    {
        if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
        this.V = V;
        this.E = 0;
        indegree = new int[V];
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++) 
            adj[v] = new Bag<Integer>();
    }

    //Initializes a digraph from the specified input stream.
    public Digraph(In in) 
    {
        if (in == null) throw new IllegalArgumentException("argument is null");
        try 
        {
            this.V = in.readInt();
            if (V < 0) throw new IllegalArgumentException("number of vertices in a Digraph must be nonnegative");
            indegree = new int[V];
            adj = (Bag<Integer>[]) new Bag[V];
            for (int v = 0; v < V; v++) 
                adj[v] = new Bag<Integer>();
            int E = in.readInt();
            if (E < 0) throw new IllegalArgumentException("number of edges in a Digraph must be nonnegative");
            for (int i = 0; i < E; i++) 
            {
                int v = in.readInt();
                int w = in.readInt();
                addEdge(v, w);
            }
        }
        catch (NoSuchElementException e) 
        {
            throw new IllegalArgumentException("invalid input format in Digraph constructor", e);
        }
    }

    //Initializes a new digraph that is a deep copy of the specified digraph.
    public Digraph(Digraph G) 
    {
        if (G == null) throw new IllegalArgumentException("argument is null");

        this.V = G.V();
        this.E = G.E();
        if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");

        // update indegrees
        indegree = new int[V];
        for (int v = 0; v < V; v++)
            this.indegree[v] = G.indegree(v);

        // update adjacency lists
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++) 
            adj[v] = new Bag<Integer>();

        for (int v = 0; v < G.V(); v++) 
        {
            // reverse so that adjacency list is in same order as original
            Stack<Integer> reverse = new Stack<Integer>();
            for (int w : G.adj[v])
                reverse.push(w);
            for (int w : reverse)
                adj[v].add(w);
        }
    }

    //Returns the number of vertices in this digraph.
    public int V() 
    {
        return V;
    }

    //Returns the number of edges in this digraph.
    public int E() 
    {
        return E;
    }


    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    //Adds the directed edge v→w to this digraph.
    public void addEdge(int v, int w) 
    {
        validateVertex(v);
        validateVertex(w);
        adj[v].add(w);
        indegree[w]++;
        E++;
    }

    //Returns the vertices adjacent from vertex {@code v} in this digraph.
    public Iterable<Integer> adj(int v) 
    {
        validateVertex(v);
        return adj[v];
    }

    //Returns the number of directed edges incident from vertex {@code v}.
    public int outdegree(int v) 
    {
        validateVertex(v);
        return adj[v].size();
    }

    //Returns the number of directed edges incident to vertex {@code v}.
    public int indegree(int v) 
    {
        validateVertex(v);
        return indegree[v];
    }

    //Returns the reverse of the digraph.
    public Digraph reverse() 
    {
        Digraph reverse = new Digraph(V);
        for (int v = 0; v < V; v++) 
        {
            for (int w : adj(v))
                reverse.addEdge(w, v);
        }
        return reverse;
    }

    //Returns a string representation of the graph.
    public String toString() 
    {
        StringBuilder s = new StringBuilder();
        s.append(V + " vertices, " + E + " edges " + NEWLINE);
        for (int v = 0; v < V; v++) 
        {
            s.append(String.format("%d: ", v));
            for (int w : adj[v])
                s.append(String.format("%d ", w));
            s.append(NEWLINE);
        }
        return s.toString();
    }
}

寻找有向环

无权有向图中寻找有向环
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
public class DirectedCycle 
{
    private boolean[] marked;        // marked[v] = has vertex v been marked?
    private int[] edgeTo;            // edgeTo[v] = previous vertex on path to v
    private boolean[] onStack;       // onStack[v] = is vertex on the stack?
    private Stack<Integer> cycle;    // directed cycle (or null if no such cycle)

    //Determines whether the digraph {@code G} has a directed cycle and, if so,
    public DirectedCycle(Digraph G) 
    {
        marked  = new boolean[G.V()];
        onStack = new boolean[G.V()];
        edgeTo  = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v] && cycle == null) dfs(G, v);
    }

    // run DFS and find a directed cycle (if one exists)
    private void dfs(Digraph G, int v) 
    {
        onStack[v] = true;
        marked[v] = true;
        for (int w : G.adj(v)) 
        {

            // short circuit if directed cycle found
            if (cycle != null) return;

                // found new vertex, so recur
            else if (!marked[w]) 
            {
                edgeTo[w] = v;
                dfs(G, w);
            }

            // trace back directed cycle
            else if (onStack[w]) 
            {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x]) 
                {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
                assert check();
            }
        }
        onStack[v] = false;
    }

    //Does the digraph have a directed cycle?
    public boolean hasCycle() 
    {
        return cycle != null;
    }

    //Returns a directed cycle if the digraph has a directed cycle, and {@code null} otherwise.
    public Iterable<Integer> cycle()
    {
        return cycle;
    }


    // certify that digraph has a directed cycle if it reports one
    private boolean check() 
    {

        if (hasCycle()) 
        {
            // verify cycle
            int first = -1, last = -1;
            for (int v : cycle()) 
            {
                if (first == -1) first = v;
                last = v;
            }
            if (first != last) 
            {
                System.err.printf("cycle begins with %d and ends with %d\n", first, last);
                return false;
            }
        }


        return true;
    }

    /**
     * Unit tests the {@code DirectedCycle} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        Digraph G = new Digraph(in);

        DirectedCycle finder = new DirectedCycle(G);
        if (finder.hasCycle()) {
            StdOut.print("Directed cycle: ");
            for (int v : finder.cycle()) 
            {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }

        else 
        {
            StdOut.println("No directed cycle");
        }
        StdOut.println();
    }
}
带权有向图中寻找有向环
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
public class EdgeWeightedDirectedCycle 
{
    private boolean[] marked;             // marked[v] = has vertex v been marked?
    private DirectedEdge[] edgeTo;        // edgeTo[v] = previous edge on path to v
    private boolean[] onStack;            // onStack[v] = is vertex on the stack?
    private Stack<DirectedEdge> cycle;    // directed cycle (or null if no such cycle)

    /**
     * Determines whether the edge-weighted digraph {@code G} has a directed cycle and,
     * if so, finds such a cycle.
     */
    public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) 
    {
        marked  = new boolean[G.V()];
        onStack = new boolean[G.V()];
        edgeTo  = new DirectedEdge[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);

        // check that digraph has a cycle
        assert check();
    }

    // check that algorithm computes either the topological order or finds a directed cycle
    private void dfs(EdgeWeightedDigraph G, int v) 
    {
        onStack[v] = true;
        marked[v] = true;
        for (DirectedEdge e : G.adj(v)) 
        {
            int w = e.to();

            // short circuit if directed cycle found
            if (cycle != null) return;

            // found new vertex, so recur
            else if (!marked[w]) 
            {
                edgeTo[w] = e;
                dfs(G, w);
            }

            // trace back directed cycle
            else if (onStack[w])
            {
                cycle = new Stack<DirectedEdge>();

                DirectedEdge f = e;
                while (f.from() != w)
                {
                    cycle.push(f);
                    f = edgeTo[f.from()];
                }
                cycle.push(f);

                return;
            }
        }

        onStack[v] = false;
    }

    //Does the edge-weighted digraph have a directed cycle?
    public boolean hasCycle() 
    {
        return cycle != null;
    }

    /**
     * Returns a directed cycle if the edge-weighted digraph has a directed cycle,
     * and {@code null} otherwise.
     */
    public Iterable<DirectedEdge> cycle() 
    {
        return cycle;
    }


    // certify that digraph is either acyclic or has a directed cycle
    private boolean check() 
    {

        // edge-weighted digraph is cyclic
        if (hasCycle()) 
        {
            // verify cycle
            DirectedEdge first = null, last = null;
            for (DirectedEdge e : cycle()) 
            {
                if (first == null) first = e;
                if (last != null) {
                    if (last.to() != e.from())
                    {
                        System.err.printf("cycle edges %s and %s not incident\n", last, e);
                        return false;
                    }
                }
                last = e;
            }

            if (last.to() != first.from()) 
            {
                System.err.printf("cycle edges %s and %s not incident\n", last, first);
                return false;
            }
        }


        return true;
    }

    /**
     * Unit tests the {@code EdgeWeightedDirectedCycle} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {

        // create random DAG with V vertices and E edges; then add F random edges
        int V = Integer.parseInt(args[0]);
        int E = Integer.parseInt(args[1]);
        int F = Integer.parseInt(args[2]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(V);
        int[] vertices = new int[V];
        for (int i = 0; i < V; i++)
            vertices[i] = i;
        StdRandom.shuffle(vertices);
        for (int i = 0; i < E; i++) 
        {
            int v, w;
            do 
            {
                v = StdRandom.uniform(V);
                w = StdRandom.uniform(V);
            } while (v >= w);
            double weight = StdRandom.uniform();
            G.addEdge(new DirectedEdge(v, w, weight));
        }

        // add F extra edges
        for (int i = 0; i < F; i++) 
        {
            int v = StdRandom.uniform(V);
            int w = StdRandom.uniform(V);
            double weight = StdRandom.uniform(0.0, 1.0);
            G.addEdge(new DirectedEdge(v, w, weight));
        }

        StdOut.println(G);

        // find a directed cycle
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
        if (finder.hasCycle()) 
        {
            StdOut.print("Cycle: ");
            for (DirectedEdge e : finder.cycle()) 
            {
                StdOut.print(e + " ");
            }
            StdOut.println();
        }

        // or give topologial sort
        else 
        {
            StdOut.println("No directed cycle");
        }
    }

}

顶点排序(有向图中基于深度优先搜索)

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
public class DepthFirstOrder
{
    private boolean[] marked;          // marked[v] = has v been marked in dfs?
    private int[] pre;                 // pre[v]    = preorder  number of v
    private int[] post;                // post[v]   = postorder number of v
    private Queue<Integer> preorder;   // vertices in preorder
    private Queue<Integer> postorder;  // vertices in postorder
    private int preCounter;            // counter or preorder numbering
    private int postCounter;           // counter for postorder numbering

    public DepthFirstOrder(Digraph G) 
    {
        pre    = new int[G.V()];
        post   = new int[G.V()];
        postorder = new Queue<Integer>();
        preorder  = new Queue<Integer>();
        marked    = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);

        assert check();
    }

    //Determines a depth-first order for the edge-weighted digraph {@code G}.
    public DepthFirstOrder(EdgeWeightedDigraph G) 
    {
        pre    = new int[G.V()];
        post   = new int[G.V()];
        postorder = new Queue<Integer>();
        preorder  = new Queue<Integer>();
        marked    = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);
    }

    // run DFS in digraph G from vertex v and compute preorder/postorder
    private void dfs(Digraph G, int v) 
    {
        marked[v] = true;
        pre[v] = preCounter++;
        preorder.enqueue(v);
        for (int w : G.adj(v)) 
        {
            if (!marked[w]) 
            {
                dfs(G, w);
            }
        }
        postorder.enqueue(v);
        post[v] = postCounter++;
    }

    // run DFS in edge-weighted digraph G from vertex v and compute preorder/postorder
    private void dfs(EdgeWeightedDigraph G, int v) 
    {
        marked[v] = true;
        pre[v] = preCounter++;
        preorder.enqueue(v);
        for (DirectedEdge e : G.adj(v)) 
        {
            int w = e.to();
            if (!marked[w])
            {
                dfs(G, w);
            }
        }
        postorder.enqueue(v);
        post[v] = postCounter++;
    }

    //Returns the preorder number of vertex {@code v}.
    public int pre(int v) 
    {
        validateVertex(v);
        return pre[v];
    }

    //Returns the postorder number of vertex {@code v}.
    public int post(int v) 
    {
        validateVertex(v);
        return post[v];
    }

    //Returns the vertices in postorder.
    public Iterable<Integer> post() 
    {
        return postorder;
    }

    //Returns the vertices in preorder.
    public Iterable<Integer> pre() 
    {
        return preorder;
    }
	//Returns the vertices in reverse postorder.
    public Iterable<Integer> reversePost() 
    {
        Stack<Integer> reverse = new Stack<Integer>();
        for (int v : postorder)
            reverse.push(v);
        return reverse;
    }


    // check that pre() and post() are consistent with pre(v) and post(v)
    private boolean check() 
    {

        // check that post(v) is consistent with post()
        int r = 0;
        for (int v : post()) 
        {
            if (post(v) != r) 
            {
                StdOut.println("post(v) and post() inconsistent");
                return false;
            }
            r++;
        }

        // check that pre(v) is consistent with pre()
        r = 0;
        for (int v : pre()) {
            if (pre(v) != r) {
                StdOut.println("pre(v) and pre() inconsistent");
                return false;
            }
            r++;
        }

        return true;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code DepthFirstOrder} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        Digraph G = new Digraph(in);

        DepthFirstOrder dfs = new DepthFirstOrder(G);
        StdOut.println("   v  pre post");
        StdOut.println("--------------");
        for (int v = 0; v < G.V(); v++)
            StdOut.printf("%4d %4d %4d\n", v, dfs.pre(v), dfs.post(v));

        StdOut.print("Preorder:  ");
        for (int v : dfs.pre()) 
            StdOut.print(v + " ");
        StdOut.println();

        StdOut.print("Postorder: ");
        for (int v : dfs.post()) 
            StdOut.print(v + " ");
        StdOut.println();

        StdOut.print("Reverse postorder: ");
        for (int v : dfs.reversePost())
            StdOut.print(v + " ");
        StdOut.println();
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
*  % java DepthFirstOrder tinyDAG.txt
*     v  pre post
*  --------------
*     0    0    8
*     1    3    2
*     2    9   10
*     3   10    9
*     4    2    0
*     5    1    1
*     6    4    7
*     7   11   11
*     8   12   12
*     9    5    6
*    10    8    5
*    11    6    4
*    12    7    3
*  Preorder:  0 5 4 1 6 9 11 12 10 2 3 7 8 
*  Postorder: 4 5 1 12 11 10 9 6 0 3 2 7 8 
*  Reverse postorder: 8 7 2 3 0 6 9 10 11 12 1 5 4

拓扑排序

命题。一幅有向无环图的拓扑排序即为所有顶点的逆后序排列。

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
public class Topological 
{
    private Iterable<Integer> order;  // topological order
    private int[] rank;               // rank[v] = rank of vertex v in order

    /**
     * Determines whether the digraph {@code G} has a topological order and, if so,
     * finds such a topological order.
     */
    public Topological(Digraph G) 
    {
        DirectedCycle finder = new DirectedCycle(G);
        if (!finder.hasCycle()) 
        {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
            rank = new int[G.V()];
            int i = 0;
            for (int v : order)
                rank[v] = i++;
        }
    }

    /**
     * Determines whether the edge-weighted digraph {@code G} has a topological
     * order and, if so, finds such an order.
     */
    public Topological(EdgeWeightedDigraph G)
    {
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
        if (!finder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }

    /**
     * Returns a topological order if the digraph has a topologial order,
     * and {@code null} otherwise.
     */
    public Iterable<Integer> order() 
    {
        return order;
    }

    /**
     * Does the digraph have a topological order?
     * @return {@code true} if the digraph has a topological order (or equivalently,
     *    if the digraph is a DAG), and {@code false} otherwise
     */
    public boolean hasOrder() 
    {
        return order != null;
    }

    /**
     * The the rank of vertex {@code v} in the topological order;
     * -1 if the digraph is not a DAG
     */
    public int rank(int v)
    {
        validateVertex(v);
        if (hasOrder()) return rank[v];
        else            return -1;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = rank.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code Topological} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        String filename  = args[0];
        String delimiter = args[1];
        SymbolDigraph sg = new SymbolDigraph(filename, delimiter);
        Topological topological = new Topological(sg.digraph());
        for (int v : topological.order()) 
            StdOut.println(sg.nameOf(v));
    }

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
*  % java Topological jobs.txt "/"
*  Calculus
*  Linear Algebra
*  Introduction to CS
*  Advanced Programming
*  Algorithms
*  Theoretical CS
*  Artificial Intelligence
*  Robotics
*  Machine Learning
*  Neural Networks
*  Databases
*  Scientific Computing
*  Computational Biology

有向图的强连通性

定义。如果两个顶点v和w是互相可达的，则称它们为强连通的。也就是说，既存在一条从v到w的有向路径，也存在一条从w到v的有向路径。如果一幅有向图中的任意两个顶点都是强连通的，则称这两幅有向图也是强连通的的。

和无向图的连通性一样，有向图中的强连通性也是一种顶点之间等价关系，因为它有着以下性质。

  • 自反性：任意顶点v和自己都是强连通的。
  • 对称性：如果v和w是强连通的，那么w和v也是强连通的。
  • 传递性：如果v和w是强连通的且w和x也是强连通的，那么v和x也是强连通的。

作为一种等价关系，强连通性将所有顶点分为了一些等价类，每个等价类都是由相互均为强连通的顶点的最大子集组成的，我们将这些自己称为强连通分量。

计算强连通分量的Kosaraju算法
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
public class KosarajuSharirSCC 
{
    private boolean[] marked;     // marked[v] = has vertex v been visited?
    private int[] id;             // id[v] = id of strong component containing v
    private int count;            // number of strongly-connected components

    //Computes the strong components of the digraph {@code G}.
    public KosarajuSharirSCC(Digraph G) 
    {

        // compute reverse postorder of reverse graph
        DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());

        // run DFS on G, using reverse postorder to guide calculation
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int v : dfs.reversePost()) 
        {
            if (!marked[v]) 
            {
                dfs(G, v);
                count++;
            }
        }

        // check that id[] gives strong components
        assert check(G);
    }

    // DFS on graph G
    private void dfs(Digraph G, int v) 
    { 
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v)) 
        {
            if (!marked[w]) dfs(G, w);
        }
    }

    //Returns the number of strong components.
    public int count() 
    {
        return count;
    }

    //Are vertices {@code v} and {@code w} in the same strong component?
    public boolean stronglyConnected(int v, int w) 
    {
        validateVertex(v);
        validateVertex(w);
        return id[v] == id[w];
    }

    //Returns the component id of the strong component containing vertex {@code v}.
    public int id(int v) 
    {
        validateVertex(v);
        return id[v];
    }

    // does the id[] array contain the strongly connected components?
    private boolean check(Digraph G) 
    {
        TransitiveClosure tc = new TransitiveClosure(G);
        for (int v = 0; v < G.V(); v++) 
        {
            for (int w = 0; w < G.V(); w++) 
            {
                if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v)))
                    return false;
            }
        }
        return true;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code KosarajuSharirSCC} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        Digraph G = new Digraph(in);
        KosarajuSharirSCC scc = new KosarajuSharirSCC(G);

        // number of connected components
        int m = scc.count();
        StdOut.println(m + " strong components");

        // compute list of vertices in each strong component
        Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
        for (int i = 0; i < m; i++) 
        {
            components[i] = new Queue<Integer>();
        }
        for (int v = 0; v < G.V(); v++) 
        {
            components[scc.id(v)].enqueue(v);
        }

        // print results
        for (int i = 0; i < m; i++) 
        {
            for (int v : components[i]) 
            {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }

    }

}

测试

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
*  % java -Xss50m KosarajuSharirSCC mediumDG.txt 
*  25 strong components
*  7 11 32 36 61 84 95 116 121 128 230   ...
*  28 73 80 104 115 143 149 164 184 185  ...
*  38 40 200 201 207 218 286 387 418 422 ...
*  12 14 56 78 87 103 216 269 271 272    ...
*  42 48 112 135 160 217 243 246 273 346 ...
*  46 76 96 97 224 237 297 303 308 309   ...
*  9 15 21 22 27 90 167 214 220 225 227  ...
*  74 99 133 146 161 166 202 205 245 262 ...
*  43 83 94 120 125 183 195 206 244 254  ...
*  1 13 54 91 92 93 106 140 156 194 208  ...
*  10 39 67 69 131 144 145 154 168 258   ...
*  6 52 66 113 118 122 139 147 212 213   ...
*  8 127 150 182 203 204 249 367 400 432 ...
*  63 65 101 107 108 136 169 170 171 173 ...
*  55 71 102 155 159 198 228 252 325 419 ...
*  4 25 34 58 70 152 172 196 199 210 226 ...
*  2 44 50 88 109 138 141 178 197 211    ...
*  57 89 129 162 174 179 188 209 238 276 ...
*  33 41 49 119 126 132 148 181 215 221  ...
*  3 18 23 26 35 64 105 124 157 186 251  ...
*  5 16 17 20 31 47 81 98 158 180 187    ...
*  24 29 51 59 75 82 100 114 117 134 151 ...
*  30 45 53 60 72 85 111 130 137 142 163 ...
*  19 37 62 77 79 110 153 352 353 361    ...
*  0 68 86 123 165 176 193 239 289 336   ...

命题。Kosaraju算法的预处理所需的时间与V+E成正比且支持常数时间的有向图强连通性查询。

我们能否用和无向图相同的效率解决有向图的连通性问题？这个问题已经被研究了很长时间了（R.E.Tarjan在20世纪70年代末解决了这个问题）。这样一个简单的解决方法实在令人惊讶。

计算强连通分量的Tarjan算法
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
public class TarjanSCC 
{
    private boolean[] marked;        // marked[v] = has v been visited?
    private int[] id;                // id[v] = id of strong component containing v
    private int[] low;               // low[v] = low number of v
    private int pre;                 // preorder number counter
    private int count;               // number of strongly-connected components
    private Stack<Integer> stack;

	//Computes the strong components of the digraph {@code G}.
    public TarjanSCC(Digraph G) 
    {
        marked = new boolean[G.V()];
        stack = new Stack<Integer>();
        id = new int[G.V()];
        low = new int[G.V()];
        for (int v = 0; v < G.V(); v++) 
        {
            if (!marked[v]) dfs(G, v);
        }

        // check that id[] gives strong components
        assert check(G);
    }

    private void dfs(Digraph G, int v) 
    {
        marked[v] = true;
        low[v] = pre++;
        int min = low[v];
        stack.push(v);
        for (int w : G.adj(v)) 
        {
            if (!marked[w]) dfs(G, w);
            if (low[w] < min) min = low[w];
        }
        if (min < low[v]) 
        {
            low[v] = min;
            return;
        }
        int w;
        do 
        {
            w = stack.pop();
            id[w] = count;
            low[w] = G.V();
        } while (w != v);
        count++;
    }


    //Returns the number of strong components.
    public int count() 
    {
        return count;
    }

    // Are vertices {@code v} and {@code w} in the same strong component?
	public boolean stronglyConnected(int v, int w) 
    {
        validateVertex(v);
        validateVertex(w);
        return id[v] == id[w];
    }

    //Returns the component id of the strong component containing vertex {@code v}.
    public int id(int v) 
    {
        validateVertex(v);
        return id[v];
    }

    // does the id[] array contain the strongly connected components?
    private boolean check(Digraph G) 
    {
        TransitiveClosure tc = new TransitiveClosure(G);
        for (int v = 0; v < G.V(); v++) 
        {
            for (int w = 0; w < G.V(); w++) 
            {
                if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v)))
                    return false;
            }
        }
        return true;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code TarjanSCC} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        Digraph G = new Digraph(in);
        TarjanSCC scc = new TarjanSCC(G);

        // number of connected components
        int m = scc.count();
        StdOut.println(m + " components");

        // compute list of vertices in each strong component
        Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
        for (int i = 0; i < m; i++) 
        {
            components[i] = new Queue<Integer>();
        }
        for (int v = 0; v < G.V(); v++) 
        {
            components[scc.id(v)].enqueue(v);
        }

        // print results
        for (int i = 0; i < m; i++) 
        {
            for (int v : components[i]) 
            {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }
    }
}

顶点对可达性

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
public class TransitiveClosure 
{
    private DirectedDFS[] tc;  // tc[v] = reachable from v

    //Computes the transitive closure of the digraph {@code G}.
    public TransitiveClosure(Digraph G) 
    {
        tc = new DirectedDFS[G.V()];
        for (int v = 0; v < G.V(); v++)
            tc[v] = new DirectedDFS(G, v);
    }

    //Is there a directed path from vertex {@code v} to vertex {@code w} in the digraph?
    public boolean reachable(int v, int w) 
    {
        validateVertex(v);
        validateVertex(w);
        return tc[v].marked(w);
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = tc.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code TransitiveClosure} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        Digraph G = new Digraph(in);

        TransitiveClosure tc = new TransitiveClosure(G);

        // print header
        StdOut.print("     ");
        for (int v = 0; v < G.V(); v++)
            StdOut.printf("%3d", v);
        StdOut.println();
        StdOut.println("--------------------------------------------");

        // print transitive closure
        for (int v = 0; v < G.V(); v++) 
        {
            StdOut.printf("%3d: ", v);
            for (int w = 0; w < G.V(); w++)
            {
                if (tc.reachable(v, w)) StdOut.printf("  T");
                else                    StdOut.printf("   ");
            }
            StdOut.println();
        }
    }

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
*  Preprocessing time: O(V(E + V)) time.
*  Query time: O(1).
*  Space: O(V^2).
*
*  % java TransitiveClosure tinyDG.txt
*         0  1  2  3  4  5  6  7  8  9 10 11 12
*  --------------------------------------------
*    0:   T  T  T  T  T  T                     
*    1:      T                                 
*    2:   T  T  T  T  T  T                     
*    3:   T  T  T  T  T  T                     
*    4:   T  T  T  T  T  T                     
*    5:   T  T  T  T  T  T                     
*    6:   T  T  T  T  T  T  T        T  T  T  T
*    7:   T  T  T  T  T  T  T  T  T  T  T  T  T
*    8:   T  T  T  T  T  T  T  T  T  T  T  T  T
*    9:   T  T  T  T  T  T           T  T  T  T
*   10:   T  T  T  T  T  T           T  T  T  T
*   11:   T  T  T  T  T  T           T  T  T  T
*   12:   T  T  T  T  T  T           T  T  T  T

最小生成树

定义。图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点的边。

命题J（切分定理）。在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。

带权重的边的数据类型

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
public class Edge implements Comparable<Edge> 
{ 
    private final int v;
    private final int w;
    private final double weight;

    public Edge(int v, int w, double weight) 
    {
        if (v < 0) throw new IllegalArgumentException("vertex index must be a nonnegative integer");
        if (w < 0) throw new IllegalArgumentException("vertex index must be a nonnegative integer");
        if (Double.isNaN(weight)) throw new IllegalArgumentException("Weight is NaN");
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public double weight() 
    {
        return weight;
    }

    //Returns either endpoint of this edge.
    public int either() 
    {
        return v;
    }

    //Returns the endpoint of this edge that is different from the given vertex.
    public int other(int vertex) {
        if      (vertex == v) return w;
        else if (vertex == w) return v;
        else throw new IllegalArgumentException("Illegal endpoint");
    }

    //Compares two edges by weight.
    @Override
    public int compareTo(Edge that) 
    {
        return Double.compare(this.weight, that.weight);
    }

    public String toString() 
    {
        return String.format("%d-%d %.5f", v, w, weight);
    }
}

加权无向图的数据类型

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
public class EdgeWeightedGraph 
{
    private static final String NEWLINE = System.getProperty("line.separator");

    private final int V;
    private int E;
    private Bag<Edge>[] adj;
    
    //Initializes an empty edge-weighted graph with {@code V} vertices and 0 edges.
    public EdgeWeightedGraph(int V) 
    {
        if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        this.V = V;
        this.E = 0;
        adj = (Bag<Edge>[]) new Bag[V];
        for (int v = 0; v < V; v++) 
            adj[v] = new Bag<Edge>();
    }

    //Initializes a random edge-weighted graph with {@code V} vertices and <em>E</em> edges.
    public EdgeWeightedGraph(int V, int E) 
    {
        this(V);
        if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
        for (int i = 0; i < E; i++) {
            int v = StdRandom.uniform(V);
            int w = StdRandom.uniform(V);
            double weight = Math.round(100 * StdRandom.uniform()) / 100.0;
            Edge e = new Edge(v, w, weight);
            addEdge(e);
        }
    }

    //Initializes an edge-weighted graph from an input stream.
    public EdgeWeightedGraph(In in) 
    {
        if (in == null) throw new IllegalArgumentException("argument is null");

        try 
        {
            V = in.readInt();
            adj = (Bag<Edge>[]) new Bag[V];
            for (int v = 0; v < V; v++) 
            {
                adj[v] = new Bag<Edge>();
            }

            int E = in.readInt();
            if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
            for (int i = 0; i < E; i++) 
            {
                int v = in.readInt();
                int w = in.readInt();
                validateVertex(v);
                validateVertex(w);
                double weight = in.readDouble();
                Edge e = new Edge(v, w, weight);
                addEdge(e);
            }
        }   
        catch (NoSuchElementException e) 
        {
            throw new IllegalArgumentException("invalid input format in EdgeWeightedGraph constructor", e);
        }

    }

    //Initializes a new edge-weighted graph that is a deep copy of {@code G}.
    public EdgeWeightedGraph(EdgeWeightedGraph G) 
    {
        this(G.V());
        this.E = G.E();
        for (int v = 0; v < G.V(); v++) 
        {
            // reverse so that adjacency list is in same order as original
            Stack<Edge> reverse = new Stack<Edge>();
            for (Edge e : G.adj[v]) 
            {
                reverse.push(e);
            }
            for (Edge e : reverse) 
            {
                adj[v].add(e);
            }
        }
    }

    public int V() 
    {
        return V;
    }

    public int E() 
    {
        return E;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    //Adds the undirected edge {@code e} to this edge-weighted graph.
    public void addEdge(Edge e) 
    {
        int v = e.either();
        int w = e.other(v);
        validateVertex(v);
        validateVertex(w);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }

    //Returns the edges incident on vertex {@code v}.
    public Iterable<Edge> adj(int v) 
    {
        validateVertex(v);
        return adj[v];
    }

    //Returns the degree of vertex {@code v}.
    public int degree(int v) 
    {
        validateVertex(v);
        return adj[v].size();
    }

    //Returns all edges in this edge-weighted graph.
    public Iterable<Edge> edges() 
    {
        Bag<Edge> list = new Bag<Edge>();
        for (int v = 0; v < V; v++) 
        {
            int selfLoops = 0;
            for (Edge e : adj(v)) 
            {
                if (e.other(v) > v) 
                {
                    list.add(e);
                }
                // add only one copy of each self loop (self loops will be consecutive)
                else if (e.other(v) == v) 
                {
                    if (selfLoops % 2 == 0) list.add(e);
                    selfLoops++;
                }
            }
        }
        return list;
    }

    public String toString() 
    {
        StringBuilder s = new StringBuilder();
        s.append(V + " " + E + NEWLINE);
        for (int v = 0; v < V; v++) 
        {
            s.append(v + ": ");
            for (Edge e : adj[v]) 
            {
                s.append(e + "  ");
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }
}

Prim算法

命题M。Prim算法的延时实现计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间与E成正比，所需的时间与ElogE成正比（最坏情况）。

延时实现
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
public class LazyPrimMST 
{
    private static final double FLOATING_POINT_EPSILON = 1E-12;

    private double weight;       // total weight of MST
    private Queue<Edge> mst;     // edges in the MST
    private boolean[] marked;    // marked[v] = true iff v on tree
    private MinPQ<Edge> pq;      // edges with one endpoint in tree

    //Compute a minimum spanning tree (or forest) of an edge-weighted graph.
    public LazyPrimMST(EdgeWeightedGraph G) 
    {
        mst = new Queue<Edge>();
        pq = new MinPQ<Edge>();
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)     // run Prim from all vertices to
            if (!marked[v]) prim(G, v);     // get a minimum spanning forest

        // check optimality conditions
        assert check(G);
    }

    // run Prim's algorithm
    private void prim(EdgeWeightedGraph G, int s) 
    {
        scan(G, s);
        while (!pq.isEmpty()) 
        {                        // better to stop when mst has V-1 edges
            Edge e = pq.delMin();                      // smallest edge on pq
            int v = e.either(), w = e.other(v);        // two endpoints
            assert marked[v] || marked[w];
            if (marked[v] && marked[w]) continue;      // lazy, both v and w already scanned
            mst.enqueue(e);                            // add e to MST
            weight += e.weight();
            if (!marked[v]) scan(G, v);               // v becomes part of tree
            if (!marked[w]) scan(G, w);               // w becomes part of tree
        }
    }

    // add all edges e incident to v onto pq if the other endpoint has not yet been scanned
    private void scan(EdgeWeightedGraph G, int v) 
    {
        assert !marked[v];
        marked[v] = true;
        for (Edge e : G.adj(v))
            if (!marked[e.other(v)]) pq.insert(e);
    }

    //Returns the edges in a minimum spanning tree (or forest).
    public Iterable<Edge> edges() 
    {
        return mst;
    }

    //Returns the sum of the edge weights in a minimum spanning tree (or forest).
    public double weight() 
    {
        return weight;
    }

    // check optimality conditions (takes time proportional to E V lg* V)
    private boolean check(EdgeWeightedGraph G) 
    {

        // check weight
        double totalWeight = 0.0;
        for (Edge e : edges()) 
        {
            totalWeight += e.weight();
        }
        if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON) 
        {
            System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight());
            return false;
        }

        // check that it is acyclic
        UF uf = new UF(G.V());	//UF见《数据结构-并查集 》
        for (Edge e : edges()) 
        {
            int v = e.either(), w = e.other(v);
            if (uf.find(v) == uf.find(w)) 
            {
                System.err.println("Not a forest");
                return false;
            }
            uf.union(v, w);
        }

        // check that it is a spanning forest
        for (Edge e : G.edges()) 
        {
            int v = e.either(), w = e.other(v);
            if (uf.find(v) != uf.find(w)) 
            {
                System.err.println("Not a spanning forest");
                return false;
            }
        }

        // check that it is a minimal spanning forest (cut optimality conditions)
        for (Edge e : edges()) 
        {

            // all edges in MST except e
            uf = new UF(G.V());
            for (Edge f : mst) 
            {
                int x = f.either(), y = f.other(x);
                if (f != e) uf.union(x, y);
            }

            // check that e is min weight edge in crossing cut
            for (Edge f : G.edges()) 
            {
                int x = f.either(), y = f.other(x);
                if (uf.find(x) != uf.find(y)) 
                {
                    if (f.weight() < e.weight()) 
                    {
                        System.err.println("Edge " + f + " violates cut optimality conditions");
                        return false;
                    }
                }
            }

        }

        return true;
    }


    /**
     * Unit tests the {@code LazyPrimMST} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        LazyPrimMST mst = new LazyPrimMST(G);
        for (Edge e : mst.edges()) 
        {
            StdOut.println(e);
        }
        StdOut.printf("%.5f\n", mst.weight());
    }

}

测试

1
2
3
4
5
6
7
8
9
*  %  java LazyPrimMST tinyEWG.txt 
*  0-7 0.16000
*  1-7 0.19000
*  0-2 0.26000
*  2-3 0.17000
*  5-7 0.28000
*  4-5 0.35000
*  6-2 0.40000
*  1.81000

Prim算法的这种实现使用了一条优先队列来保存所有的横切边、一个由顶点索引的数组来标记树的顶点以及一条队列来保存最小生成树的边。这种延时实现会在优先队列中保留失效的边。

即时实现

要改进LazyPrimMST，可以尝试从优先队列中删除失效的边，这样优先队列就只含有树顶点和非树顶点的之间的横切边，但其实还可以删除更多的边。关键在于，我们感兴趣的只是连接树顶点和非树顶点中权重最小的边。当我们将顶点v添加到树中时，对于每个非树顶点w产生的变化只可能使得w到最小生成树的距离更近了。简而言之，我们不需要在优先队列中保存所有从w到树顶点的边——而只需要保存其中权重最小的那条，在将v添加到树中后检查是否需要更新这条权重最小的边（因为v-w的权重可能更小）。我们只需遍历v的邻接表就可以完成这个任务。换句话说，我们只会在优先队列中保存每个非树顶点w的一条边：将它与树中的顶点连接起来的权重最小的那条边。将w和树的顶点连接起来的其他权重较大的边迟早会失效，所以没必要在优先队列中保存它们。

命题。Prim算法的即时实现计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间与V成正比，所需的时间与ElogV成正比（最坏情况）。

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
public class PrimMST 
{
    private static final double FLOATING_POINT_EPSILON = 1E-12;

    private Edge[] edgeTo;        // edgeTo[v] = shortest edge from tree vertex to non-tree vertex
    private double[] distTo;      // distTo[v] = weight of shortest such edge
    private boolean[] marked;     // marked[v] = true if v on tree, false otherwise
    private IndexMinPQ<Double> pq;

    //Compute a minimum spanning tree (or forest) of an edge-weighted graph.
    public PrimMST(EdgeWeightedGraph G) 
    {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new IndexMinPQ<Double>(G.V());
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;

        for (int v = 0; v < G.V(); v++)      // run from each vertex to find
            if (!marked[v]) prim(G, v);      // minimum spanning forest

        // check optimality conditions
        assert check(G);
    }

    // run Prim's algorithm in graph G, starting from vertex s
    private void prim(EdgeWeightedGraph G, int s) 
    {
        distTo[s] = 0.0;
        pq.insert(s, distTo[s]);
        while (!pq.isEmpty()) 
        {
            int v = pq.delMin();
            scan(G, v);
        }
    }

    // scan vertex v
    private void scan(EdgeWeightedGraph G, int v) 
    {
        marked[v] = true;
        for (Edge e : G.adj(v)) 
        {
            int w = e.other(v);
            if (marked[w]) continue;         // v-w is obsolete edge
            if (e.weight() < distTo[w]) 
            {
                distTo[w] = e.weight();
                edgeTo[w] = e;
                if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
                else                pq.insert(w, distTo[w]);
            }
        }
    }

    //Returns the edges in a minimum spanning tree (or forest).
    public Iterable<Edge> edges() 
    {
        Queue<Edge> mst = new Queue<Edge>();
        for (int v = 0; v < edgeTo.length; v++) 
        {
            Edge e = edgeTo[v];
            if (e != null) 
            {
                mst.enqueue(e);
            }
        }
        return mst;
    }

    //Returns the sum of the edge weights in a minimum spanning tree (or forest).
    public double weight() 
    {
        double weight = 0.0;
        for (Edge e : edges())
            weight += e.weight();
        return weight;
    }


    // check optimality conditions (takes time proportional to E V lg* V)
    private boolean check(EdgeWeightedGraph G) 
    {

        // check weight
        double totalWeight = 0.0;
        for (Edge e : edges()) 
        {
            totalWeight += e.weight();
        }
        if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON)
        {
            System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight());
            return false;
        }

        // check that it is acyclic
        UF uf = new UF(G.V());
        for (Edge e : edges()) 
        {
            int v = e.either(), w = e.other(v);
            if (uf.find(v) == uf.find(w))
            {
                System.err.println("Not a forest");
                return false;
            }
            uf.union(v, w);
        }

        // check that it is a spanning forest
        for (Edge e : G.edges()) 
        {
            int v = e.either(), w = e.other(v);
            if (uf.find(v) != uf.find(w)) 
            {
                System.err.println("Not a spanning forest");
                return false;
            }
        }

        // check that it is a minimal spanning forest (cut optimality conditions)
        for (Edge e : edges()) 
        {

            // all edges in MST except e
            uf = new UF(G.V());
            for (Edge f : edges()) 
            {
                int x = f.either(), y = f.other(x);
                if (f != e) uf.union(x, y);
            }

            // check that e is min weight edge in crossing cut
            for (Edge f : G.edges()) 
            {
                int x = f.either(), y = f.other(x);
                if (uf.find(x) != uf.find(y)) 
                {
                    if (f.weight() < e.weight()) 
                    {
                        System.err.println("Edge " + f + " violates cut optimality conditions");
                        return false;
                    }
                }
            }

        }

        return true;
    }

    /**
     * Unit tests the {@code PrimMST} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        PrimMST mst = new PrimMST(G);
        for (Edge e : mst.edges()) {
            StdOut.println(e);
        }
        StdOut.printf("%.5f\n", mst.weight());
    }


}

测试

1
2
3
4
5
6
7
8
9
*  %  java PrimMST tinyEWG.txt 
*  1-7 0.19000
*  0-2 0.26000
*  2-3 0.17000
*  4-5 0.35000
*  5-7 0.28000
*  6-2 0.40000
*  0-7 0.16000
*  1.81000

Kruskal算法

命题。Kruskal计算一幅含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间与E成正比，所需的时间与ElogE成正比（最坏情况）。

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
public class KruskalMST 
{
    private static final double FLOATING_POINT_EPSILON = 1E-12;

    private double weight;                        // weight of MST
    private Queue<Edge> mst = new Queue<Edge>();  // edges in MST

    //Compute a minimum spanning tree (or forest) of an edge-weighted graph.
    public KruskalMST(EdgeWeightedGraph G) 
    {
        // more efficient to build heap by passing array of edges
        MinPQ<Edge> pq = new MinPQ<Edge>();
        for (Edge e : G.edges()) 
        {
            pq.insert(e);
        }

        // run greedy algorithm
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1)
        {
            Edge e = pq.delMin();
            int v = e.either();
            int w = e.other(v);
            if (uf.find(v) != uf.find(w)) 
            { // v-w does not create a cycle
                uf.union(v, w);  // merge v and w components
                mst.enqueue(e);  // add edge e to mst
                weight += e.weight();
            }
        }

        // check optimality conditions
        assert check(G);
    }

    //Returns the edges in a minimum spanning tree (or forest).
    public Iterable<Edge> edges() 
    {
        return mst;
    }

    //Returns the sum of the edge weights in a minimum spanning tree (or forest).
    public double weight() 
    {
        return weight;
    }
    
    // check optimality conditions (takes time proportional to E V lg* V)
    private boolean check(EdgeWeightedGraph G) 
    {

        // check total weight
        double total = 0.0;
        for (Edge e : edges()) 
        {
            total += e.weight();
        }
        if (Math.abs(total - weight()) > FLOATING_POINT_EPSILON) 
        {
            System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", total, weight());
            return false;
        }

        // check that it is acyclic
        UF uf = new UF(G.V());
        for (Edge e : edges()) 
        {
            int v = e.either(), w = e.other(v);
            if (uf.find(v) == uf.find(w)) 
            {
                System.err.println("Not a forest");
                return false;
            }
            uf.union(v, w);
        }

        // check that it is a spanning forest
        for (Edge e : G.edges()) 
        {
            int v = e.either(), w = e.other(v);
            if (uf.find(v) != uf.find(w)) 
            {
                System.err.println("Not a spanning forest");
                return false;
            }
        }

        // check that it is a minimal spanning forest (cut optimality conditions)
        for (Edge e : edges()) 
        {

            // all edges in MST except e
            uf = new UF(G.V());
            for (Edge f : mst) 
            {
                int x = f.either(), y = f.other(x);
                if (f != e) uf.union(x, y);
            }
            
            // check that e is min weight edge in crossing cut
            for (Edge f : G.edges())
            {
                int x = f.either(), y = f.other(x);
                if (uf.find(x) != uf.find(y)) 
                {
                    if (f.weight() < e.weight()) 
                    {
                        System.err.println("Edge " + f + " violates cut optimality conditions");
                        return false;
                    }
                }
            }

        }

        return true;
    }
}

最短路径

算法 局限 一般情况 最坏情况 所需空间 优势
Dijkstra算法（即时版本） 边的权重必须非负 ElogV ElogV V 最坏情况下仍有较好的性能
拓扑排序 只适用于无环加权有向图 E+V E+V V 是无环图中的最优算法
Bellman-Ford算法（基于队列） 不能存在负权重环 E+V VE V 适用领域广泛

加权有向边的数据类型

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
public class DirectedEdge 
{ 
    private final int v;
    private final int w;
    private final double weight;

    /**
     * Initializes a directed edge from vertex {@code v} to vertex {@code w} with
     * the given {@code weight}.
     */
    public DirectedEdge(int v, int w, double weight) 
    {
        if (v < 0) throw new IllegalArgumentException("Vertex names must be nonnegative integers");
        if (w < 0) throw new IllegalArgumentException("Vertex names must be nonnegative integers");
        if (Double.isNaN(weight)) throw new IllegalArgumentException("Weight is NaN");
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    //Returns the tail vertex of the directed edge.
    public int from() 
    {
        return v;
    }

    //Returns the head vertex of the directed edge.
    public int to() 
    {
        return w;
    }

    //Returns the weight of the directed edge.
    public double weight()
    {
        return weight;
    }

    //Returns a string representation of the directed edge.
    public String toString() 
    {
        return v + "->" + w + " " + String.format("%5.2f", weight);
    }

}

加权有向图的数据类型

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
public class EdgeWeightedDigraph 
{
    private static final String NEWLINE = System.getProperty("line.separator");

    private final int V;                // number of vertices in this digraph
    private int E;                      // number of edges in this digraph
    private Bag<DirectedEdge>[] adj;    // adj[v] = adjacency list for vertex v
    private int[] indegree;             // indegree[v] = indegree of vertex v
    
    //Initializes an empty edge-weighted digraph with {@code V} vertices and 0 edges.
    public EdgeWeightedDigraph(int V) 
    {
        if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
        this.V = V;
        this.E = 0;
        this.indegree = new int[V];
        adj = (Bag<DirectedEdge>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<DirectedEdge>();
    }

    //Initializes a random edge-weighted digraph with {@code V} vertices and <em>E</em> edges.
    public EdgeWeightedDigraph(int V, int E) 
    {
        this(V);
        if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative");
        for (int i = 0; i < E; i++) 
        {
            int v = StdRandom.uniform(V);
            int w = StdRandom.uniform(V);
            double weight = 0.01 * StdRandom.uniform(100);
            DirectedEdge e = new DirectedEdge(v, w, weight);
            addEdge(e);
        }
    }

    /**  
     * /Initializes an edge-weighted digraph from the specified input stream.
     * The format is the number of vertices <em>V</em>,
     * followed by the number of edges <em>E</em>,
     * followed by <em>E</em> pairs of vertices and edge weights,
     * with each entry separated by whitespace.
     */
    public EdgeWeightedDigraph(In in) 
    {
        if (in == null) throw new IllegalArgumentException("argument is null");
        try 
        {
            this.V = in.readInt();
            if (V < 0) throw new IllegalArgumentException("number of vertices in a Digraph must be nonnegative");
            indegree = new int[V];
            adj = (Bag<DirectedEdge>[]) new Bag[V];
            for (int v = 0; v < V; v++) 
            {
                adj[v] = new Bag<DirectedEdge>();
            }

            int E = in.readInt();
            if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
            for (int i = 0; i < E; i++) 
            {
                int v = in.readInt();
                int w = in.readInt();
                validateVertex(v);
                validateVertex(w);
                double weight = in.readDouble();
                addEdge(new DirectedEdge(v, w, weight));
            }
        }   
        catch (NoSuchElementException e) 
        {
            throw new IllegalArgumentException("invalid input format in EdgeWeightedDigraph constructor", e);
        }
    }

    //Initializes a new edge-weighted digraph that is a deep copy of {@code G}.
    public EdgeWeightedDigraph(EdgeWeightedDigraph G) 
    {
        this(G.V());
        this.E = G.E();
        for (int v = 0; v < G.V(); v++)
            this.indegree[v] = G.indegree(v);
        for (int v = 0; v < G.V(); v++)
        {
            // reverse so that adjacency list is in same order as original
            Stack<DirectedEdge> reverse = new Stack<DirectedEdge>();
            for (DirectedEdge e : G.adj[v]) 
            {
                reverse.push(e);
            }
            for (DirectedEdge e : reverse) 
            {
                adj[v].add(e);
            }
        }
    }

    //Returns the number of vertices in this edge-weighted digraph.
    public int V() 
    {
        return V;
    }

    //Returns the number of edges in this edge-weighted digraph.
    public int E()
    {
        return E;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    //Adds the directed edge {@code e} to this edge-weighted digraph.
    public void addEdge(DirectedEdge e) 
    {
        int v = e.from();
        int w = e.to();
        validateVertex(v);
        validateVertex(w);
        adj[v].add(e);
        indegree[w]++;
        E++;
    }


    //Returns the directed edges incident from vertex {@code v}.
    public Iterable<DirectedEdge> adj(int v)
    {
        validateVertex(v);
        return adj[v];
    }

    //Returns the number of directed edges incident from vertex {@code v}.
    public int outdegree(int v) 
    {
        validateVertex(v);
        return adj[v].size();
    }

    //Returns the number of directed edges incident to vertex {@code v}.
    public int indegree(int v) 
    {
        validateVertex(v);
        return indegree[v];
    }

    //Returns all directed edges in this edge-weighted digraph.
    public Iterable<DirectedEdge> edges() 
    {
        Bag<DirectedEdge> list = new Bag<DirectedEdge>();
        for (int v = 0; v < V; v++) {
            for (DirectedEdge e : adj(v)) 
            {
                list.add(e);
            }
        }
        return list;
    } 

    //Returns a string representation of this edge-weighted digraph.
    public String toString() 
    {
        StringBuilder s = new StringBuilder();
        s.append(V + " " + E + NEWLINE);
        for (int v = 0; v < V; v++) 
        {
            s.append(v + ": ");
            for (DirectedEdge e : adj[v]) 
                s.append(e + "  ");
            s.append(NEWLINE);
        }
        return s.toString();
    }
}

Dijkstra算法

命题。Dijkstra算法能够解决边权重非负的加权有向图的单起点最短路径问题。在一幅含有V个顶点和E条边的加权有向图中，使用Dijkstra算法计算根结点为给定起点的最短路径树所需的空间与V成正比，时间与ElogV成正比（最坏情况下）。

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
public class DijkstraSP 
{
    private double[] distTo;          // distTo[v] = distance  of shortest s->v path
    private DirectedEdge[] edgeTo;    // edgeTo[v] = last edge on shortest s->v path
    private IndexMinPQ<Double> pq;    // priority queue of vertices

    /**
     * Computes a shortest-paths tree from the source vertex {@code s} to every other
     * vertex in the edge-weighted digraph {@code G}.
     */
    public DijkstraSP(EdgeWeightedDigraph G, int s) 
    {
        for (DirectedEdge e : G.edges()) 
        {
            if (e.weight() < 0)
                throw new IllegalArgumentException("edge " + e + " has negative weight");
        }

        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];

        validateVertex(s);

        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;

        // relax vertices in order of distance from s
        pq = new IndexMinPQ<Double>(G.V());
        pq.insert(s, distTo[s]);
        while (!pq.isEmpty()) 
        {
            int v = pq.delMin();
            for (DirectedEdge e : G.adj(v))
                relax(e);
        }

        // check optimality conditions
        assert check(G, s);
    }

    // relax edge e and update pq if changed
    private void relax(DirectedEdge e) 
    {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) 
        {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else                pq.insert(w, distTo[w]);
        }
    }

    //Returns the length of a shortest path from the source vertex {@code s} to vertex {@code v}.
    public double distTo(int v) 
    {
        validateVertex(v);
        return distTo[v];
    }

    //Returns true if there is a path from the source vertex {@code s} to vertex {@code v}.
    public boolean hasPathTo(int v) 
    {
        validateVertex(v);
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    //Returns a shortest path from the source vertex {@code s} to vertex {@code v}.
    public Iterable<DirectedEdge> pathTo(int v) 
    {
        validateVertex(v);
        if (!hasPathTo(v)) return null;
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) 
        {
            path.push(e);
        }
        return path;
    }


    // check optimality conditions:
    // (i) for all edges e:            distTo[e.to()] <= distTo[e.from()] + e.weight()
    // (ii) for all edge e on the SPT: distTo[e.to()] == distTo[e.from()] + e.weight()
    private boolean check(EdgeWeightedDigraph G, int s) {

        // check that edge weights are nonnegative
        for (DirectedEdge e : G.edges()) 
        {
            if (e.weight() < 0) 
            {
                System.err.println("negative edge weight detected");
                return false;
            }
        }

        // check that distTo[v] and edgeTo[v] are consistent
        if (distTo[s] != 0.0 || edgeTo[s] != null)
        {
            System.err.println("distTo[s] and edgeTo[s] inconsistent");
            return false;
        }
        for (int v = 0; v < G.V(); v++) 
        {
            if (v == s) continue;
            if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) 
            {
                System.err.println("distTo[] and edgeTo[] inconsistent");
                return false;
            }
        }

        // check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight()
        for (int v = 0; v < G.V(); v++) 
        {
            for (DirectedEdge e : G.adj(v)) 
            {
                int w = e.to();
                if (distTo[v] + e.weight() < distTo[w]) {
                    System.err.println("edge " + e + " not relaxed");
                    return false;
                }
            }
        }

        // check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight()
        for (int w = 0; w < G.V(); w++)
        {
            if (edgeTo[w] == null) continue;
            DirectedEdge e = edgeTo[w];
            int v = e.from();
            if (w != e.to()) return false;
            if (distTo[v] + e.weight() != distTo[w]) 
            {
                System.err.println("edge " + e + " on shortest path not tight");
                return false;
            }
        }
        return true;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = distTo.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code DijkstraSP} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);
        int s = Integer.parseInt(args[1]);

        // compute shortest paths
        DijkstraSP sp = new DijkstraSP(G, s);


        // print shortest path
        for (int t = 0; t < G.V(); t++) {
            if (sp.hasPathTo(t)) {
                StdOut.printf("%d to %d (%.2f)  ", s, t, sp.distTo(t));
                for (DirectedEdge e : sp.pathTo(t)) {
                    StdOut.print(e + "   ");
                }
                StdOut.println();
            }
            else {
                StdOut.printf("%d to %d         no path\n", s, t);
            }
        }
    }

}

测试

1
2
3
4
5
6
7
*  % java DijkstraSP mediumEWD.txt 0
*  0 to 0 (0.00)  
*  0 to 1 (0.71)  0->44  0.06   44->93  0.07   ...  107->1  0.07   
*  0 to 2 (0.65)  0->44  0.06   44->231  0.10  ...  42->2  0.11   
*  0 to 3 (0.46)  0->97  0.08   97->248  0.09  ...  45->3  0.12   
*  0 to 4 (0.42)  0->44  0.06   44->93  0.07   ...  77->4  0.11   
*  ...

无环加权有向图的最短路径算法

命题。按照拓扑顺序放松顶点，就能在和E+V成正比的时间内解决无环加权有向图的单点最短路径问题。

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
public class AcyclicSP 
{
    private double[] distTo;         // distTo[v] = distance  of shortest s->v path
    private DirectedEdge[] edgeTo;   // edgeTo[v] = last edge on shortest s->v path


    /**
     * Computes a shortest paths tree from {@code s} to every other vertex in
     * the directed acyclic graph {@code G}.
     */
    public AcyclicSP(EdgeWeightedDigraph G, int s) 
    {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];

        validateVertex(s);

        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;

        // visit vertices in topological order
        Topological topological = new Topological(G);
        if (!topological.hasOrder())
            throw new IllegalArgumentException("Digraph is not acyclic.");
        for (int v : topological.order()) {
            for (DirectedEdge e : G.adj(v))
                relax(e);
        }
    }

    // relax edge e
    private void relax(DirectedEdge e) 
    {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) 
        {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
        }       
    }

    //Returns the length of a shortest path from the source vertex {@code s} to vertex {@code v}.
    public double distTo(int v) 
    {
        validateVertex(v);
        return distTo[v];
    }

    //Is there a path from the source vertex {@code s} to vertex {@code v}?
    public boolean hasPathTo(int v) 
    {
        validateVertex(v);
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    //Returns a shortest path from the source vertex {@code s} to vertex {@code v}.
    public Iterable<DirectedEdge> pathTo(int v) 
    {
        validateVertex(v);
        if (!hasPathTo(v)) return null;
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) 
        {
            path.push(e);
        }
        return path;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = distTo.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code AcyclicSP} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {
        In in = new In(args[0]);
        int s = Integer.parseInt(args[1]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);

        // find shortest path from s to each other vertex in DAG
        AcyclicSP sp = new AcyclicSP(G, s);
        for (int v = 0; v < G.V(); v++) 
        {
            if (sp.hasPathTo(v)) 
            {
                StdOut.printf("%d to %d (%.2f)  ", s, v, sp.distTo(v));
                for (DirectedEdge e : sp.pathTo(v))
                {
                    StdOut.print(e + "   ");
                }
                StdOut.println();
            }
            else
            {
                StdOut.printf("%d to %d         no path\n", s, v);
            }
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
*  % java AcyclicSP tinyEWDAG.txt 5
*  5 to 0 (0.73)  5->4  0.35   4->0  0.38   
*  5 to 1 (0.32)  5->1  0.32   
*  5 to 2 (0.62)  5->7  0.28   7->2  0.34   
*  5 to 3 (0.61)  5->1  0.32   1->3  0.29   
*  5 to 4 (0.35)  5->4  0.35   
*  5 to 5 (0.00)  
*  5 to 6 (1.13)  5->1  0.32   1->3  0.29   3->6  0.52   
*  5 to 7 (0.28)  5->7  0.28

命题。解决无环加权有向图中的最长路径问题所需的时间与E+V成正比。

根据这种转换实现$AcyclicLP$类来寻找一幅无环加权有向图中的最长路径就十分简单了。实现该类的一个更简单的方法是修改$AcyclicLP$，将$distTo[]$的初始值变为$Double.NEGATIVE$_$INFINITY$并改变$relax()$方法中的不等式的方向。

优先级限制下的并行任务调度问题的关键路径方法

命题。解决优先级限制下的并行任务调度问题的关键路径法所需的时间为线性级别。

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
public class CPM 
{

    // this class cannot be instantiated
    private CPM() { }

    /**
     *  Reads the precedence constraints from standard input
     *  and prints a feasible schedule to standard output.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) 
    {

        // number of jobs
        int n = StdIn.readInt();

        // source and sink
        int source = 2 * n;
        int sink   = 2 * n + 1;

        // build network
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(2 * n + 2);
        for (int i = 0; i < n; i++) 
        {
            double duration = StdIn.readDouble();
            G.addEdge(new DirectedEdge(source, i, 0.0));
            G.addEdge(new DirectedEdge(i + n, sink, 0.0));
            G.addEdge(new DirectedEdge(i, i + n,    duration));

            // precedence constraints
            int m = StdIn.readInt();
            for (int j = 0; j < m; j++) 
            {
                int precedent = StdIn.readInt();
                G.addEdge(new DirectedEdge(n + i, precedent, 0.0));
            }
        }

        // compute longest path
        AcyclicLP lp = new AcyclicLP(G, source);//AcyclicLP只需将AcyclicSP稍作修改即可

        // print results
        StdOut.println(" job   start  finish");
        StdOut.println("--------------------");
        for (int i = 0; i < n; i++) {
            StdOut.printf("%4d %7.1f %7.1f\n", i, lp.distTo(i), lp.distTo(i+n));
        }
        StdOut.printf("Finish time: %7.1f\n", lp.distTo(sink));
    }

}

测试

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
*  % more jobsPC.txt
*  10
*  41.0  3  1 7 9	
*  51.0  1  2
*  50.0  0
*  36.0  0
*  38.0  0
*  45.0  0
*  21.0  2  3 8
*  32.0  2  3 8
*  32.0  1  2
*  29.0  2  4 6
//左起第一个数为该任务时耗，第二个数代表该任务需要在几个任务之前完成，后续数字为需要在其之前完成的任务编号
//以41.0  3  1 7 9为例
//该任务耗时41.0，需要在三项任务之前完成，分别是第一、第七和第九项任务

*  % java CPM < jobsPC.txt
*   job   start  finish
*  --------------------
*     0     0.0    41.0
*     1    41.0    92.0
*     2   123.0   173.0
*     3    91.0   127.0
*     4    70.0   108.0
*     5     0.0    45.0
*     6    70.0    91.0
*     7    41.0    73.0
*     8    91.0   123.0
*     9    41.0    70.0
*  Finish time:   173.0

Bellman-Ford算法

命题。在任意含有V个顶点的加权有向图中给定起点s，从s无法到达任何负权重环，以下算法能够解决其中的单点最短路径问题：将$distTo[s]$初始化为0，其他

$distTo[]$元素初始化为无穷大。以任意顺序放松有向图的所有边，重复V轮。

命题。Bellman-Ford算法所需的时间和EV成正比，空间和V成正比。

证明。在每一轮中算法都会放松E条边，共重复V轮。

这个方法非常通用，因为它没有指定边的放松顺序。下面将注意力集中在一个通用性稍逊的方法上，其中只放松从任意顶点指出的所有边（顺序任意），以下代码说明了这种方法的简洁性：

1
2
3
4
for (int pass = 0; pass < G.V(); pass++)
       for (int v = 0; v < G.V(); v++)
           for (DirectedEdge e : G.adj(v))
               relax(e);

我们不会仔细研究这个版本，因为它总是会放松VE条边且只需稍作修改即可使算法在一般的应用场景中更加高效。

命题。对于任意含有V个顶点的加权有向图和给定的起点s，在最坏情况下基于队列的Bellman-Ford算法解决最短路径问题（或者找到从s可达的负权重环）所需的时间与EV成正比，空间和V成正比。

基于队列的Bellman-Ford算法
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
public class BellmanFordSP 
{
    private double[] distTo;               // distTo[v] = distance  of shortest s->v path
    private DirectedEdge[] edgeTo;         // edgeTo[v] = last edge on shortest s->v path
    private boolean[] onQueue;             // onQueue[v] = is v currently on the queue?
    private Queue<Integer> queue;          // queue of vertices to relax
    private int cost;                      // number of calls to relax()
    private Iterable<DirectedEdge> cycle;  // negative cycle (or null if no such cycle)

    /**
     * Computes a shortest paths tree from {@code s} to every other vertex in
     * the edge-weighted digraph {@code G}.
     */
    public BellmanFordSP(EdgeWeightedDigraph G, int s) 
    {
        distTo  = new double[G.V()];
        edgeTo  = new DirectedEdge[G.V()];
        onQueue = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;

        // Bellman-Ford algorithm
        queue = new Queue<Integer>();
        queue.enqueue(s);
        onQueue[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle()) 
        {
            int v = queue.dequeue();
            onQueue[v] = false;
            relax(G, v);
        }

        assert check(G, s);
    }

    // relax vertex v and put other endpoints on queue if changed
    private void relax(EdgeWeightedDigraph G, int v) 
    {
        for (DirectedEdge e : G.adj(v)) 
        {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) 
            {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (!onQueue[w]) 
                {
                    queue.enqueue(w);
                    onQueue[w] = true;
                }
            }
            if (++cost % G.V() == 0) 
            {
                findNegativeCycle();
                if (hasNegativeCycle()) return;  // found a negative cycle
            }
        }
    }

    //Is there a negative cycle reachable from the source vertex {@code s}?
    public boolean hasNegativeCycle() 
    {
        return cycle != null;
    }

    /**
     * Returns a negative cycle reachable from the source vertex {@code s}, or {@code null}
     * if there is no such cycle.
     */
    public Iterable<DirectedEdge> negativeCycle() 
    {
        return cycle;
    }

    // by finding a cycle in predecessor graph
    private void findNegativeCycle() {
        int V = edgeTo.length;
        EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
        for (int v = 0; v < V; v++)
            if (edgeTo[v] != null)
                spt.addEdge(edgeTo[v]);

        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
        cycle = finder.cycle();
    }

    //Returns the length of a shortest path from the source vertex {@code s} to vertex {@code v}.
    public double distTo(int v) 
    {
        validateVertex(v);
        if (hasNegativeCycle())
            throw new UnsupportedOperationException("Negative cost cycle exists");
        return distTo[v];
    }

    //Is there a path from the source {@code s} to vertex {@code v}?
    public boolean hasPathTo(int v) 
    {
        validateVertex(v);
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    //Returns a shortest path from the source {@code s} to vertex {@code v}.
    public Iterable<DirectedEdge> pathTo(int v) 
    {
        validateVertex(v);
        if (hasNegativeCycle())
            throw new UnsupportedOperationException("Negative cost cycle exists");
        if (!hasPathTo(v)) return null;
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) 
        {
            path.push(e);
        }
        return path;
    }

    // check optimality conditions: either 
    // (i) there exists a negative cycle reacheable from s
    //     or 
    // (ii)  for all edges e = v->w:            distTo[w] <= distTo[v] + e.weight()
    // (ii') for all edges e = v->w on the SPT: distTo[w] == distTo[v] + e.weight()
    private boolean check(EdgeWeightedDigraph G, int s) 
    {

        // has a negative cycle
        if (hasNegativeCycle()) 
        {
            double weight = 0.0;
            for (DirectedEdge e : negativeCycle()) 
            {
                weight += e.weight();
            }
            if (weight >= 0.0) {
                System.err.println("error: weight of negative cycle = " + weight);
                return false;
            }
        }

        // no negative cycle reachable from source
        else 
        {

            // check that distTo[v] and edgeTo[v] are consistent
            if (distTo[s] != 0.0 || edgeTo[s] != null) 
            {
                System.err.println("distanceTo[s] and edgeTo[s] inconsistent");
                return false;
            }
            for (int v = 0; v < G.V(); v++) 
            {
                if (v == s) continue;
                if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) 
                {
                    System.err.println("distTo[] and edgeTo[] inconsistent");
                    return false;
                }
            }

            // check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight()
            for (int v = 0; v < G.V(); v++) 
            {
                for (DirectedEdge e : G.adj(v))
                {
                    int w = e.to();
                    if (distTo[v] + e.weight() < distTo[w]) 
                    {
                        System.err.println("edge " + e + " not relaxed");
                        return false;
                    }
                }
            }

            // check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight()
            for (int w = 0; w < G.V(); w++) 
            {
                if (edgeTo[w] == null) continue;
                DirectedEdge e = edgeTo[w];
                int v = e.from();
                if (w != e.to()) return false;
                if (distTo[v] + e.weight() != distTo[w]) 
                {
                    System.err.println("edge " + e + " on shortest path not tight");
                    return false;
                }
            }
        }

        StdOut.println("Satisfies optimality conditions");
        StdOut.println();
        return true;
    }

    // throw an IllegalArgumentException unless {@code 0 <= v < V}
    private void validateVertex(int v) 
    {
        int V = distTo.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    /**
     * Unit tests the {@code BellmanFordSP} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args)
    {
        In in = new In(args[0]);
        int s = Integer.parseInt(args[1]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);

        BellmanFordSP sp = new BellmanFordSP(G, s);

        // print negative cycle
        if (sp.hasNegativeCycle()) 
        {
            for (DirectedEdge e : sp.negativeCycle())
                StdOut.println(e);
        }

        // print shortest paths
        else {
            for (int v = 0; v < G.V(); v++) 
            {
                if (sp.hasPathTo(v)) 
                {
                    StdOut.printf("%d to %d (%5.2f)  ", s, v, sp.distTo(v));
                    for (DirectedEdge e : sp.pathTo(v)) 
                    {
                        StdOut.print(e + "   ");
                    }
                    StdOut.println();
                }
                else 
                {
                    StdOut.printf("%d to %d           no path\n", s, v);
                }
            }
        }

    }

}

测试

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
*  $more tinyEWD.txt
*  8
*  15
*  4 5  0.35
*  5 4  0.35
*  4 7  0.37
*  5 7  0.28
*  7 5  0.28
*  5 1  0.32
*  0 4  0.38
*  0 2  0.26
*  7 3  0.39
*  1 3  0.29
*  2 7  0.34
*  6 2 -1.20
*  3 6  0.52
*  6 0 -1.40
*  6 4 -1.25

*  % java BellmanFordSP tinyEWDn.txt 0
*  0 to 0 ( 0.00)  
*  0 to 1 ( 0.93)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   6->4 -1.25   4->5  0.35   5->1  0.32
*  0 to 2 ( 0.26)  0->2  0.26   
*  0 to 3 ( 0.99)  0->2  0.26   2->7  0.34   7->3  0.39   
*  0 to 4 ( 0.26)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   6->4 -1.25   
*  0 to 5 ( 0.61)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   6->4 -1.25   4->5  0.35
*  0 to 6 ( 1.51)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   
*  0 to 7 ( 0.60)  0->2  0.26   2->7  0.34