算法：图（Graph）的遍历、最小生成树和拓扑排序

背景

不同的数据结构有不同的用途，像：数组、链表、队列、栈多数是用来做为基本的工具使用，二叉树多用来作为已排序元素列表的存储，B 树用在存储中，本文介绍的 Graph 多数是为了解决现实问题（说到底，所有的数据结构都是这个目的），如：网络布局、任务安排等。

图的基本概念

示例

顶点（Vertex）

上图的 1、2、3、4、5、6 就是顶点。

邻接（Adjoin）

如果 A 和 B 通过定向边相连，且方向为 A -> B，则 B 为 A 的邻接，如果相连的边是没有方向的，则 A 和 B 互为邻接。

边（Edge）

顶点之间的连线就是边。

连通图（Connected Graph）

不考虑边的方向性，从任何一个节点都可以遍历到其它节点。本文的所有算法（除了拓扑排序）只适合连通图。

定向图（Directed Graph）

图中的所有边都带方向。

权重图（Weighted Graph）

图中的所有边都有权重。

图的程序表示

如果图 T 有 A、B、C 三个节点，有 A -> B，B -> C，C -> A 三个边（没有方向），如何在程序中表示 T 呢？

邻接矩阵

    A   B   C
A  0   1   0
B  0   0   1
C  1   0   0

矩阵的行代表了定向边的起始顶点，矩阵的列代表了定向边的介绍顶点，矩阵中的值：1 代表了列是行的邻接，0 则反之。如果边没有方向，则矩阵是相对于正对角线是对称的。

邻接列表

A：[ B ]
B：[ C ]
C：[ A ]

这个就不多说了，多数书籍使用都是邻接矩阵。

代码

 1         class Vertex<T>
 2         {
 3             public T Value { get; set; }
 4 
 5             public bool WasVisited { get; set; }
 6         }
 7 
 8         class Graph<T>
 9         {
10             #region 私有字段
11 
12             private int _maxSize;
13             private Vertex<T>[] _vertexs;
14             private bool[][] _edges;
15             private int _vertexCount = 0;
16 
17             #endregion
18 
19             #region 构造方法
20 
21             public Graph(int maxSize)
22             {
23                 _maxSize = maxSize;
24                 _vertexs = new Vertex<T>[_maxSize];
25                 _edges = new bool[_maxSize][];
26                 for (var i = 0; i < _maxSize; i++)
27                 {
28                     _edges[i] = new bool[_maxSize];
29                 }
30             }
31 
32             #endregion
33 
34             #region 添加顶点
35 
36             public Graph<T> AddVertex(T value)
37             {
38                 _vertexs[_vertexCount++] = new Vertex<T> { Value = value };
39 
40                 return this;
41             }
42 
43             #endregion
44 
45             #region 添加边
46 
47             public Graph<T> AddUnDirectedEdge(T startItem, T endItem)
48             {
49                 var startIndex = this.GetVertexIndex(startItem);
50                 var endIndex = this.GetVertexIndex(endItem);
51 
52                 _edges[startIndex][endIndex] = true;
53                 _edges[endIndex][startIndex] = true;
54 
55                 return this;
56             }
57 
58             public Graph<T> AddDirectedEdge(T startItem, T endItem)
59             {
60                 var startIndex = this.GetVertexIndex(startItem);
61                 var endIndex = this.GetVertexIndex(endItem);
62 
63                 _edges[startIndex][endIndex] = true;
64 
65                 return this;
66             }
67 
68             #endregion
69         }

图的常见算法

遍历

本文的遍历算法只适合一般的无向图。

深度优先遍历

深度优先遍历的原则是：尽可能的离开始节点远，二叉树的三种遍历算法都属于这种算法。

示例

从 A 开始的遍历顺序为（邻接的遍历顺序为字母升序）：ABCEDBF。

栈版本

 1             #region 深度优先遍历：栈版本
 2 
 3             public void DepthFirstSearch(T startItem, Action<T> action)
 4             {
 5                 var startIndex = this.GetVertexIndex(startItem);
 6                 var stack = new Stack<int>();
 7 
 8                 this.DepthFirstSearchVisit(stack, startIndex, action);
 9                 while (stack.Count > 0)
10                 {
11                     var adjoinVertexIndex = this.GetNextUnVisitedAdjoinVertexIndex(stack.Peek());
12                     if (adjoinVertexIndex >= 0)
13                     {
14                         this.DepthFirstSearchVisit(stack, adjoinVertexIndex, action);
15                     }
16                     else
17                     {
18                         stack.Pop();
19                     }
20                 }
21 
22                 this.ResetVisited();
23             }
24 
25             private void DepthFirstSearchVisit(Stack<int> stack, int index, Action<T> action)
26             {
27                 _vertexs[index].WasVisited = true;
28                 action(_vertexs[index].Value);
29                 stack.Push(index);
30             }
31 
32             #endregion

