首页 > 代码库 > Graph Theory Algorithms
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; // 要添加的边存在，边数减1109 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没有邻接点，则返回-1116 **/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 else141 return tempVertex; // 返回邻接顶点142 }143 144 145 /***************************** 图的邻接表表示表示 ***********************************/146 // 结点抽象类型定义147 struct GraphNode148 {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 Graph158 {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; // 初始化边数为0173 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; // 置顶点数为0197 graph.EdgeCount = 0; // 置边数为0198 }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，否则返回false217 **/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 else225 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没有邻接点，则返回-1274 **/275 int FirstAdjoinVertex(Graph &graph, int vertex)276 {277 GraphLink link = graph.adjoinMatrix[vertex]->next; // 取链表头278 if(link)279 return link->vertex; // 返回第一个邻接顶点280 else281 return -1; // 没有邻接顶点，则返回-1282 }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 else294 link = link->next; // 指向下一个邻接顶点295 }296 return -1; // 未找到，返回-1297 }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, ¤tVertex); // 队列元素出队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]; // 源点的邻接顶点入度减1397 if(inDegrees[tempVertex] == 0)398 EnQueue(circleQueue, tempVertex); // 若成为新源点，入源点队列399 }400 }401 DetroyQueue(circleQueue);402 }
Ok哒，哈哈~
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。