图（ Graph ）的算法探究

发表于 分类于 本文字数： 2.3k 阅读时长 ≈ 8 分钟

深度优先遍历

思想

深度优先遍历，从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。

具体算法表述如下：

  1. 访问初始结点 v，并标记结点 v 为已访问。
  2. 查找结点 v 的第一个邻接结点 w 。
  3. 若 w 存在，则继续执行 4，否则算法结束。
  4. 若 w 未被访问，对 w 进行深度优先遍历递归（ 即把 w 当做另一个 v ，然后进行步骤 123 ）。
  5. 查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3。

例如下图，其深度优先遍历顺序为 1->2->4->8->5->3->6->7

DFS-BFS

代码

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

//Java
import java.util.*;

public class DFS {

    private DirectedGraph graph;

    Queue<Vertex> visited = new LinkedList<>();

    public DFS(DirectedGraph graph){
        this.graph = graph;
    }

    public Queue<Vertex> findDFS(String start_id){

        Vertex parent = null;
        ArrayList<Vertex> adjacent;

        for (Map.Entry<Vertex, ArrayList<Vertex>> entry : graph.getAdjacentList().entrySet()){

            Vertex vertex = entry.getKey();
            if (vertex.getId().equals(start_id)) {

                if (!visited.contains(vertex)) {
                    visited.offer(vertex);
                    parent = vertex;
                    adjacent = graph.getAdjacentVertex(parent);

                        for (int i = 0; i < adjacent.size(); i++) {

                            findDFS(adjacent.get(i).getId());
                        }

                }
            }
        }

        for (Map.Entry<Vertex, ArrayList<Vertex>> entry : graph.getAdjacentList().entrySet()){

            Vertex vertex = entry.getKey();
            if (!visited.contains(vertex)){
                findDFS(vertex.getId());
            }
        }

        return visited;
    }

    public static void main(String[] args){

        /*
            构造有向图：
            共有六个点：a, b, c, d, e, f
            点 a 指向 b 和 d
            点 b 指向 e
            点 d 指向 b
            点 e 指向 d
            点 c 指向 e 和 f
            点 f 指向 f， 即自己
         */

        //点初始化
        Vertex a = new Vertex("a");
        Vertex b = new Vertex("b");
        Vertex c = new Vertex("c");
        Vertex d = new Vertex("d");
        Vertex e = new Vertex("e");
        Vertex f = new Vertex("f");

        //图初始化
        DirectedGraph graph = new DirectedGraph();
        graph.addVertex(a, b);
        graph.addVertex(a, d);
        graph.addVertex(b, e);
        graph.addVertex(e, d);
        graph.addVertex(d, b);
        graph.addVertex(c, e);
        graph.addVertex(c, f);
        graph.addVertex(f, f);

        DFS dfs = new DFS(graph);
        Queue<Vertex> queue= new LinkedList<>();
        queue = dfs.findDFS("a");

        System.out.println("Index: ");
        for (Vertex vertex : queue){
            System.out.print(vertex.getId() + " ");
        }
    }

}

//点
class Vertex{

    private String id;

    public Vertex(String id){
        this.id = id;
    }

    public String getId() {
        return this.id;
    }

}

//有向图
class DirectedGraph{

    private HashMap<Vertex, ArrayList<Vertex>> adjacent_list;

    public DirectedGraph(){
        this.adjacent_list = new HashMap<>();
    }

    //vertex1 指向 vertex2
    public void addVertex(Vertex vertex1, Vertex vertex2){

        if ( adjacent_list.containsKey(vertex1) ){
            adjacent_list.get(vertex1).add(vertex2);
        }
        else {
            adjacent_list.put(vertex1, new ArrayList<>());
            addVertex(vertex1, vertex2);
        }
    }

    public HashMap<Vertex, ArrayList<Vertex>> getAdjacentList() {
        return this.adjacent_list;
    }

    public ArrayList<Vertex> getAdjacentVertex(Vertex vertex){
        return adjacent_list.get(vertex);
    }
}

广度优先遍历

思想

广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

具体算法表述如下：

  1. 访问初始结点 v 并标记结点 v 为已访问。
  2. 结点 v 入队列
  3. 当队列非空时，继续执行，否则算法结束。
  4. 出队列，取得队头结点 u。
  5. 查找结点 u 的第一个邻接结点 w 。
  6. 若结点 u 的邻接结点 w 不存在，则转到步骤 3 ；否则循环执行以下三个步骤：
    • 若结点w尚未被访问，则访问结点 w 并标记为已访问。
    • 结点 w 入队列
    • 查找结点u的继w邻接结点后的下一个邻接结点 w，转到步骤6。

如下图，其广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8

DFS/BFS.webp

代码

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

//Java
import java.util.*;

public class BFS {

    private DirectedGraph graph;


    public BFS(DirectedGraph graph){
        this.graph = graph;
    }