递归版本

 1             #region 深度优先遍历：递归版本
 2 
 3             public void DepthFirstSearchRecursion(T startItem, Action<T> action)
 4             {
 5                 var startIndex = this.GetVertexIndex(startItem);
 6 
 7                 this.DepthFirstSearchRecursionVisit(startIndex, action);
 8 
 9                 this.ResetVisited();
10             }
11 
12             private void DepthFirstSearchRecursionVisit(int index, Action<T> action)
13             {
14                 _vertexs[index].WasVisited = true;
15                 action(_vertexs[index].Value);
16 
17                 var adjoinVertexIndex = this.GetNextUnVisitedAdjoinVertexIndex(index);
18                 while (adjoinVertexIndex >= 0)
19                 {
20                     this.DepthFirstSearchRecursionVisit(adjoinVertexIndex, action);
21                     adjoinVertexIndex = this.GetNextUnVisitedAdjoinVertexIndex(index);
22                 }
23             }
24 
25             #endregion

广度优先遍历

广度优先遍历的原则是：尽可能的离开始节点近。这个算法没有办法通过递归实现，多数都是使用的队列（终于发现了队列的又一个用处）。

示例

从 A 开始的遍历顺序为（邻接的遍历顺序为字母升序）：ABCEDFB。

代码

 1             #region 广度优先遍历
 2 
 3             public void BreadthFirstSearch(T startItem, Action<T> action)
 4             {
 5                 var startIndex = this.GetVertexIndex(startItem);
 6                 var queue = new Queue<int>();
 7 
 8                 this.BreadthFirstSearchVisit(queue, startIndex, action);
 9                 while (queue.Count > 0)
10                 {
11                     var adjoinVertexIndexs = this.GetNextUnVisitedAdjoinVertexIndexs(queue.Dequeue());
12                     foreach (var adjoinVertexIndex in adjoinVertexIndexs)
13                     {
14                         this.BreadthFirstSearchVisit(queue, adjoinVertexIndex, action);
15                     }
16                 }
17 
18                 this.ResetVisited();
19             }
20 
21             private void BreadthFirstSearchVisit(Queue<int> queue, int index, Action<T> action)
22             {
23                 _vertexs[index].WasVisited = true;
24                 action(_vertexs[index].Value);
25                 queue.Enqueue(index);
26             }
27 
28             #endregion

最小生成树

本文的最小生成树算法只适合一般的无向图。

将 N 个顶点连接起来的最小树叫：最小生成树。

给定一个颗有 N 个顶点的连通图，则最小生成树的边为：N - 1。

不同的遍历算法生成的最小生成树是不同的，下面使用广度优先遍历来生成最小树。

示例

从 A 开始的遍历顺序为（邻接的遍历顺序为字母升序）：A->B、B->C、C->E、E->D、E->F、D->B。

代码

 1             #region 最小生成树
 2 
 3             public void DisplayMinimumSpanningTree(T startItem)
 4             {
 5                 var startIndex = this.GetVertexIndex(startItem);
 6                 var queue = new Queue<int>();
 7 
 8                 _vertexs[startIndex].WasVisited = true;
 9                 queue.Enqueue(startIndex);
10                 while (queue.Count > 0)
11                 {
12                     var currentIndex = queue.Dequeue();
13                     var adjoinVertexIndexs = this.GetNextUnVisitedAdjoinVertexIndexs(currentIndex);
14                     foreach (var adjoinVertexIndex in adjoinVertexIndexs)
15                     {
16                         Console.WriteLine(_vertexs[currentIndex].Value + "->" + _vertexs[adjoinVertexIndex].Value);
17 
18                         _vertexs[adjoinVertexIndex].WasVisited = true;
19                         queue.Enqueue(adjoinVertexIndex);
20                     }
21                 }
22 
23                 this.ResetVisited();
24             }
25 
26             #endregion

拓扑排序

拓扑排序只适合定向图，且图中不存在循环结构。其算法非常简单，依次获取图中的没有邻接顶点的顶点，然后删除该顶点。

示例

