devbox
思考机器5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构——图_图数据结构

作者：思考机器5 | 2024-01-05 09:50:57

赞

踩

图数据结构

图的定义

        图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

        线性表中可以没有数据元素，称为空表；树中可以没有结点，叫做空树；图的点集不能为空，边集可以为空。

各种图的定义

 

 

  

图的顶点与边间的关系 

 

 

 

连通图的相关术语

  

  

               一个连通图的生成树是一个极小的连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。 

图的定义与术语总结 

图的存储结构

邻接矩阵

         无向图的边数组是一个对称矩阵。

  1. typedef char VertexType; 			/* 顶点类型应由用户定义  */
  2. typedef int EdgeType; 				/* 边上的权值类型应由用户定义 */
  3. #define MAXVEX 100 					/* 最大顶点数，应由用户定义 */
  4. #define INFINITY 65535				/* 用65535来代表∞ */
  5. typedef struct
  6. {
  7. 	VertexType vexs[MAXVEX]; 		/* 顶点表 */
  8. 	EdgeType arc[MAXVEX][MAXVEX];	/* 邻接矩阵，可看作边表 */
  9. 	int numNodes, numEdges; 		/* 图中当前的顶点数和边数  */
  10. }MGraph;
  1. /* 建立无向网图的邻接矩阵表示 */
  2. void CreateMGraph(MGraph *G)
  3. {
  4. 	int i,j,k,w;
  5. 	printf("输入顶点数和边数:\n");
  6. 	scanf("%d,%d",&G->numNodes,&G->numEdges); 		/* 输入顶点数和边数 */
  7. 	for(i = 0;i <G->numNodes;i++) 					/* 读入顶点信息,建立顶点表 */
  8. 		scanf(&G->vexs[i]);
  9. 	for(i = 0;i <G->numNodes;i++)
  10. 		for(j = 0;j <G->numNodes;j++)
  11. 			G->arc[i][j]=INFINITY;					/* 邻接矩阵初始化 */
  12. 	for(k = 0;k <G->numEdges;k++) 					/* 读入numEdges条边，建立邻接矩阵 */
  13. 	{
  14. 		printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
  15. 		scanf("%d,%d,%d",&i,&j,&w); 				/* 输入边(vi,vj)上的权w */
  16. 		G->arc[i][j]=w; 
  17. 		G->arc[j][i]= G->arc[i][j]; 				/* 因为是无向图，矩阵对称 */
  18. 	}
  19. }

邻接表 

         邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。

        将数组与链表相结合的存储方法称为邻接表。

  1. typedef char VertexType; 	/* 顶点类型应由用户定义 */
  2. typedef int EdgeType; 		/* 边上的权值类型应由用户定义 */
  3.  
  4. typedef struct EdgeNode 	/* 边表结点  */
  5. {
  6. 	int adjvex;    			/* 邻接点域,存储该顶点对应的下标 */
  7. 	EdgeType info;			/* 用于存储权值,对于非网图可以不需要 */
  8. 	struct EdgeNode *next; 	/* 链域,指向下一个邻接点 */
  9. }EdgeNode;
  10.  
  11. typedef struct VertexNode 	/* 顶点表结点 */
  12. {
  13. 	VertexType data; 		/* 顶点域,存储顶点信息 */
  14. 	EdgeNode *firstedge;	/* 边表头指针 */
  15. }VertexNode, AdjList[MAXVEX];
  16.  
  17. typedef struct
  18. {
  19. 	AdjList adjList; 
  20. 	int numNodes,numEdges; 	/* 图中当前顶点数和边数 */
  21. }GraphAdjList;

