整理了一下图的基本算法,包括图的深度优先遍历、广度优先遍历、拓扑排序、三种单源最短路径(Bell-Ford、Dijkstra、有向无回路最短路径算法)、关键路径。
图的存储结构采用的邻接表。
这里贴出算法的关键部分,具体的实现已经上传到我的资源上了。
”graphOperation.cpp“
//图的操作:广度优先遍历、深度优先遍历、拓扑排序、单源最短路径(Bellman-Ford, DAG, Dijkstra)、关键路径 #include "h1.h" #include "QueueDefinition.h" #include "StackDefinition.h" void createGraph(ALGraph *g){ //为了方便,图的顶点名称就用顶点的序号代替 int i, j,vexNum, arcNum; int va, vb, w; ArcNode *arc, *tempArc; printf("请输入图的顶点数,边数: "); scanf("%d%d", &vexNum, &arcNum); g->vexNum = vexNum; g->arcNum = arcNum; for(i=0; i<6; i++){ //初始化顶点 g->vertices[i].data = i; g->vertices[i].firstArc = NULL; } printf("请输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n"); for(j=0; j<arcNum; j++){ scanf("%d%d%d", &w, &va, &vb); arc = (ArcNode*)malloc(sizeof(ArcNode)); arc->weight = w; arc->adjvex = vb; arc->nextArc = NULL; tempArc = g->vertices[va].firstArc;//插入该弧 g->vertices[va].firstArc = arc; arc->nextArc = tempArc; printf("Input next arc:\n"); } } Boolean visited[MAXSIZE]; void visitGraphNode(ALGraph g, int v){ printf(" %d ", g.vertices[v].data); } void BFSTraverse(ALGraph g, SqQueue *Q, int v){//从顶点v开始的广度遍历 int n = g.vexNum; int adjVex; VNode *vNode; ArcNode *arcNode; vNode = (VNode *)malloc(sizeof(VNode)); if(!vNode){ printf("Memory allocation error!\n"); exit(OVERFLOW); } EnQueue(Q, g.vertices[v]); while(QueueLength(*Q) != 0){ DeQueue(Q, vNode); if(!visited[vNode->data]){ visitGraphNode(g, vNode->data); visited[vNode->data] = TRUE; arcNode = vNode->firstArc; while(arcNode){ adjVex = arcNode->adjvex; EnQueue(Q, g.vertices[adjVex]); arcNode = arcNode->nextArc; } } } free(vNode); ClearQueue(Q); } void graphBFSTraverse(ALGraph g, int v){//以顶点v开始的所有顶点的宽度遍历 int n = g.vexNum; int i; SqQueue *Q; Q = (SqQueue *)malloc(sizeof(SqQueue)); if(!Q){ printf("Q initialization error!\n"); exit(OVERFLOW); } InitQueue(Q); for(i=0; i<n; i++){ visited[i] = FALSE; } for(i=v; i<n; i++){ if(!visited[i]){ BFSTraverse(g, Q, i); } } for(i=0; i<v; i++){ if(!visited[i]){ BFSTraverse(g, Q, i); } } DestroyQueue(Q); } void DFSTraverse(ALGraph g, int v){ visited[v] = TRUE; visitGraphNode(g, v); ArcNode *arcNode; arcNode = g.vertices[v].firstArc; while(arcNode){ if(!visited[arcNode->adjvex]){ DFSTraverse(g, arcNode->adjvex); } arcNode = arcNode->nextArc; } } void graphDFSTraverse(ALGraph g, int v){ int i; int n = g.vexNum; for(i=0; i<n; i++){ visited[i] = FALSE; } for(i=v; i<n; i++){ if(!visited[i]){ DFSTraverse(g, i); } } for(i=0; i<v; i++){ if(!visited[i]){ DFSTraverse(g, i); } } } void FindInDegree(ALGraph g, int inDegree[]){ int i; int n = g.vexNum; ArcNode *arcNode; for(i=0; i<n; i++){ inDegree[i] = 0; } for(i=0; i<n; i++){ arcNode = g.vertices[i].firstArc; while(arcNode){ inDegree[arcNode->adjvex]++; arcNode = arcNode->nextArc; } } } Status TopologicalSort(ALGraph g, SqQueue *q){//拓扑排序,将拓扑排序结果保存在队列中 int inDegree[MAXSIZE]; int i, k, n; int count = 0; SqStack *S; ArcNode *arcNode; n = g.vexNum; S = (SqStack*)malloc(sizeof(SqStack)); if(!S){ printf("初始化栈失败!\n"); exit(OVERFLOW); } FindInDegree(g, inDegree); InitStack(S); for(i=0; i<n; i++){ if(inDegree[i] == 0){ Push(S, i); } } while(!StackEmpty(*S)){ Pop(S, &i); EnQueue(q, g.vertices[i]); count++; arcNode = g.vertices[i].firstArc; while(arcNode){ k = --inDegree[arcNode->adjvex]; if(k == 0){ Push(S, arcNode->adjvex); } arcNode = arcNode->nextArc; } } if(count<g.vexNum){ DestroyStack(S); return ERROR; //有回路 } else{ DestroyStack(S); return OK; } } void printPath(int s, int n, int k, int path[][MAXSIZE]){//由于在path中存储的路径是逆序的,为了能正序的打印路径,我们这里使用递归方式打印 k = path[n][k]; if(k != s){ printPath(s, n, k, path); printf(" %d ", k); } } void ShortestPath_BellmanFord(ALGraph g, int s){ //无“负权回路”的带权有向图单源最短路径算法 int n = g.vexNum; int i, j, k, u, v; ArcNode *arcNode; int d[MAXSIZE];//用来描述从源点s到v的最短路径上权值的上界 int path[MAXSIZE][MAXSIZE]; for(i=0; i<n; i++){ d[i] = INFINITY; for(j=0; j<n; j++){ path[i][j] = s; } } d[s] = 0; path[s][s] = s; for(i=0; i<n-1; i++){ //松弛技术 for(u=0; u<n; u++){ arcNode = g.vertices[u].firstArc; while(arcNode){ v = arcNode->adjvex; if(d[v] > d[u]+arcNode->weight){ d[v] = d[u] + arcNode->weight; k = path[u][u]; path[v][u] = k; while(k != s){ path[v][k] = path[u][k]; k = path[u][k]; } path[v][v] = u; } arcNode = arcNode->nextArc; } } } for(i=0; i<n; i++){ //打印最短距离和路径 if(d[i]==INFINITY){ printf("%d->%d:不可达\n", s, i); } else{ printf("%d->%d: %d ", s, i, d[i]); printf("路径为: %d", s); printPath(s, i, i, path); printf(" %d \n", i); } } } //时间复杂度为O(VE) V:顶点数 E:边数 Status ShortestPath_DAG(ALGraph g, int s){ //对于有向无回路的单源最短路径,我们可以用在更低的时间复杂度内完成 int n = g.vexNum; int i, j, k, u, v; ArcNode *arcNode; VNode *vNode; SqQueue *q; vNode = (VNode*)malloc(sizeof(VNode)); if(!vNode){ printf("Allocate memory for vNode error!\n"); exit(OVERFLOW); } q = (SqQueue*)malloc(sizeof(SqQueue)); if(!q){ printf("Allocate memory for queue error!\n"); exit(OVERFLOW); } InitQueue(q); if(!TopologicalSort(g, q)){ printf("ERROR!此图有回路,无法使用此算法求最短路径!\n"); return ERROR; } int d[MAXSIZE];//用来描述从源点s到v的最短路径上权值的上界 int path[MAXSIZE][MAXSIZE]; for(i=0; i<n; i++){ d[i] = INFINITY; for(j=0; j<n; j++){ path[i][j] = s; } } d[s] = 0; path[s][s] = s; while(!QueueEmpty(*q)){ //执行松弛技术;在有向无回路图中,松弛技术只执行了|E|次(即边数的次数,采用的是聚集分析技术) DeQueue(q, vNode); u = vNode->data; arcNode = vNode->firstArc; while(arcNode){ v = arcNode->adjvex; if(d[v] > d[u] + arcNode->weight){ d[v] = d[u] + arcNode->weight; k = path[u][u]; path[v][u] = k; while(k != s){ path[v][k] = path[u][k]; k = path[u][k]; } path[v][v] = u; } arcNode = arcNode->nextArc; } } DestroyQueue(q); free(vNode); for(i=0; i<n; i++){ //打印最短距离和路径 if(d[i]==INFINITY){ printf("%d->%d:不可达\n", s, i); } else{ printf("%d->%d: %d ", s, i, d[i]); printf("路径为: %d", s); printPath(s, i, i, path); printf(" %d \n", i); } } return OK; }//时间复杂度为O(V+E) V:顶点数 E:边数 int minimum(int d[], int n){ int i, k, min; min = INFINITY; for(i=0; i<n; i++){ if(d[i] < min){ min = d[i]; k = i; } } return k; } void ShortestPath_Dijkstra(ALGraph g, int s){ //带“正值”权的图的单源最短路径 int n = g.vexNum; int i, j, k, u, v; Boolean final[MAXSIZE]; ArcNode *arcNode; int d[MAXSIZE];//用来描述从源点s到v的最短路径上权值的上界 int path[MAXSIZE][MAXSIZE]; for(i=0; i<n; i++){ d[i] = INFINITY; final[i] = FALSE; for(j=0; j<n; j++){ path[i][j] = s; } } d[s] = 0; path[s][s] = s; final[s] = TRUE; arcNode = g.vertices[s].firstArc; //找到源点的邻接点 while(arcNode){ v = arcNode->adjvex; d[v] = arcNode->weight; path[v][v] = s; arcNode = arcNode->nextArc; } for(i=0; i<n-1; i++){ u = minimum(d, n);//找到已经获得最短路径的点(贪心性质) final[u] = TRUE; arcNode = g.vertices[u].firstArc; while(arcNode){ //对该结点的邻接点进行松弛操作 v = arcNode->adjvex; if(d[v] > d[u] + arcNode->weight){ d[v] = d[u] + arcNode->weight; k = path[u][u]; path[v][u] = k; while(k != s){ path[v][k] = path[u][k]; k = path[u][k]; } path[v][v] = u; } arcNode = arcNode->nextArc; } } for(i=0; i<n; i++){ //打印最短距离和路径 if(d[i]==INFINITY){ printf("%d->%d:不可达\n", s, i); } else{ printf("%d->%d: %d ", s, i, d[i]); printf("路径为: %d", s); printPath(s, i, i, path); printf(" %d \n", i); } } } Status TopologicalOrder(ALGraph g, SqStack *t, int ve[]){//拓扑排序,并返回逆序,为求关键路径做准备 int inDegree[MAXSIZE]; int i, k, n, u, v; int count = 0; SqStack *S; ArcNode *arcNode; n = g.vexNum; S = (SqStack*)malloc(sizeof(SqStack)); if(!S){ printf("初始化栈失败!\n"); exit(OVERFLOW); } FindInDegree(g, inDegree); InitStack(S); for(i=0; i<n; i++){ if(inDegree[i] == 0){ Push(S, i); } ve[i] = 0; } while(!StackEmpty(*S)){ Pop(S, &u); Push(t, u); count++; arcNode = g.vertices[u].firstArc; while(arcNode){ v = arcNode->adjvex; if(--inDegree[v] == 0){ Push(S, v); } if(ve[v] < ve[u] + arcNode->weight){ //计算每个顶点的最早开始时间 ve[v] = ve[u] + arcNode->weight; } arcNode = arcNode->nextArc; } } if(count<g.vexNum){ DestroyStack(S); return ERROR; //有回路 } else{ DestroyStack(S); return OK; } } Status CriticalPath(ALGraph g){ //求关键路径,即最长路径 int i, k, u, v, n; ArcNode *arcNode; SqStack *t; int ve[MAXSIZE]; //顶点的最早开始时间 int vl[MAXSIZE]; //顶点的最迟开始时间 n = g.vexNum; t = (SqStack*)malloc(sizeof(SqStack)); if(!t){ printf("Allocate memory for stack error!\n"); exit(OVERFLOW); } InitStack(t); if(!TopologicalOrder(g, t, ve)){ printf("ERROR!有回路,无法求得关键路径!\n"); return ERROR; } for(i=0; i<n; i++){ vl[i] = ve[n-1]; } while(!StackEmpty(*t)){ Pop(t, &u); arcNode = g.vertices[u].firstArc; while(arcNode){ v = arcNode->adjvex; if(vl[u] > vl[v] - arcNode->weight){ vl[u] = vl[v] - arcNode->weight; } arcNode = arcNode->nextArc; } } int ee, el; for(u=0; u<n; u++){ arcNode = g.vertices[u].firstArc; while(arcNode){ v = arcNode->adjvex; ee = ve[u]; el = vl[v]- arcNode->weight; if(ee == el){ printf("%d ==> %d\n", u, v); } arcNode = arcNode->nextArc; } } DestroyStack(t); return OK; } int main(){ ALGraph *g; g = (ALGraph*)malloc(sizeof(ALGraph)); if(!g){ printf("Allocate memory for graph error!\n"); exit(OVERFLOW); } createGraph(g); printf("\n\n****************\n"); printf("广度优先遍历结果:\n"); graphBFSTraverse(*g, 0); printf("\n\n****************\n"); printf("深度优先遍历:\n"); graphDFSTraverse(*g, 0); printf("\n\n***************\n"); printf("拓扑排序:\n"); SqQueue *q; VNode *vNode; vNode = (VNode*)malloc(sizeof(VNode)); if(!vNode){ printf("Allocate memory for vNode error!\n"); exit(OVERFLOW); } q = (SqQueue*)malloc(sizeof(SqQueue)); if(!q){ printf("Allocate memory for queue error!\n"); exit(OVERFLOW); } InitQueue(q); TopologicalSort(*g, q); while(!QueueEmpty(*q)){ DeQueue(q, vNode); visitGraphNode(*g, vNode->data); } free(vNode); DestroyQueue(q); printf("\n\n****************\n"); printf("最短路径(Bellman-Ford):\n"); ShortestPath_BellmanFord(*g, 0); printf("\n\n****************\n"); printf("最短路径(DAG):\n"); ShortestPath_DAG(*g, 0); printf("\n\n****************\n"); printf("最短路径(Dijkstra):\n"); ShortestPath_DAG(*g, 0); printf("\n\n****************\n"); printf("关键路径:\n"); CriticalPath(*g); free(g); return 1; }