上图出现了循环结构，假如没有顶点 C，拓扑排序的结果为（顶点的遍历顺序为字母升序）：EFDAB。

算法

 1             #region 拓扑排序
 2 
 3             public List<T> TopologySort()
 4             {
 5                 var cloneVertexs = (Vertex<T>[])_vertexs.Clone();
 6                 var cloneEdges = (bool[][])_edges.Clone();
 7                 var cloneVertexCount = _vertexCount;
 8 
 9                 var results = new List<T>();
10                 while (_vertexCount > 0)
11                 {
12                     var successor = this.NextSuccessor();
13                     if (successor == -1)
14                     {
15                         throw new InvalidOperationException("出现循环了！");
16                     }
17 
18                     results.Insert(0, _vertexs[successor].Value);
19 
20                     this.RemoveVertex(successor);
21                     _vertexCount--;
22                 }
23 
24                 _vertexs = cloneVertexs;
25                 _edges = cloneEdges;
26                 _vertexCount = cloneVertexCount;
27 
28                 return results;
29             }
30 
31             private int NextSuccessor()
32             {
33                 for (var row = 0; row < _vertexCount; row++)
34                 {
35                     if (_edges[row].Take(_vertexCount).All(x => !x))
36                     {
37                         return row;
38                     }
39                 }
40 
41                 return -1;
42             }
43 
44             private void RemoveVertex(int successor)
45             {
46                 for (int i = successor; i < _vertexCount - 1; i++)
47                 {
48                     _vertexs[i] = _vertexs[i + 1];
49                 }
50 
51                 for (int row = successor; row < _vertexCount - 1; row++)
52                 {
53                     for (int column = 0; column < _vertexCount; column++)
54                     {
55                         _edges[row][column] = _edges[row + 1][column];
56                     }
57                 }
58 
59                 for (int column = successor; column < _vertexCount - 1; column++)
60                 {
61                     for (int row = 0; row < _vertexCount; row++)
62                     {
63                         _edges[row][column] = _edges[row][column + 1];
64                     }
65                 }
66             }
67 
68             #endregion