无向图的邻接表的创建代码如下

  1. /* 建立图的邻接表结构 */
  2. void  CreateALGraph(GraphAdjList *G)
  3. {
  4. 	int i,j,k;
  5. 	EdgeNode *e;
  6. 	printf("输入顶点数和边数:\n");
  7. 	scanf("%d,%d",&G->numNodes,&G->numEdges); 	/* 输入顶点数和边数 */
  8. 	for(i = 0;i < G->numNodes;i++) 				/* 读入顶点信息,建立顶点表 */
  9. 	{
  10. 		scanf(&G->adjList[i].data); 			/* 输入顶点信息 */
  11. 		G->adjList[i].firstedge=NULL; 			/* 将边表置为空表 */
  12. 	}
  13. 	
  14. 	
  15. 	for(k = 0;k < G->numEdges;k++)				/* 建立边表 */
  16. 	{
  17. 		printf("输入边(vi,vj)上的顶点序号:\n");
  18. 		scanf("%d,%d",&i,&j); 					/* 输入边(vi,vj)上的顶点序号 */     
  19. 		e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */     
  20. 		e->adjvex=j;							/* 邻接序号为j */                  
  21. 		e->next=G->adjList[i].firstedge;		/* 将e的指针指向当前顶点上指向的结点 */
  22. 		G->adjList[i].firstedge=e;				/* 将当前顶点的指针指向e */          
  23. 		e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */     
  24. 		e->adjvex=i;							/* 邻接序号为i */                  
  25. 		e->next=G->adjList[j].firstedge;		/* 将e的指针指向当前顶点上指向的结点 */
  26. 		G->adjList[j].firstedge=e;				/* 将当前顶点的指针指向e */           
  27. 	}
  28. }

         对于无向图，一条边都是对应两个顶点，所以在循环中，一次就针对i和j分别进行了插入。本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

十字链表

 邻接多重表

        有4个顶点5条边，先将4个顶点和5条边表结点画出来，然后再连线。

边集数组

图的遍历 

        从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。 

         图极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此我们需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问后设置为1。

深度优先遍历 

        图的深度优先遍历与树的先序遍历类似，即尽可能深的遍历图。

        如果我们用的是邻接矩阵的方式，则代码如下

  1. #define MAXVEX 9
  2. Boolean visited[MAXVEX]; 				/* 访问标志的数组 */
  3.  
  4. /* 邻接矩阵的深度优先递归算法 */
  5. void DFS(MGraph G, int i)
  6. {
  7. 	int j;
  8.  	visited[i] = TRUE;                    /*该顶点已被访问*/
  9.  	printf("%c ", G.vexs[i]);			/* 打印顶点，也可以其它操作 */
  10. 	for(j = 0; j < G.numVertexes; j++)
  11. 		if(G.arc[i][j] == 1 && !visited[j])
  12.  			DFS(G, j);					/* 对未访问的邻接顶点递归调用 */
  13. }
  14.  
  15. /* 邻接矩阵的深度遍历操作 */
  16. //从每个顶点进行深度优先遍历，防止非连通图
  17. void DFSTraverse(MGraph G)
  18. {
  19. 	int i;
  20.  	for(i = 0; i < G.numVertexes; i++)
  21.  		visited[i] = FALSE; 			/* 初始所有顶点状态都是未访问过状态 */
  22. 	for(i = 0; i < G.numVertexes; i++)
  23.  		if(!visited[i]) 				/* 对未访问过的顶点调用DFS，若连通图仅执行一次 */ 
  24. 			DFS(G, i);
  25. }

        如果图结构是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有所不同

  1. /* 邻接表的深度优先递归算法 */
  2. void DFS(GraphAdjList GL, int i)
  3. {
  4. 	EdgeNode *p;
  5.  	visited[i] = TRUE;
  6.  	printf("%c ",GL->adjList[i].data);	/* 打印顶点,也可以其它操作 */
  7. 	p = GL->adjList[i].firstedge;
  8. 	while(p)
  9. 	{
  10.  		if(!visited[p->adjvex])
  11.  			DFS(GL, p->adjvex);			/* 对为访问的邻接顶点递归调用 */
  12. 		p = p->next;
  13.  	}
  14. }
  15.  
  16. /* 邻接表的深度遍历操作 */
  17. void DFSTraverse(GraphAdjList GL)
  18. {
  19. 	int i;
  20.  	for(i = 0; i < GL->numVertexes; i++)
  21.  		visited[i] = FALSE; 			/* 初始所有顶点状态都是未访问过状态 */
  22. 	for(i = 0; i < GL->numVertexes; i++)
  23.  		if(!visited[i]) 				/* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */ 
  24. 			DFS(GL, i);
  25. }

 广度优先遍历

        图的广度优先遍历与树的层次遍历类似，需要借助队列来实现

