Graph Theory Algorithms

  1 /**
  2  * 图论
  3  **/
  4 
  5  /***************************** 图的抽象数据类型 ************************************/
  6 ADT Graph
  7 {
  8     数据：
  9     Graph = (Vertex, Edge)是可以用不同方式存储的图，Vertex是顶点集，
 10     Edge = {<vertex_1, vertex_2> | vertex_1, vertex_2属于Vertex，vertex_1不等于vertex_2，<vertex_1, vertex_2>表示连接vertex_1和vertext_2的边}
 11 
 12     操作：
 13     void InitGraph(Graph &graph, int vertextCount, bool directed);// 按顶点个数vertexCount和有向标志directed构造图graph
 14     void DestroyGraph(Graph &graph);                                     // 清楚原有的图graph
 15     bool IsDirected(Graph &graph);                                       // 判断图graph是否是有向图
 16     int  VertexCount(Graph &graph);                                      // 求出并返回图graph的顶点数
 17     int  EdgeCount(Graph &graph);                                        // 求出并返回图graph的边数
 18     int  FirstAdjoinVertex(Graph &graph, Vertex vertex);          // 返回vertex的第一个邻接顶点，若vertex没有邻接点，则返回-1
 19     int  NextAdjoinVertex(Graph &graph, Vertex vertex_1, Vertex vertex_2);  // 返回vertex_1的下一个邻接点(相对于vertex_2)
 20     void Insert(Graph &graph, Vertex vertex_1, Vertex vertex_2);            // 在图中插入边<vertex_1, vertex_2>
 21     void Delete(Graph &graph, Vertex vertex_1, Vertex vertex_2);            // 在图中删除边<vertex_1, vertex_2>
 22     bool EdgeExisting(Graph &graph, Vertex vertex_1, Vertex vertex_2);   // 判断边<vertex_1, vertex_2>是否是图graph的边，                                                                                       若是，返回true，否则返回false
 23     void Traverse(Graph &graph, Vertex vertex, *Visit());// 从顶点vertex开始遍历graph,对每个顶点调用函数Visit(),Visit()因遍历方法而异
 24 }    
 25 
 26 struct Graph
 27 {
 28     int  vertextCount;             // 图的顶点数
 29     int  EdgeCount;                // 图的边数
 30     bool directed;                 // 有向图和无向图的标志
 31     bool *adjoinMatrix;            // 指向邻接矩阵的指针
 32     bool *visited;                 // 顶点是否被访问过的标志
 33 };
 34 
 35 /****************************** 图的邻接矩阵表示 ***********************************/
 36 /**
 37  * 下面表示的是无权图的基本操作的实现（带权图的操作实现类似）
 38  **/
 39 /**
 40  *    图的初始化操作
 41  **/
 42 void InitGraph(Graph &graph, int vertextCount, bool directed)
 43 {
 44     graph.vertextCount = vertextCount;                                // 初始化顶点数
 45     graph.EdgeCount = 0;                                              // 初始化边数为0
 46     graph.directed = directed;                                        // 设置有向图和无向图的标志
 47     graph.adjoinMatrix = new bool[vertextCount * vertextCount];       // 为邻接矩阵分配内存空间
 48     graph.visited = new bool[vertextCount];                           // 为顶点访问标志数组分配内存空间
 49     for(int out = 0; out < vertextCount; ++out) {        
 50         for(int in = 0; in < vertextCount; ++in)
 51             graph.adjoinMatrix[out * vertextCount + in] = false;      // 初始化邻接矩阵
 52         graph.visited[out] = false;                                   // 初始化顶点访问标志
 53     }
 54 }
 55 
 56 /**
 57  * 清除图的操作
 58  **/
 59 void DestroyGraph(Graph &graph)
 60 {
 61     delete [] graph.adjoinMatrix;        // 清除图的标志
 62     delete [] graph.visited;             // 清除标志数组
 63     graph.vertextCount = 0;              // 置顶点数为0
 64     graph.EdgeCount = 0;                 // 置边数为0
 65 }
 66 
 67 /**
 68  * 图graph的顶点数统计
 69  **/
 70 int  VertexCount(Graph &graph) { return graph.vertextCount; }
 71 
 72 /**
 73  * 图graph的边数统计
 74  **/
 75 int  EdgeCount(Graph &graph) { return graph.EdgeCount; }
 76 
 77 /**
 78  * 判断图graph是否是有向图
 79  **/
 80 bool IsDirected(Graph &graph) { return graph.directed; }
 81 
 82 /**
 83  * 判断边<vertex_1, vertex_2>是否是图graph的边，若是，返回true，否则返回false
 84  **/
 85 bool EdgeExisting(Graph &graph, Vertex vertex_1, Vertex vertex_2)
 86 {
 87     return graph.adjoinMatrix[vertex_1 * graph.vertextCount + vertex_2];
 88 }
 89 
 90 /**
 91  * 在图中插入边<vertex_1, vertex_2>
 92  **/
 93 void Insert(Graph &graph, Vertex vertex_1, Vertex vertex_2)
 94 {
 95     if(graph.adjoinMatrix[vertex_1 * graph.vertextCount + vertex_2] == false)
 96         ++graph.EdgeCount;                                                              // 要添加的边不存在，边数加1
 97     graph.adjoinMatrix[vertex_1 * graph.vertextCount + vertex_2] = true;                // 添加边<vertex_1, vertex_2>
 98     if(!graph.directed)
 99         graph.adjoinMatrix[vertex_2 * graph.vertextCount + vertex_1] = true;            // 如果是无向图，处理对称元素
100 }
101 
102 /**
103  * 在图中删除边<vertex_1, vertex_2>
104  **/
105 void Delete(Graph &graph, Vertex vertex_1, Vertex vertex_2)
106 {
107     if(graph.adjoinMatrix[vertex_1 * graph.vertextCount + vertex_2] == true)
108         --graph.vertextCount;                                                            // 要添加的边存在，边数减1
109     graph.adjoinMatrix[vertex_1 * graph.vertextCount + vertex_2] = false;                // 删除边<vertex_1, vertex_2>
110     if(!graph.directed)
111         graph.adjoinMatrix[vertex_2 * graph.vertextCount + vertex_1] = false;            // 如果是无向图，处理对称元素
112 }
113 
114 /**
115  * 返回vertex的第一个邻接顶点，若vertex没有邻接点，则返回-1
116  **/
117 int  FirstAdjoinVertex(Graph &graph, Vertex vertex)
118 {
119     int tempVertex = 0;
120     while((tempVertex < graph.vertextCount) && (graph.adjoinMatrix[vertex * graph.vertextCount + tempVertex] == false)) {
121         ++tempVertex;
122     }
123     if(tempVertex == graph.vertextCount)
124         return -1;                                // 未找到邻接顶点
125     else 
126         return tempVertex;                        // 返回邻接顶点
127 }    
128 
129 /**
130  * 返回vertex_1的下一个邻接点(相对于vertex_2)
131  **/
132 int  NextAdjoinVertex(Graph &graph, Vertex vertex_1, Vertex vertex_2)
133 {
134     int tempVertex = vertex_2 + 1;
135     while((tempVertex < graph.vertextCount) && (graph.adjoinMatrix[vertex * graph.vertextCount + tempVertex] == false)) {
136         ++tempVertex;
137     }
138     if(tempVertex == graph.vertextCount)
139         return -1;                                // 未找到邻接顶点
140     else
141         return tempVertex;                        // 返回邻接顶点
142 }
143 
144 
145 /***************************** 图的邻接表表示表示 ***********************************/
146 // 结点抽象类型定义
147 struct GraphNode
148 {
149     int vertex;                                                                            // 顶点
150     GraphNode *next;                                                                       // 指向边的终端结点的指针
151     GraphNode(int tempVertex, GraphNode *pointer) { vertex = tempVertex; next = pointer; } // 构造函数
152 };
153 
154 typedef GraphNode *GraphLink;
155 
156 // 邻接表的结构声明
157 struct Graph
158 {
159     int  vertextCount;                // 图的顶点数
160     int  edgeCount;                   // 图的边数
161     bool directed;                    // 有向图/无向图的标志
162     bool *visited;                    // 顶点是否被访问过的标志
163     GraphLink adjoinMatrix;           // 单链表的表头定义
164 };
165 
166 /**
167  *    图的初始化操作
168  **/
169 void InitGraph(Graph &graph, int vertextCount, bool directed)
170 {
171     graph.vertextCount = vertextCount;                           // 初始化顶点数
172     graph.EdgeCount = 0;                                         // 初始化边数为0
173     graph.directed = directed;                                   // 设置有向图和无向图的标志
174     graph.adjoinMatrix = new GraphLink[vertextCount];            // 为邻接矩阵分配内存空间
175     graph.visited = new bool[vertextCount];                      // 为顶点访问标志数组分配内存空间
176     for(int index = 0; index < vertextCount; ++index) {        
177         graph.adjoinMatrix[index] = new GraphNode(index, NULL);  // 初始化单链表表头，结点值为index，指针域为空
178         graph.visited[index] = false;                            // 初始化顶点访问标志
179     }
180 }
181 
182 /**
183  * 清除图的操作
184  **/
185 void DestroyGraph(Graph &graph)
186 {
187     for(int index = 0; index < graph.vertextCount; ++index) {     // 一次销毁各单链表
188         GraphLink link = graph.adjoinMatrix[index];
189         while(link) {
190             GraphLink tempLink = link;
191             link = link->next;
192             delete tempLink;
193         }
194     }
195     delete [] graph.visited;            // 清除标志数组
196     graph.vertextCount = 0;             // 置顶点数为0
197     graph.EdgeCount = 0;                // 置边数为0
198 }
199 
200 /**
201  * 图graph的顶点数统计
202  **/
203 int  VertexCount(Graph &graph) { return graph.vertextCount; }
204 
205 /**
206  * 图graph的边数统计
207  **/
208 int  EdgeCount(Graph &graph) { return graph.EdgeCount; }
209 
210 /**
211  * 判断图graph是否是有向图
212  **/
213 bool IsDirected(Graph &graph) { return graph.directed; }
214 
215 /**
216  * 判断边<vertex_1, vertex_2>是否是图graph的边，若是，返回true，否则返回false
217  **/
218 bool EdgeExisting(Graph &graph, Vertex vertex_1, Vertex vertex_2)
219 {
220     GraphLink link = graph.adjoinMatrix[vertex_1]->next;            // 根据起始点确定链表
221     while(link) {
222         if(link->vertex == vertex_2)                                // 边存在
223             return true;
224         else
225             link = link->next;                                      // 寻找下一条
226     }
227     return false;                                                   // 边不存在
228 }
229 
230 /**
231  * 在图中插入边<vertex_1, vertex_2>
232  **/
233 void Insert(Graph &graph, Vertex vertex_1, Vertex vertex_2)
234 {
235     if(EdgeExisting(graph, vertex_1, vertex_2) == false) {　　　　　　// 没有判断要添加的边是否存在
236         graph.adjoinMatrix[vertex_1]->next = new GraphNode(vertex_2, graph.adjoinMatrix[vertex_1]->next); 
237         if(!graph.directed)
238             graph.adjoinMatrix[vertex_2]->next = new GraphNode(vertex_1, graph.adjoinMatrix[vertex_2]->next); // 若是无向图
239         ++graph.EdgeCount;    　　　　　　　　　　　　　　　　　　　　　　　// 边数加1    
240     }                                                                               
241 }
242 
243 /**
244  * 在图中删除边<vertex_1, vertex_2>
245  **/
246 void Delete(Graph &graph, Vertex vertex_1, Vertex vertex_2)
247 {
248     GraphLink link = graph.adjoinMatrix[vertex_1];                // 取链表头
249     while(link->next) {                                           // 寻找待删除的边
250         if(vertex_2 == link->next->vertex) {                      // 找到要删除的边，执行删除操作
251             GraphLink tempLink = link->next;
252             link->next = tempLink->next;
253             delete tempLink;
254             break;
255         }
256         link = link->next;                                        // 指向下一个邻接顶点
257     }
258     if(graph.directed == true)                                    // 如果是有向图，则返回
259         return ;
260     link = graph.adjoinMatrix[vertex_2];                          // 去链表头
261     while(link->next) {                                           // 寻找待删除的边
262         if(vertex_1 == link->next->vertex) {                      // 找到要删除的边，执行删除操作
263             GraphLink tempLink = link->next;
264             link->next = tempLink->next;
265             delete tempLink;
266             break;
267         }
268         link = link->next;                                        // 指向下一个邻接顶点
269     }
270 }
271 
272 /**
273  * 返回vertex的第一个邻接顶点，若vertex没有邻接点，则返回-1
274  **/
275 int FirstAdjoinVertex(Graph &graph, int vertex)
276 {
277     GraphLink link = graph.adjoinMatrix[vertex]->next;            // 取链表头
278     if(link)
279         return link->vertex;                                      // 返回第一个邻接顶点
280     else
281         return -1;                                                // 没有邻接顶点，则返回-1
282 }
283 
284 /**
285  * 返回vertex_1的下一个邻接点(相对于vertex_2)
286  **/
287 int  NextAdjoinVertex(Graph &graph, Vertex vertex_1, Vertex vertex_2)
288 {
289     GraphLink link = graph.adjoinMatrix[vertex_1]->next;          // 取链表头
290     while(link) {
291         if(link->vertex == vertex_2 && link->next != NULL)        // 判断当前邻接顶点
292             return link->next->vertext;                           // 返回下一个邻接顶点
293         else
294             link = link->next;                                    // 指向下一个邻接顶点
295     }
296     return -1;                                                    // 未找到，返回-1
297 }
298 
299 /**
300  * 图的深度优先遍历
301  **/
302 void DepthFirstTraverse(Graph &graph, int vertex) 
303 {
304     graph.visited[vertex] = true;                                                    // 置访问标志
305     for(int tempVertex = FirstAdjoinVertex(graph); tempVertex != -1; ++tempVertex) { // 依次访问顶点vertex的邻接顶点
306         if(graph.visited[tempVertex] == false)                                       // 若顶点未访问，则递归调用
307             DepthFirstTraverse(graph, tempVertex);
308     }
309 }
310 
311 /**
312  * 图的广度优先遍历
313  **/
314 void BreadthFirstSearch(Graph &graph, Vertex vertex)
315 {
316     CircleQueue circleQueue;                                    // 定义循环队列
317     InitQueue(circleQueue);                                     // 初始化循环队列
318     if(graph.visited[vertex] == false)                          // 是否没有访问过
319         graph.visited[vertex] = true;                           // 置访问标志，可插入顶点访问操作
320     EnQueue(circleQueue, vertex);                               // 顶点入队列
321     while(!IsEmpty(circleQueue)) {                              /* 循环直到队列为空 */
322         Vertex currentVertex;
323         DeQueue(circleQueue, &currentVertex);                   // 队列元素出队
324         for(Vertex tempVertex = FirstAdjoinVertex(graph, currentVertex); tempVertex != -1; tempVertex = NextAdjoinVertex(graph, currentVertex, tempVertex)) {
325             if(graph.visited[tempVertex] == false) {            // 是否没有访问过
326                 graph.visited[tempVertex] = true;               // 置访问标志
327                 EnQueue(circleQueue, tempVertex);               // 刚访问过的顶点元素入队
328             }
329         }
330     }
331     DestroyGraph(circleQueue);
332 }
333 
334 /**
335  * 寻找图中从顶点vertex_1到顶点vertex_2的简单路径
336  * 基本思路：
337  *         对依附于顶点vertex_1的每条边<vertex_1, temp_1>，寻找从顶点temp_1到顶点vertex_2的一条简单路径，而且不经过vertex_1，
338  *        考虑依附于顶点temp_1的边<temp_1, temp_2>，寻找从顶点temp_2到顶点vertex_2的一条简单路径，并且不经过顶点vertex_1和
339  *        顶点temp_1，如此下去，直到找到解为止，所以这个问题可以利用深度优先遍历实现。
340  *        从顶点vertex_1出发做深度优先遍历，如果遇到顶点vertex_2，回溯就可以得到从顶点vertex_1到顶点vertex_2的一条路径。那
341  *        如何保证这是一条简单路径，方法是：维护一条路径，依次记录深度优先遍历过程中访问过的顶点；在深度优先遍历过程中，如果
342  *        顶点的所有邻接顶点都被访问过，仍然未能到达目标顶点vertex_2，则将此顶点从路径中删除；到达目标顶点后，就可以得到一条简单路径
343  **/
344 void SimplePath(Graph &graph, Vertex vertex_1, Vertex vertex_2)
345 {
346     graph.visited[vertex_1] = true;                                        // 设置访问标志
347     Append(path, vertex_1);                                                // 将当前顶点加入路径
348     for(Vertex tempVertex = FirstAdjoinVertex(graph, vertex_1); tempVertex != -1; tempVertex = NextAdjoinVertex(graph, vertex_1, tempVertex)) {
349         if(tempVertex == vertex_2) {                                       // 查找成功
350             Append(path, vertex_2);
351             return ;
352         }
353         if(!graph.visited(tempVertex))                                     // 递归调用
354             SimplePath(graph, tempVertex, vertex_2);
355     }
356     Delete(path, vertex_1);                                                // 删除路径上最后一个顶点
357 }
358 
359 /**
360  * 非连通图的遍历
361  **/
362 void DepthFirstTraverse(Graph &graph, Vertex vertext)
363 {
364     for(vertext = 0; vertext < graph.vertextCount; ++vertext) {     // 只需把每个顶点作为起点进行深度优先遍历即可
365         graph.visited[vertext] = true;
366         for(int temp = FirstAdjoinVertex(graph, vertext); temp != -1; tmep = NextAdjoinVertex(graph, vertext, temp)) {
367             if(graph.visited[temp] == false)
368                 DepthFirstTraverse(graph, temp);
369         }
370     }
371 }
372 
373 /**
374  * 拓扑排序
375  **/
376 void TopologicalSort(Graph &graph, int *topologicalSequence)
377 {
378     CircleQueue circleQueue;
379     InitQueue(circleQueue);
380     int *inDegrees = new int[graph.vertextCount];                        // 记录每个顶点的入度
381     for(int vertex = 0; vertex < graph.vertextCount; ++vertex)           // 初始化顶点入度
382         inDegrees[vertex] = 0;    
383     for(int vertex = 0; vertex < graph.vertextCount; ++vertex) {         // 遍历图得到顶点输入边数
384         for(int tempVertex = FirstAdjoinVertex(graph, vertext); tempVertex != -1; tempVertex = NextAdjoinVertex(graph, vertex, tempVertex)) {
385             ++inDegrees[tempVertex];
386         }
387     }
388     for(int vertex = 0; vertex < graph.vertextCount; ++vertex)
389         if(inDegrees[vertex] == 0)
390             EnQueue(circleQueue, vertex);                                // 源点入源点队列
391     for(int index = 0; !IsEmpty(circleQueue); ++index) {                 // 开始拓扑排序
392         int outVertex;
393         DeQueue(circleQueue, &outVertex);
394         topologicalSequence[index] = outVertex;                          // 从源点队列中取元素如拓扑队列
395         for(int tempVertex = FirstAdjoinVertex(graph, outVertex); tempVertex != -1; tempVertex = NextAdjoinVertex(graph, outVertex, tempVertex)) {
396             --inDegrees[tempVertex];                                     // 源点的邻接顶点入度减1
397             if(inDegrees[tempVertex] == 0)
398                 EnQueue(circleQueue, tempVertex);                        // 若成为新源点，入源点队列
399         }
400     }
401     DetroyQueue(circleQueue);
402 }