完整代码

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Collections.ObjectModel;
  4 using System.Linq;
  5 using System.Text;
  6 using System.Threading.Tasks;
  7 
  8 namespace DataStuctureStudy.Graphs
  9 {
 10     class GraphTest
 11     {
 12         public static void Test()
 13         {
 14             var graph = new Graph<String>(50);
 15             graph
 16                 .AddVertex("A")
 17                 .AddVertex("B")
 18                 .AddVertex("C")
 19                 .AddVertex("D")
 20                 .AddVertex("E")
 21                 .AddVertex("F")
 22                 .AddVertex("G")
 23                 .AddVertex("H")
 24                 .AddVertex("I");
 25             graph
 26                 .AddDirectedEdge("A", "B").AddDirectedEdge("A", "C").AddDirectedEdge("A", "D").AddDirectedEdge("A", "E")
 27                 .AddDirectedEdge("B", "F")
 28                 .AddDirectedEdge("D", "G")
 29                 .AddDirectedEdge("F", "H")
 30                 .AddDirectedEdge("G", "I");
 31 
 32             Console.WriteLine("深度遍历，栈版本：");
 33             graph.DepthFirstSearch("A", Console.Write);
 34             Console.WriteLine();
 35             Console.WriteLine();
 36 
 37             Console.WriteLine("深度遍历，递归版本：");
 38             graph.DepthFirstSearchRecursion("A", Console.Write);
 39             Console.WriteLine();
 40             Console.WriteLine();
 41 
 42             Console.WriteLine("广度遍历：");
 43             graph.BreadthFirstSearch("A", Console.Write);
 44             Console.WriteLine();
 45             Console.WriteLine();
 46 
 47             Console.WriteLine("最小生成树：");
 48             graph.DisplayMinimumSpanningTree("A");
 49             Console.WriteLine();
 50             Console.WriteLine();
 51 
 52             Console.WriteLine("拓扑排序：");
 53             var results = graph.TopologySort();
 54             Console.WriteLine(String.Join("->", results.ToArray()));
 55             Console.WriteLine();
 56         }
 57 
 58         class Vertex<T>
 59         {
 60             public T Value { get; set; }
 61 
 62             public bool WasVisited { get; set; }
 63         }
 64 
 65         class Graph<T>
 66         {
 67             #region 私有字段
 68 
 69             private int _maxSize;
 70             private Vertex<T>[] _vertexs;
 71             private bool[][] _edges;
 72             private int _vertexCount = 0;
 73 
 74             #endregion
 75 
 76             #region 构造方法
 77 
 78             public Graph(int maxSize)
 79             {
 80                 _maxSize = maxSize;
 81                 _vertexs = new Vertex<T>[_maxSize];
 82                 _edges = new bool[_maxSize][];
 83                 for (var i = 0; i < _maxSize; i++)
 84                 {
 85                     _edges[i] = new bool[_maxSize];
 86                 }
 87             }
 88 
 89             #endregion
 90 
 91             #region 添加顶点
 92 
 93             public Graph<T> AddVertex(T value)
 94             {
 95                 _vertexs[_vertexCount++] = new Vertex<T> { Value = value };
 96 
 97                 return this;
 98             }
 99 
100             #endregion
101 
102             #region 添加边
103 
104             public Graph<T> AddUnDirectedEdge(T startItem, T endItem)
105             {
106                 var startIndex = this.GetVertexIndex(startItem);
107                 var endIndex = this.GetVertexIndex(endItem);
108 
109                 _edges[startIndex][endIndex] = true;
110                 _edges[endIndex][startIndex] = true;
111 
112                 return this;
113             }
114 
115             public Graph<T> AddDirectedEdge(T startItem, T endItem)
116             {
117                 var startIndex = this.GetVertexIndex(startItem);
118                 var endIndex = this.GetVertexIndex(endItem);
119 
120                 _edges[startIndex][endIndex] = true;
121 
122                 return this;
123             }
124 
125             #endregion
126 
127             #region 深度优先遍历：栈版本
128 
129             public void DepthFirstSearch(T startItem, Action<T> action)
130             {
131                 var startIndex = this.GetVertexIndex(startItem);
132                 var stack = new Stack<int>();
133 
134                 this.DepthFirstSearchVisit(stack, startIndex, action);
135                 while (stack.Count > 0)
136                 {
137                     var adjoinVertexIndex = this.GetNextUnVisitedAdjoinVertexIndex(stack.Peek());
138                     if (adjoinVertexIndex >= 0)
139                     {
140                         this.DepthFirstSearchVisit(stack, adjoinVertexIndex, action);
141                     }
142                     else
143                     {
144                         stack.Pop();
145                     }
146                 }
147 
148                 this.ResetVisited();
149             }
150 
151             private void DepthFirstSearchVisit(Stack<int> stack, int index, Action<T> action)
152             {
153                 _vertexs[index].WasVisited = true;
154                 action(_vertexs[index].Value);
155                 stack.Push(index);
156             }
157 
158             #endregion
159 
160             #region 深度优先遍历：递归版本
161 
162             public void DepthFirstSearchRecursion(T startItem, Action<T> action)
163             {
164                 var startIndex = this.GetVertexIndex(startItem);
165 
166                 this.DepthFirstSearchRecursionVisit(startIndex, action);
167 
168                 this.ResetVisited();
169             }
170 
171             private void DepthFirstSearchRecursionVisit(int index, Action<T> action)
172             {
173                 _vertexs[index].WasVisited = true;
174                 action(_vertexs[index].Value);
175 
176                 var adjoinVertexIndex = this.GetNextUnVisitedAdjoinVertexIndex(index);
177                 while (adjoinVertexIndex >= 0)
178                 {
179                     this.DepthFirstSearchRecursionVisit(adjoinVertexIndex, action);
180                     adjoinVertexIndex = this.GetNextUnVisitedAdjoinVertexIndex(index);
181                 }
182             }
183 
184             #endregion
185 
186             #region 广度优先遍历
187 
188             public void BreadthFirstSearch(T startItem, Action<T> action)
189             {
190                 var startIndex = this.GetVertexIndex(startItem);
191                 var queue = new Queue<int>();
192 
193                 this.BreadthFirstSearchVisit(queue, startIndex, action);
194                 while (queue.Count > 0)
195                 {
196                     var adjoinVertexIndexs = this.GetNextUnVisitedAdjoinVertexIndexs(queue.Dequeue());
197                     foreach (var adjoinVertexIndex in adjoinVertexIndexs)
198                     {
199                         this.BreadthFirstSearchVisit(queue, adjoinVertexIndex, action);
200                     }
201                 }
202 
203                 this.ResetVisited();
204             }
205 
206             private void BreadthFirstSearchVisit(Queue<int> queue, int index, Action<T> action)
207             {
208                 _vertexs[index].WasVisited = true;
209                 action(_vertexs[index].Value);
210                 queue.Enqueue(index);
211             }
212 
213             #endregion
214 
215             #region 最小生成树
216 
217             public void DisplayMinimumSpanningTree(T startItem)
218             {
219                 var startIndex = this.GetVertexIndex(startItem);
220                 var queue = new Queue<int>();
221 
222                 _vertexs[startIndex].WasVisited = true;
223                 queue.Enqueue(startIndex);
224                 while (queue.Count > 0)
225                 {
226                     var currentIndex = queue.Dequeue();
227                     var adjoinVertexIndexs = this.GetNextUnVisitedAdjoinVertexIndexs(currentIndex);
228                     foreach (var adjoinVertexIndex in adjoinVertexIndexs)
229                     {
230                         Console.WriteLine(_vertexs[currentIndex].Value + "->" + _vertexs[adjoinVertexIndex].Value);
231 
232                         _vertexs[adjoinVertexIndex].WasVisited = true;
233                         queue.Enqueue(adjoinVertexIndex);
234                     }
235                 }
236 
237                 this.ResetVisited();
238             }
239 
240             #endregion
241 
242             #region 拓扑排序
243 
244             public List<T> TopologySort()
245             {
246                 var cloneVertexs = (Vertex<T>[])_vertexs.Clone();
247                 var cloneEdges = (bool[][])_edges.Clone();
248                 var cloneVertexCount = _vertexCount;
249 
250                 var results = new List<T>();
251                 while (_vertexCount > 0)
252                 {
253                     var successor = this.NextSuccessor();
254                     if (successor == -1)
255                     {
256                         throw new InvalidOperationException("出现循环了！");
257                     }
258 
259                     results.Insert(0, _vertexs[successor].Value);
260 
261                     this.RemoveVertex(successor);
262                     _vertexCount--;
263                 }
264 
265                 _vertexs = cloneVertexs;
266                 _edges = cloneEdges;
267                 _vertexCount = cloneVertexCount;
268 
269                 return results;
270             }
271 
272             private int NextSuccessor()
273             {
274                 for (var row = 0; row < _vertexCount; row++)
275                 {
276                     if (_edges[row].Take(_vertexCount).All(x => !x))
277                     {
278                         return row;
279                     }
280                 }
281 
282                 return -1;
283             }
284 
285             private void RemoveVertex(int successor)
286             {
287                 for (int i = successor; i < _vertexCount - 1; i++)
288                 {
289                     _vertexs[i] = _vertexs[i + 1];
290                 }
291 
292                 for (int row = successor; row < _vertexCount - 1; row++)
293                 {
294                     for (int column = 0; column < _vertexCount; column++)
295                     {
296                         _edges[row][column] = _edges[row + 1][column];
297                     }
298                 }
299 
300                 for (int column = successor; column < _vertexCount - 1; column++)
301                 {
302                     for (int row = 0; row < _vertexCount; row++)
303                     {
304                         _edges[row][column] = _edges[row][column + 1];
305                     }
306                 }
307             }
308 
309             #endregion
310 
311             #region 帮助方法
312 
313             private int GetVertexIndex(T item)
314             {
315                 for (var i = 0; i < _vertexCount; i++)
316                 {
317                     if (_vertexs[i].Value.Equals(item))
318                     {
319                         return i;
320                     }
321                 }
322                 return -1;
323             }
324 
325             private int GetNextUnVisitedAdjoinVertexIndex(int index)
326             {
327                 for (var i = 0; i < _vertexCount; i++)
328                 {
329                     if (_edges[index][i] && _vertexs[i].WasVisited == false)
330                     {
331                         return i;
332                     }
333                 }
334 
335                 return -1;
336             }
337 
338             private List<int> GetNextUnVisitedAdjoinVertexIndexs(int index)
339             {
340                 var results = new List<int>();
341 
342                 for (var i = 0; i < _vertexCount; i++)
343                 {
344                     if (_edges[index][i] && _vertexs[i].WasVisited == false)
345                     {
346                         results.Add(i);
347                     }
348                 }
349 
350                 return results;
351             }
352 
353             private void ResetVisited()
354             {
355                 for (var i = 0; i < _vertexCount; i++)
356                 {
357                     _vertexs[i].WasVisited = false;
358                 }
359             }
360 
361             #endregion
362         }
363     }
364 }
View Code

备注

本文没有解释权重图，下篇再介绍。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/happyframework/p/3493606.html