本文主要是介绍图（有向图）的邻接表表示 C++实现(遍历，拓扑排序，最短路径，最小生成树) Implement of digraph and undigraph using adjacency list，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文实现了有向图的邻接表表示，并且实现了从创建到销毁图的各种操作。
以及深度优先遍历，广度优先遍历，Dijkstra最短路径算法，Prim最小生成树算法，拓扑排序算法。
可结合我的另一篇文章（有向图，无向图的邻接矩阵表示）看。
PS: 等有时间了作详细的讲解。
#include <iostream>
#include <climits>
#include <sstream>
#include <queue>
using namespace std;//const bool UNDIGRAPH = 1;struct EdgeNode//edge,the node of linked list
{ int vtxNO; int weight; EdgeNode *next;
}; struct VNode//vertex, the head of the linked list
{ string vertexLabel; EdgeNode *first; bool visited;//only for DFS,BFS,Dijkstraint distance; //only for Dijkstraint path;//only for Dijkstraint indegree; //only for topological sort
}; struct Graph
{ VNode *vertexList;//the size of this array is equal to vertexes int vertexes; int edges;
}; void BuildGraph(Graph *&graph, int n)
{if (graph == NULL){graph = new Graph;graph->vertexList = new VNode[n];graph->vertexes = n;graph->edges = 0;for (int i = 0; i < n; i++) { stringstream ss; ss<<"v" << i+1; ss >> graph->vertexList[i].vertexLabel; graph->vertexList[i].path = -1;graph->vertexList[i].visited = false;graph->vertexList[i].first = NULL;graph->vertexList[i].indegree = 0;}}
}void MakeEmpty(Graph *&graph)
{if(graph == NULL)return;for (int i = 0; i < graph->vertexes; i++) { EdgeNode *pEdge = graph->vertexList[i].first; while (pEdge!=NULL) { EdgeNode *tmp = pEdge; pEdge = pEdge->next; delete tmp; } } delete graph;
}void AddEdge(Graph *graph,int v1, int v2, int weight)
{if (graph == NULL) return;if (v1 < 0 || v1 > graph->vertexes-1) return;if (v2 < 0 || v2 > graph->vertexes-1) return;if (v1 == v2) return; //no loop is allowedEdgeNode *p = graph->vertexList[v1].first; if(p == NULL) { //can not be p = new EdgeNode; graph->vertexList[v1].first = new EdgeNode; graph->vertexList[v1].first->next = NULL; graph->vertexList[v1].first->vtxNO = v2; graph->vertexList[v1].first->weight = weight; graph->edges++;graph->vertexList[v2].indegree++;return;} while (p->next != NULL)//move to the last node { if(p->vtxNO == v2)//already exits. checking all nodes but the last one return; p = p->next; } if(p->vtxNO == v2)//already exits. checking the first or the last node return; EdgeNode *node = new EdgeNode; node->next = NULL; node->vtxNO = v2; node->weight = weight; p->next = node;//last node's next is the new node graph->edges++; graph->vertexList[v2].indegree++;
}void RemoveEdge(Graph *graph, int v1, int v2)
{if (graph == NULL) return;if (v1 < 0 || v1 > graph->vertexes-1) return;if (v2 < 0 || v2 > graph->vertexes-1) return;if (v1 == v2) return; //no loop is allowedEdgeNode *p = graph->vertexList[v1].first; if(p == NULL)//not found return; if(p->vtxNO == v2)//found,delete the first node { EdgeNode *tmp = p;//first graph->vertexList[v1].first = p->next; //can not be p = p->next delete tmp; graph->edges--; graph->vertexList[v2].indegree--;return; } while(p->next != NULL) { if(p->next->vtxNO == v2)//found { EdgeNode *tmp = p->next; p = p->next->next; delete tmp; graph->edges--; graph->vertexList[v2].indegree--;return; } p = p->next; }
}int GetIndegree(Graph *graph, int v)
{if(graph == NULL) return -1;if(v < 0 || v > graph->vertexes -1) return -2;int degree = 0; for (int i = 0; i < graph->vertexes; i++) { EdgeNode *p = graph->vertexList[i].first; while (p != NULL) { if(p->vtxNO == v) { degree++; break; } p = p->next; } } return degree;
}int GetOutdegree(Graph *graph, int v)
{if(graph == NULL) return -1;if(v < 0 || v > graph->vertexes -1) return -2;int degree = 0; EdgeNode *p = graph->vertexList[v].first; while(p != NULL) { p = p->next; degree++; } return degree;
}int GetDegree(Graph *graph, int v)
{if(graph == NULL) return -1;if(v < 0 || v > graph->vertexes -1) return -2;return GetIndegree(graph,v) + GetOutdegree(graph,v);
}void PrintGraph(Graph *graph)
{if(graph == NULL)return;cout << "Vertex: " << graph->vertexes <<"\n";cout << "Edge: " << graph->edges << "\n";for (int i = 0; i < graph->vertexes; i++) { cout << i+1 << ": " << graph->vertexList[i].vertexLabel<<"->"; EdgeNode *p = graph->vertexList[i].first; while (p != NULL) { cout << graph->vertexList[p->vtxNO].vertexLabel << "(" << p->weight <<")->"; p = p->next; } cout << "\n"; } cout << "\n";
}//depth first search (use stack or recursion)
//DFS is similar to preorder traversal of trees
void DFS(Graph *graph, int i)
{if (!graph->vertexList[i].visited){cout << graph->vertexList[i].vertexLabel << " ";graph->vertexList[i].visited = true;}EdgeNode *p = graph->vertexList[i].first;while (p != NULL){if(!graph->vertexList[p->vtxNO].visited)//notice!DFS(graph, p->vtxNO);p = p->next;}
}void BeginDFS(Graph *graph)
{if(graph == NULL) return;cout << "DFS\n";for (int i = 0; i < graph->vertexes; i++)graph->vertexList[i].visited = false;for (int i = 0; i < graph->vertexes; i++)DFS(graph,i);
}
//breadth first search(use queue)
//BFS is similar to leverorder traversal of trees
//all of the vertexes will be searched once no matter how the digraph is constructed
void BFS(Graph *graph)
{if(graph == NULL)return;cout << "BFS\n";for (int i = 0; i < graph->vertexes; i++)graph->vertexList[i].visited = false;queue<int> QVertex;for (int i = 0; i < graph->vertexes; i++){if (!graph->vertexList[i].visited){QVertex.push(i);cout << graph->vertexList[i].vertexLabel << " ";graph->vertexList[i].visited = true;}while(!QVertex.empty()){int vtxNO = QVertex.front();QVertex.pop();EdgeNode *p = graph->vertexList[vtxNO].first;while(p != NULL){if (!graph->vertexList[p->vtxNO].visited){cout << graph->vertexList[p->vtxNO].vertexLabel << " ";graph->vertexList[p->vtxNO].visited = true;QVertex.push(p->vtxNO);}p = p->next;}}}cout << "\n";
}void TopologicalSort(Graph *graph)
{//if(UNDIGRAPH) return;if(graph == NULL) return;cout << "TopologicalSort"<<"\n";int counter = 0;queue <int> qVertex;for (int i = 0; i < graph->vertexes; i++){if(GetIndegree(graph,i) == 0)qVertex.push(i);}while (!qVertex.empty()){int vtxNO = qVertex.front();counter++;cout << graph->vertexList[vtxNO].vertexLabel;if(counter != graph->vertexes)cout << " > ";qVertex.pop();EdgeNode *p = graph->vertexList[vtxNO].first;while(p != NULL){int vtxNo = p->vtxNO;/*EdgeNode *tmp = p;p = p->next;delete tmp;tmp = NULL;*/// although tmp is NULL,but p is not NULL,and the data pointed by p has been deletedp = p->next;//if (GetIndegree(graph,vtxNo) == 0)//error,in while(p != NULL),so use a variable indegree insteadif (--graph->vertexList[vtxNo].indegree == 0)qVertex.push(vtxNo);}}cout << "\n";
}void Dijkstra(Graph *graph, int v)
{if(graph == NULL) return;if(v < 0 || v > graph->vertexes-1) return;for (int i = 0; i < graph->vertexes; i++){graph->vertexList[i].visited = false;graph->vertexList[i].distance = INT_MAX;//can delete this line,as initialized in BuildGraphgraph->vertexList[i].path = -1;}graph->vertexList[v].distance = 0;//the rest are all INT_MAXwhile(1){int minDisInx = -1;int minDis = INT_MAX;for (int i = 0; i < graph->vertexes; i++){if(!graph->vertexList[i].visited){if(graph->vertexList[i].distance < minDis){minDis = graph->vertexList[i].distance;minDisInx = i;}}}if(minDisInx == -1)//all visitedbreak;graph->vertexList[minDisInx].visited = true;EdgeNode *p = graph->vertexList[minDisInx].first;while(p != NULL){int vtxNO = p->vtxNO;if(!graph->vertexList[vtxNO].visited){if (graph->vertexList[minDisInx].distance + p->weight < graph->vertexList[vtxNO].distance){graph->vertexList[vtxNO].distance = graph->vertexList[minDisInx].distance + p->weight;graph->vertexList[vtxNO].path = minDisInx;cout << graph->vertexList[vtxNO].vertexLabel << " Updated to " << graph->vertexList[vtxNO].distance << "\n";}}p = p->next;}}cout << "Vertex Visited Distance Path\n";for (int i = 0; i < graph->vertexes; i++){cout << graph->vertexList[i].vertexLabel<< " ";cout << graph->vertexList[i].visited<< " ";cout << graph->vertexList[i].distance<< " ";if(graph->vertexList[i].path == -1)cout << "NONE\n";elsecout << graph->vertexList[graph->vertexList[i].path].vertexLabel << "\n";}
}//almost for undigraph
void Prim(Graph *graph, int v)
{if(graph == NULL) return;if(v < 0 || v > graph->vertexes-1) return;for (int i = 0; i < graph->vertexes; i++){graph->vertexList[i].visited = false;graph->vertexList[i].distance = INT_MAX;//can delete this line,as initialized in BuildGraphgraph->vertexList[i].path = -1;}graph->vertexList[v].distance = 0;//the rest are all INT_MAXwhile(1){int minDisInx = -1;int minDis = INT_MAX;for (int i = 0; i < graph->vertexes; i++){if(!graph->vertexList[i].visited){if(graph->vertexList[i].distance < minDis){minDis = graph->vertexList[i].distance;minDisInx = i;}}}if(minDisInx == -1)//all visitedbreak;graph->vertexList[minDisInx].visited = true;EdgeNode *p = graph->vertexList[minDisInx].first;while(p != NULL){int vtxNO = p->vtxNO;if(!graph->vertexList[vtxNO].visited){if (p->weight < graph->vertexList[vtxNO].distance){graph->vertexList[vtxNO].distance = p->weight;graph->vertexList[vtxNO].path = minDisInx;cout << graph->vertexList[vtxNO].vertexLabel << " Updated to " << graph->vertexList[vtxNO].distance << "\n";}}p = p->next;}}cout << "Vertex Visited Distance Path\n";for (int i = 0; i < graph->vertexes; i++){cout << graph->vertexList[i].vertexLabel<< " ";cout << graph->vertexList[i].visited<< " ";cout << graph->vertexList[i].distance<< " ";if(graph->vertexList[i].path == -1)cout << "NONE\n";elsecout << graph->vertexList[graph->vertexList[i].path].vertexLabel << "\n";}}
int main()
{Graph *graph = NULL;BuildGraph(graph,7);PrintGraph(graph);//for simple test, 0 indexed/*AddEdge(graph,0,1,1);AddEdge(graph,0,2,1);AddEdge(graph,1,3,1);*///for TopologicalSort//0 indexedAddEdge(graph,0,1,1);AddEdge(graph,0,2,1);AddEdge(graph,0,3,1);AddEdge(graph,1,3,1);AddEdge(graph,1,4,1);AddEdge(graph,2,5,1);AddEdge(graph,3,2,1);AddEdge(graph,3,5,1);AddEdge(graph,3,6,1);AddEdge(graph,4,3,1);AddEdge(graph,4,6,1);AddEdge(graph,6,5,1);PrintGraph(graph);RemoveEdge(graph,6,5);AddEdge(graph,6,5,1);//for Dijkstra(shortest path),Prim(minimum spanning tree)//0 indexed/*AddEdge(graph,0,1,2); AddEdge(graph,0,3,1); AddEdge(graph,1,3,3); AddEdge(graph,1,4,10); AddEdge(graph,2,0,4); AddEdge(graph,2,5,5); AddEdge(graph,3,2,2);AddEdge(graph,3,4,2);AddEdge(graph,3,5,8); AddEdge(graph,3,6,4); AddEdge(graph,4,6,6); AddEdge(graph,6,5,1);*/PrintGraph(graph);BeginDFS(graph);cout << "\n";BFS(graph);for (int i = 0; i < graph->vertexes; i++){cout << "\n";Dijkstra(graph,i);}Prim(graph,0);TopologicalSort(graph);MakeEmpty(graph);return 0;
}这篇关于图（有向图）的邻接表表示 C++实现(遍历，拓扑排序，最短路径，最小生成树) Implement of digraph and undigraph using adjacency list的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