基本思想：

  • 首先访问某一顶点v，并由v出发，依次访问顶点v未被访问过的所有邻接顶点w1,w2…wi；
  • 再依次访问w1,w2…wi未被访问过的所有邻接顶点；
  • 重复上述过程，直到所有顶点被访问；

 邻接矩阵的广度优先遍历算法：

  1. /* 邻接矩阵的广度遍历算法 */
  2. void BFSTraverse(MGraph G)
  3. {
  4. 	int i, j;
  5. 	Queue Q;
  6. 	for(i = 0; i < G.numVertexes; i++)
  7.        	visited[i] = FALSE;
  8.     InitQueue(&Q);									/* 初始化一辅助用的队列 */
  9.     for(i = 0; i < G.numVertexes; i++)  			/* 对每一个顶点做循环 */
  10.     {
  11. 		if (!visited[i])							/* 若是未访问过就处理 */
  12. 		{
  13. 			visited[i]=TRUE;						/* 设置当前顶点访问过 */
  14. 			printf("%c ", G.vexs[i]);				/* 打印顶点，也可以其它操作 */
  15. 			EnQueue(&Q,i);							/* 将此顶点入队列 */
  16. 			while(!QueueEmpty(Q))					/* 若当前队列不为空 */
  17. 			{
  18. 				DeQueue(&Q,&i);						/* 将队对元素出队列，赋值给i */
  19. 				for(j=0;j<G.numVertexes;j++) 
  20. 				{ 							
  21. 													/* 判断其它顶点若与当前顶点存在 */
  22. 													/* 边且未访问过 */
  23. 					if(G.arc[i][j] == 1 && !visited[j]) 
  24. 					{ 					
  25.  						visited[j]=TRUE;			/* 将找到的此顶点标记为已访问 */
  26. 						printf("%c ", G.vexs[j]);	/* 打印顶点 */
  27. 						EnQueue(&Q,j);				/* 将找到的此顶点入队列  */
  28. 					} 
  29. 				} 
  30. 			}
  31. 		}
  32. 	}
  33. }

 邻接表的广度优先遍历算法

  1. /* 邻接表的广度遍历算法 */
  2. void BFSTraverse(GraphAdjList GL)
  3. {
  4. 	int i;
  5.     EdgeNode *p;
  6. 	Queue Q;
  7. 	for(i = 0; i < GL->numVertexes; i++)
  8.        	visited[i] = FALSE;
  9.     InitQueue(&Q);
  10.    	for(i = 0; i < GL->numVertexes; i++)
  11.    	{
  12. 		if (!visited[i])
  13. 		{
  14. 			visited[i]=TRUE;
  15. 			printf("%c ",GL->adjList[i].data);	/* 打印顶点,也可以其它操作 */
  16. 			EnQueue(&Q,i);
  17. 			while(!QueueEmpty(Q))
  18. 			{
  19. 				DeQueue(&Q,&i);
  20. 				p = GL->adjList[i].firstedge;	/* 找到当前顶点的边表链表头指针 */
  21. 				while(p)
  22. 				{
  23. 					if(!visited[p->adjvex])		/* 若此顶点未被访问 */
  24.  					{
  25.  						visited[p->adjvex]=TRUE;
  26. 						printf("%c ",GL->adjList[p->adjvex].data);
  27. 						EnQueue(&Q,p->adjvex);	/* 将此顶点入队列 */
  28. 					}
  29. 					p = p->next;				/* 指针指向下一个邻接点 */
  30. 				}
  31. 			}
  32. 		}
  33. 	}
  34. }

最小生成树 

        我们把构造连通网的最小代价生成树称为最小生成树。 

普里姆(Prim)算法

        就是在每次加入时每次将之前加入的顶点看作一个整体，再选择一个整体外的路径最短的顶点加入。

  1. /* Prim算法生成最小生成树  */
  2. void MiniSpanTree_Prim(MGraph G)
  3. {
  4. 	int min, i, j, k;
  5. 	int adjvex[MAXVEX];		/* 保存相关顶点下标 */
  6. 	int lowcost[MAXVEX];	/* 保存相关顶点间边的权值 */
  7. 	lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 */
  8. 			/* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
  9. 	adjvex[0] = 0;			/* 初始化第一个顶点下标为0 */
  10. 	for(i = 1; i < G.numVertexes; i++)	/* 循环除下标为0外的全部顶点 */
  11. 	{
  12. 		lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */
  13. 		adjvex[i] = 0;					/* 初始化都为v0的下标 */
  14. 	}
  15. 	for(i = 1; i < G.numVertexes; i++)
  16. 	{
  17. 		min = GRAPH_INFINITY;	/* 初始化最小权值为∞， */
  18. 						/* 通常设置为不可能的大数字如32767、65535等 */
  19. 		j = 1;k = 0;
  20. 		while(j < G.numVertexes)	/* 循环全部顶点 */
  21. 		{
  22. 			if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
  23. 			{	
  24. 				min = lowcost[j];	/* 则让当前权值成为最小值 */
  25. 				k = j;			/* 将当前最小值的下标存入k */
  26. 			}
  27. 			j++;
  28. 		}
  29. 		printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */
  30. 		lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
  31. 		for(j = 1; j < G.numVertexes; j++)	/* 循环所有顶点 */
  32. 		{
  33. 			if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j]) 
  34. 			{/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
  35. 				lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
  36. 				adjvex[j] = k;				/* 将下标为k的顶点存入adjvex */
  37. 			}
  38. 		}
  39. 	}
  40. }