    public void findBFS(String start_id){


        ArrayList<Vertex> adjacent;
        Queue<Vertex> visited = new LinkedList<>();
        ArrayList<Vertex> parent = new ArrayList<>();

        for (Map.Entry<Vertex, ArrayList<Vertex>> entry : graph.getAdjacentList().entrySet()){

            Vertex vertex = entry.getKey();
            if (vertex.getId().equals(start_id)){

                visited.add(vertex);
                parent.add(vertex);

                while (parent.size() != 0){

                    ArrayList<Vertex> next = new ArrayList<>();

                    for (int k = 0; k < parent.size(); k++) {

                        adjacent = graph.getAdjacentVertex(parent.get(k));

                        for (int j = 0; j < adjacent.size(); j++) {

                            if (!visited.contains(adjacent.get(j))){

                                visited.add(adjacent.get(j));
                                next.add(adjacent.get(j));
                            }
                        }
                    }
                    parent = next;
                }
            }
        }

        for (Vertex vertex : visited){
            System.out.print(vertex.getId() + " ");
        }
    }

    public static void main(String[] args){

        /*
        构造无向图:
        点 1 连接 点 2 和 点 3；
        点 2 连接 点 4 和 点 5；
        点 4 连接 点 8；
        点 5 连接 点 8；
        点 3 连接 点 6 和 点 7；
        点 6， 点 7 互相连接。
        */

        //点
        Vertex a = new Vertex("1");
        Vertex b = new Vertex("2");
        Vertex c = new Vertex("3");
        Vertex d = new Vertex("4");
        Vertex e = new Vertex("5");
        Vertex f = new Vertex("6");
        Vertex g = new Vertex("7");
        Vertex h = new Vertex("8");

        //图
        DirectedGraph graph = new DirectedGraph();

        graph.addVertex(a, b);
        graph.addVertex(a, c);

        graph.addVertex(b, a);
        graph.addVertex(b, d);
        graph.addVertex(b, e);

        graph.addVertex(c, a);
        graph.addVertex(c, f);
        graph.addVertex(c, g);

        graph.addVertex(d, b);
        graph.addVertex(d, h);

        graph.addVertex(e, b);
        graph.addVertex(e, h);

        graph.addVertex(f, c);
        graph.addVertex(f, g);

        graph.addVertex(g, c);
        graph.addVertex(g, f);

        graph.addVertex(h, d);
        graph.addVertex(h, e);

        BFS bfs = new BFS(graph);

        System.out.println("Index: ");
        bfs.findBFS("1");
    }

}

//点
class Vertex{

    private String id;

    public Vertex(String id){
        this.id = id;
    }

    public String getId() {
        return this.id;
    }
}

//无向图
class DirectedGraph{

    private HashMap<Vertex, ArrayList<Vertex>> adjacent_list;

    public DirectedGraph(){
        this.adjacent_list = new HashMap<>();
    }

    public void addVertex(Vertex vertex1, Vertex vertex2){

        if ( adjacent_list.containsKey(vertex1) ){
            adjacent_list.get(vertex1).add(vertex2);
        }
        else {
            adjacent_list.put(vertex1, new ArrayList<>());
            addVertex(vertex1, vertex2);
        }
    }

    public HashMap<Vertex, ArrayList<Vertex>> getAdjacentList() {
        return this.adjacent_list;
    }

    public ArrayList<Vertex> getAdjacentVertex(Vertex vertex){
        return adjacent_list.get(vertex);
    }
}

Dijkstra 算法

定义

戴克斯特拉算法（ 英语：Dijkstra’s algorithm ）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题，算法最终得到一个最短路径树。

这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0（ d [ s ] = 0）。若对于顶点 s 存在能直接到达的边（ s , m ），则把 d [ m ] 设为 w（ s , m ）,同时把所有其他（ s 不能直接到达的 ）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（ 对于所有顶点的集合 V 中的任意顶点 v， 若 v 不为 s 和上述 m 之一， d [ v ] = ∞ ）。当算法结束时，d [ v ] 中保存的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。

时间复杂度

对于基于顶点集 Q 的实现，算法的运行时间是 $O\left(\left|E\right|\cdot dk_{Q}+\left|V\right|\cdot em_{Q}\right )$，其中 $dk_{Q}$ 和 $em_{Q}$ 分别表示完成键的降序排列时间和从 Q 中提取最小键值的时间。

Dijkstra 算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q，所以搜索Q中最小元素的运算（ Extract-Min( Q ) ）只需要线性搜索 Q 中的所有元素。这样的话算法的运行时间是 $O\left( n^{2}\right)$。

对于边数少于 $n^{2}$ 的稀疏图来说，我们可以用邻接表来更有效的实现该算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点（ Extract-Min ）。当用到二叉堆的时候，算法所需的时间为 $O\left( \left( m+n\right) \log n\right)$ ，斐波纳契堆能稍微提高一些性能，让算法运行时间达到 $O\left( m+n\log n\right)$ 。然而，使用斐波纳契堆进行编程，常常会由于算法常数过大而导致速度没有显着提高。

代码

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

//Java
import java.util.*;

public class Dijkstra {

    private DirectedGraph graph;

    public Dijkstra(DirectedGraph graph){

        this.graph = graph;
    }

    public class VertexComparator implements Comparator<Vertex>{

        @Override
        public int compare(Vertex v1, Vertex v2){
            return Integer.compare(v1.getDistance(), v2.getDistance());
        }
    }

    public Set<Vertex> findShortestPath(String source_id){

        //优先队列，倒序排列，即 distance 小的点在前
        Queue<Vertex> queue = new PriorityQueue<>(10, new VertexComparator());

        for (Map.Entry<Vertex, ArrayList<Edge>> entry : graph.getAdjacentList().entrySet()){

            Vertex vertex = entry.getKey();

            if (vertex.getId().equals(source_id)){
                vertex.setDistance(0);
                queue.add(vertex);
            }
        }

        Set<Vertex> visited = new HashSet<>();

        while (!queue.isEmpty()){

            Vertex vertex = queue.poll();

            if (!visited.contains(vertex)) {
                visited.add(vertex);

                for (Edge edge : graph.getAdjacentEdges(vertex)) {

                    Vertex v = edge.getAdjacentVertex(vertex);

                    int new_distance = vertex.getDistance() + edge.gerWeight();

                    if (new_distance < v.getDistance()) {

                        v.setDistance(new_distance);
                        queue.add(v);
                    }
                }
            }
        }
        return graph.getAdjacentList().keySet();
    }

    public static void main(String[] args){

        /*
        构造一个简单有向图如下：
        四个点：
            起点，A 点，B 点， 终点；
        五条边：
            起点指向点 A，权重为 6；
            起点指向点 B，权重为 2；
            点 B 指向点 A，权重为 3；
            点 A 指向终点，权重为 1；
            点 B 指向终点，权重为5.
         */

        //点初始化
        Vertex start = new Vertex("Start");
        Vertex a = new Vertex("A");
        Vertex b = new Vertex("B");
        Vertex end = new Vertex("End");

        //线初始化
        Edge start_a = new Edge(start, a, 6);
        Edge start_b = new Edge(start, b, 2);
        Edge b_a = new Edge(b, a, 3);
        Edge a_end = new Edge(a, end, 1);
        Edge b_end = new Edge(b, end, 5);

        //图初始化
        DirectedGraph graph = new DirectedGraph();

        graph.addVertex(start);
        graph.addVertex(a);
        graph.addVertex(b);
        graph.addVertex(end);

        graph.addEdge(start_a);
        graph.addEdge(start_b);
        graph.addEdge(b_a);
        graph.addEdge(a_end);
        graph.addEdge(b_end);

        //Dijkstra
        Dijkstra dijkstra = new Dijkstra(graph);

        Set<Vertex> set = dijkstra.findShortestPath("Start");

        for (Vertex vertex : set){
            System.out.println("Vertex: " + vertex.getId() + " and Vertex distance: " + vertex.getDistance());
        }

    }


}

//点
class Vertex{

    private String id ;
    private int distance = Integer.MAX_VALUE;

    public Vertex(String id){
        this.id = id;
    }

    public String getId() {
        return this.id;
    }

    public int getDistance(){
        return this.distance;
    }

    public void setDistance(int distance){
        this.distance = distance;
    }
}

//线
class Edge{

    private Vertex in; //入点，有向线段尾
    private Vertex out; //出点，有向线段头
    private int weight; //权重

    public Edge(Vertex in, Vertex out, int weight){
        this.in = in;
        this.out = out;
        this.weight = weight;
    }

    public Vertex getIn() {
        return this.in;
    }

    public Vertex getOut() {
        return this.out;
    }

    public int gerWeight(){
        return this.weight;
    }

    //获得邻接点
    public Vertex getAdjacentVertex(Vertex vertex){
        return vertex.getId().equals(this.in.getId()) ? this.out : this.in;
    }
}

//有向图
class DirectedGraph{

    //链表
    private HashMap<Vertex, ArrayList<Vertex>> adjacent_list;

    public DirectedGraph(){
        this.adjacent_list = new HashMap<>();
    }

    public void addVertex(Vertex vertex){

        if (adjacent_list.containsKey(vertex))
            return;

        adjacent_list.put(vertex, new ArrayList<>());
    }

    public void addEdge(Edge edge){

        this.addVertex(edge.getIn());
        this.addVertex(edge.getOut());
        adjacent_list.get(edge.getIn()).add(edge);
    }

    public HashMap<Vertex, ArrayList<Edge>> getAdjacentList() {
        return adjacent_list;
    }

    public ArrayList<Edge> getAdjacentEdges(Vertex vertex){
        return adjacent_list.get(vertex);
    }
}

参考