克鲁斯卡尔(Kruskal)算法 

    直接去找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路。

  1. typedef struct
  2. {
  3. 	int begin;
  4. 	int end;
  5. 	int weight;
  6. }Edge;   /* 对边集数组Edge结构的定义 */

      从小到大每次取出一条边添加到图中，如果形成了环，就抛弃这条边，直到选中n-1条边为止。

  1. /* 查找连线顶点的尾部下标 */
  2. int Find(int *parent, int f)
  3. {
  4. 	while ( parent[f] > 0)
  5. 	{
  6. 		f = parent[f];
  7. 	}
  8. 	return f;
  9. }
  10.  
  11. /* 生成最小生成树 */
  12. void MiniSpanTree_Kruskal(MGraph G)
  13. {
  14. 	int i, j, n, m;
  15. 	int k = 0;
  16. 	int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */
  17. 	
  18. 	Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */
  19.  
  20. 	/* 用来构建边集数组并排序********************* */
  21. 	for ( i = 0; i < G.numVertexes-1; i++)
  22. 	{
  23. 		for (j = i + 1; j < G.numVertexes; j++)
  24. 		{
  25. 			if (G.arc[i][j]<GRAPH_INFINITY)
  26. 			{
  27. 				edges[k].begin = i;
  28. 				edges[k].end = j;
  29. 				edges[k].weight = G.arc[i][j];
  30. 				k++;
  31. 			}
  32. 		}
  33. 	}
  34. 	sort(edges, &G);
  35. 	/* ******************************************* */
  36.  
  37.  
  38. 	for (i = 0; i < G.numVertexes; i++)
  39. 		parent[i] = 0;	/* 初始化数组值为0 */
  40.  
  41. 	printf("打印最小生成树：\n");
  42. 	for (i = 0; i < G.numEdges; i++)	/* 循环每一条边 */
  43. 	{
  44. 		n = Find(parent,edges[i].begin);
  45. 		m = Find(parent,edges[i].end);
  46. 		if (n != m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
  47. 		{
  48. 			parent[n] = m;	/* 将此边的结尾顶点放入下标为起点的parent中。 */
  49. 							/* 表示此顶点已经在生成树集合中 */
  50. 			printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
  51. 		}
  52. 	}
  53. }

最短路径

BFS算法

        相当于对广度优先算法进行了改造。

Dijkstra算法 

 

  1. typedef struct
  2. {
  3. 	int vexs[MAXVEX];
  4. 	int arc[MAXVEX][MAXVEX];
  5. 	int numVertexes, numEdges;
  6. }MGraph;
  7.  
  8. typedef int Patharc[MAXVEX];    /* 用于存储最短路径下标的数组 */
  9. typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 */
  10.  
  11.  
  12. /*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */    
  13. /*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */  
  14. void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
  15. {    
  16. 	int v,w,k,min;    
  17. 	int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */
  18. 	for(v=0; v<G.numVertexes; v++)    /* 初始化数据 */
  19. 	{        
  20. 		final[v] = 0;			/* 全部顶点初始化为未知最短路径状态 */
  21. 		(*D)[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */
  22. 		(*P)[v] = -1;				/* 初始化路径数组P为-1  */       
  23. 	}
  24.  
  25. 	(*D)[v0] = 0;  /* v0至v0路径为0 */  
  26. 	final[v0] = 1;    /* v0至v0不需要求路径 */        
  27. 	/* 开始主循环，每次求得v0到某个v顶点的最短路径 */   
  28. 	for(v=1; v<G.numVertexes; v++)   
  29. 	{
  30. 		min=GRAPH_INFINITY;    /* 当前所知离v0顶点的最近距离 */        
  31. 		for(w=0; w<G.numVertexes; w++) /* 寻找离v0最近的顶点 */    
  32. 		{            
  33. 			if(!final[w] && (*D)[w]<min)             
  34. 			{                   
  35. 				k=w;                    
  36. 				min = (*D)[w];    /* w顶点离v0顶点更近 */            
  37. 			}        
  38. 		}        
  39. 		final[k] = 1;    /* 将目前找到的最近的顶点置为1 */
  40. 		for(w=0; w<G.numVertexes; w++) /* 修正当前最短路径及距离 */
  41. 		{
  42. 			/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
  43. 			if(!final[w] && (min+G.arc[k][w]<(*D)[w]))   
  44. 			{ /*  说明找到了更短的路径，修改D[w]和P[w] */
  45. 				(*D)[w] = min + G.arc[k][w];  /* 修改当前路径长度 */               
  46. 				(*P)[w]=k;        
  47. 			}       
  48. 		}   
  49. 	}
  50. }

Floyd算法

 

 

 

 

拓扑排序

        在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。 

         所谓拓扑排序，其实就是对一个有向图构造拓扑排序的过程。

拓扑排序算法

         由于拓扑排序的过程中需要删除顶点，用邻接表会更加方便。考虑到算法过程中始终要查找入度为0的顶点，我们在原来顶点表结点结构中，增加一个入度域in，其中in就是入度的数字。

 

  1. /* 邻接表结构****************** */
  2. typedef struct EdgeNode /* 边表结点  */
  3. {
  4. 	int adjvex;    /* 邻接点域，存储该顶点对应的下标 */
  5. 	int weight;		/* 用于存储权值，对于非网图可以不需要 */
  6. 	struct EdgeNode *next; /* 链域，指向下一个邻接点 */
  7. }EdgeNode;
  8.  
  9. typedef struct VertexNode /* 顶点表结点 */
  10. {
  11. 	int in;	/* 顶点入度 */
  12. 	int data; /* 顶点域，存储顶点信息 */
  13. 	EdgeNode *firstedge;/* 边表头指针 */
  14. }VertexNode, AdjList[MAXVEX];
  15.  
  16. typedef struct
  17. {
  18. 	AdjList adjList; 
  19. 	int numVertexes,numEdges; /* 图中当前顶点数和边数 */
  20. }graphAdjList,*GraphAdjList;

        借助栈这种数据结构， 最开始先让入度为0的结点入栈，然后弹出一个入度为0的结点并修改其他结点的入度，如果有为0的入栈，依次循环。

  1. /* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */
  2. Status TopologicalSort(GraphAdjList GL)
  3. {    
  4. 	EdgeNode *e;    
  5. 	int i,k,gettop;   
  6. 	int top=0;  /* 用于栈指针下标  */
  7. 	int count=0;/* 用于统计输出顶点的个数  */    
  8. 	int *stack;	/* 建栈将入度为0的顶点入栈  */   
  9. 	stack=(int *)malloc(GL->numVertexes * sizeof(int) );    
  10.  
  11. 	for(i = 0; i<GL->numVertexes; i++)                
  12. 		if(0 == GL->adjList[i].in) /* 将入度为0的顶点入栈 */         
  13. 			stack[++top]=i;    
  14. 	while(top!=0)    
  15. 	{        
  16. 		gettop=stack[top--];        
  17. 		printf("%d -> ",GL->adjList[gettop].data);        
  18. 		count++;        /* 输出i号顶点，并计数 */        
  19. 		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
  20. 		{            
  21. 			k=e->adjvex;            
  22. 			if( !(--GL->adjList[k].in) )  /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */                
  23. 				stack[++top]=k;        
  24. 		}
  25. 	}   
  26. 	printf("\n");   
  27. 	if(count < GL->numVertexes)        
  28. 		return ERROR;    
  29. 	else       
  30. 		return OK;
  31. }

关键路径

        在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动 ，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网。我们把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。由于一个工程，总有一个开始，一个结束，所以正常情况下，AOE网只有一个源点一个汇点。

关键路径算法的原理

        我们需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。 

关键路径算法

 

 

  1. int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组 */
  2. int *stack2;   /* 用于存储拓扑序列的栈 */
  3. int top2;	   /* 用于stack2的指针 */

  1. /* 拓扑排序 */
  2. Status TopologicalSort(GraphAdjList GL)
  3. {    /* 若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */    
  4. 	EdgeNode *e;    
  5. 	int i,k,gettop;   
  6. 	int top=0;  /* 用于栈指针下标  */
  7. 	int count=0;/* 用于统计输出顶点的个数 */   
  8. 	int *stack;	/* 建栈将入度为0的顶点入栈  */   
  9. 	stack=(int *)malloc(GL->numVertexes * sizeof(int) );    
  10. 	for(i = 0; i<GL->numVertexes; i++)                
  11. 		if(0 == GL->adjList[i].in) /* 将入度为0的顶点入栈 */           
  12. 			stack[++top]=i;    
  13.  
  14. 	top2=0;    
  15. 	etv=(int *)malloc(GL->numVertexes * sizeof(int) ); /* 事件最早发生时间数组 */    
  16. 	for(i=0; i<GL->numVertexes; i++)        
  17. 		etv[i]=0;    /* 初始化 */
  18. 	stack2=(int *)malloc(GL->numVertexes * sizeof(int) );/* 初始化拓扑序列栈 */
  19.  
  20. 	printf("TopologicalSort:\t");
  21. 	while(top!=0)    
  22. 	{        
  23. 		gettop=stack[top--];        
  24. 		printf("%d -> ",GL->adjList[gettop].data);        
  25. 		count++;        /* 输出i号顶点，并计数 */ 
  26.  
  27. 		stack2[++top2]=gettop;        /* 将弹出的顶点序号压入拓扑序列的栈 */
  28.  
  29. 		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
  30. 		{            
  31. 			k=e->adjvex;            
  32. 			if( !(--GL->adjList[k].in) )        /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */                
  33. 				stack[++top]=k; 
  34.  
  35. 			if((etv[gettop] + e->weight)>etv[k])    /* 求各顶点事件的最早发生时间etv值 */                
  36. 				etv[k] = etv[gettop] + e->weight;
  37. 		}    
  38. 	}    
  39. 	printf("\n");   
  40. 	if(count < GL->numVertexes)        
  41. 		return ERROR;    
  42. 	else       
  43. 		return OK;
  44. }
  45.  
  46. /* 求关键路径,GL为有向网，输出G的各项关键活动 */
  47. void CriticalPath(GraphAdjList GL) 
  48. {    
  49. 	EdgeNode *e;    
  50. 	int i,gettop,k,j;    
  51. 	int ete,lte;  /* 声明活动最早发生时间和最迟发生时间变量 */        
  52. 	TopologicalSort(GL);   /* 求拓扑序列，计算数组etv和stack2的值 */ 
  53. 	ltv=(int *)malloc(GL->numVertexes*sizeof(int));/* 事件最早发生时间数组 */   
  54. 	for(i=0; i<GL->numVertexes; i++)        
  55. 		ltv[i]=etv[GL->numVertexes-1];    /* 初始化 */        
  56. 	
  57. 	printf("etv:\t");   
  58. 	for(i=0; i<GL->numVertexes; i++)        
  59. 		printf("%d -> ",etv[i]);    
  60. 	printf("\n"); 
  61.  
  62. 	while(top2!=0)    /* 出栈是求ltv */    
  63. 	{        
  64. 		gettop=stack2[top2--];        
  65. 		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        /* 求各顶点事件的最迟发生时间ltv值 */        
  66. 		{            
  67. 			k=e->adjvex;            
  68. 			if(ltv[k] - e->weight < ltv[gettop])               
  69. 				ltv[gettop] = ltv[k] - e->weight;        
  70. 		}   
  71. 	}    
  72. 	
  73. 	printf("ltv:\t");   
  74. 	for(i=0; i<GL->numVertexes; i++)        
  75. 		printf("%d -> ",ltv[i]);    
  76. 	printf("\n"); 
  77.  
  78. 	for(j=0; j<GL->numVertexes; j++)        /* 求ete,lte和关键活动 */        
  79. 	{            
  80. 		for(e = GL->adjList[j].firstedge; e; e = e->next)            
  81. 		{                
  82. 			k=e->adjvex;                
  83. 			ete = etv[j];        /* 活动最早发生时间 */                
  84. 			lte = ltv[k] - e->weight; /* 活动最迟发生时间 */               
  85. 			if(ete == lte)    /* 两者相等即在关键路径上 */                    
  86. 				printf("<v%d - v%d> length: %d \n",GL->adjList[j].data,GL->adjList[k].data,e->weight);
  87. 		}        
  88. 	}
  89. }

        

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/38219?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号