编程知识 cdmana.com

数据结构学习(四)--图

(一)

线性关系是一对一的关系,是有层次的一对多且的关系,是多对多的关系。

线性表中,将数据元素称之为元素,树结构中将数据元素称之为结点,在图结构中将数据元素称之为顶点Vertex

1. 相关定义

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

顶点ViVj之间的边没有方向,则称这条边为无向边Edge),用无序偶(ViVj)来表示。

(3) 无向完全图

任何两个顶点之间都存在边,则该图称之为无向完全图

(4) 有向边

顶点ViVj之间的边有方向,则称这条边为有向边Edge),也称之为,用有序偶<ViVj>来表示。其中Vi弧尾Vj弧头

(5) 简单图

不存在顶点到自身的边,同一条边不重复出现。这样的图称之为简单图

(6) 简单定义名词

有向完全图稀疏图稠密图(边或弧上的数字)、邻接点依附(边依附于两个顶点),顶点的度(和顶点关联的边的数目)、出度(顶点为尾的弧的数目)、入度(顶点为弧头的边的数目)

(7) 

带权的图称之为网Network

(8) 路径Path

(需要验证)图中从顶点A到顶点D的路径,是一个顶点序列(),其实就是一组相互关联的边的路径。是边的集合。路径长度是边或弧的数目。

(9) 

第一个顶点到最后一个顶点相同的路径称之为回路或者。序列中,顶点不重复出现的路径称之为简单路径。除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称之为简单回路

(10) 子图

假设两个图G=VE)和G’=V’,E’,如果VV的子集,EE的子集。则称G’G的子树。

(11) 连通图

两个结点之间有路径,称之为两个结点连通。如果图中任意两个结点之间都连通,则称图为连通图。无向图中,极大连通子图称之为连通分量

(12) 连通图生成树

是一个极小连通子图,包含图的全部的N个顶点,但只有足够构成一棵树的N-1条边。

2. 存储结构

(1) 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图,一个一维数组存储途中的顶点信息。一个二维数组(称之为邻接矩阵)存储图中的弧或者边信息。

无向图的邻接矩阵是对称矩阵。邻接矩阵方便计算顶点的度。

(2) 邻接表

用数组存放顶点信息,用链表存放顶点的边的信息。这种用数组和链表相结合的存储方式称之为邻接链表。

顶点的数据结构为 数据域data和指针域first_edge

邻接表用来存放无向图比较合适。因为不存在入度出度的问题。如果存放有向图,只能存放出度的弧(邻接表)或者选择存放入度的弧(逆邻接表)。选择一种。比如选择出度,则计算该结点的入度需要遍历整个图。计算比较麻烦。

(3) 十字链表

把邻接表和逆邻接表结合起来。

顶点元素数据结构为数据域data和两个指针域first_in first_out

顶点存放在数组顶点表中。

边表结点结构tail_vex是 弧起点在顶点表的下标,head_vex是弧终点在顶点表的下标,head_link 是入边表指针域,指向终点相同的下一条边。tail_link 是出边指针域,指向起点相同的下一条边。

(4) 邻接多重表
(5) 边集数组

有两个一维数组组成。一个存储顶点信息,另一个存储边信息。边信息数据元素为边的起点下标begin,终点下标end和权值weight

3. 图的遍历

从图的某一顶点出发,遍历图中其余顶点。并且每个顶点只被访问且仅访问一次。这一过程被称之为图的遍历

(1) 图深度优先遍历

深度优先遍历(Depth_First_Search),也称之为深度优先搜索。简称DFS

从图的某顶点V出发,访问此顶点。然后从V的未被访问的邻接点出发,深度优先遍历图,直至所有和V有路径相同的顶点都被访问到。若图中尚未有顶点未被访问到,则另选一个未被访问到的顶点作为始点,重复上述过程,直到图中所有顶点都被访问到为止。

邻接矩阵深度优先算法

分为两层操作。

第一层:遍历顶点表,每个顶点被设置成未被访问过。其次遍历每个结点,如果结点未被访问,则调用 邻接矩阵深度优先递归算法。

第二层:邻接矩阵深度优先递归算法实现。首先访问该结点,设置该结点已经被访问。然后遍历邻接矩阵中该结点对应的一行数据的一维数组。本质是遍历和当前顶点邻接点。递归调用自身方法。

 

  1. bool visited[MaxVnum];  
  2. void DFS(Graph G,int v)  
  3. {  
  4. visited[v]= true; //从V开始访问,flag它  
  5. printf("%d",v);    //打印出V  
  6. for(int j=0;j<G.vexnum;j++)   
  7. if(G.arcs[v][j]==1&&visited[j]== false) //这里可以获得V未访问过的邻接点  
  8. DFS(G,j); //递归调用,如果所有节点都被访问过,就回溯,而不再调用这里的DFS  
  9. }  
  10. void DFSTraverse(Graph G) {  
  11. for (int v = 0; v < G.vexnum; v++)  
  12. visited[v] = false; //刚开始都没有被访问过  
  13. for (int v = 0; v < G.vexnum; ++v)  
  14. if (visited[v] == false) //从没有访问过的第一个元素来遍历图  
  15. DFS(G, v);  
  16. }

 

l 邻接表深度优先算法

分为两层操作。

第一层:遍历顶点表,每个顶点被设置成未被访问过。其次遍历每个结点,如果结点未被访问,则调用 邻接表深度优先递归算法。

第二层:邻接表深度优先递归算法实现。首先访问该结点,设置该结点已经被访问。然后遍历邻接表的链表。本质是遍历和当前顶点邻接点。递归调用自身方法。

代码如下:

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

广度优先遍历(Breadth_First_Search),也称之为广度优先搜索。简称BFS

l 邻接矩阵的图广度优先遍历

分为三层;第一层,设置所有顶点表中所有顶点为未被访问。然后遍历所有的顶点,访问顶点数据,并设置当前顶点已经被访问过。访问过顶点加入队列。

第二层:弹出第一层的顶点元素,遍历访问被访问过的顶点的相邻结点【对应邻接矩阵的一行数据】。相当于访问第二层数据。访问结束后,按照访问顺序加入队列。

第三层:队列中还有数据,会继续弹出数据,逐个处理第三层数据。依次向下处理。直至所有结点都被处理过。

l 邻接表的图广度优先遍历

邻接表的广度优先处理和邻接矩阵处理思路一致。只是在取下一层数据的方式不一致罢了。邻接矩阵是取一行数据,邻接表是取一个链表而已。

4. 最小生成树

构造连通图最小代价的生成树称之为最小生成树。个人理解:能连通所有结点,且连通代价最小。有很大的实际意义。多个地点之间连通网络,且代价最小。

(1) 普里姆算法

假设N=V,{E}}是连通网,TEN上最小生成树中边的集合。算法从U=U0}(U0V的元素),TE={}开始。重复执行以下操作:在所有边满足一个顶点在U中,另一个顶点在V-U中的边,选择一个权值最小的边。作为TE的元素。同时,TE中所有的顶点都放入U中。然后继续上述操作,直到U=V。则T就是N的最小生成树。

(2) 克鲁斯卡尔算法

5. 最短路径

最短路径是两个顶点之间经过边上的权值之和最小的路径。并且我们称第一个结点为源点,最后一个顶点为终点。

6. 拓扑排序

l 定义

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们成为AOVAOV网的弧表示活动之间的某种制约关系。

拓扑序列:设G=VE}是一个有n个顶点的有向图,V中的顶点序列V1V2 ... Vn,满足若从顶点i到顶点j有一条路径。则在顶点序列中顶点Vi必然在顶点Vj之前。我们称这样的顶点序列为拓扑序列

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

l 算法

AOV网络中选择一个入度为0的顶点输出,然后删除此顶点,并删除依此顶点为尾的弧(该弧的终点对应的顶点的入度需要-1),继续重复此步骤。直至全部顶点或者AOV网中不存在顶点的入度为0的顶点为止。

代码思想

1 定义一个栈(stack)存储没有入度的顶点序号,定义top指向栈顶,定义count记录输出的顶点个数,以便判断是否有环存在。

2 初始化stack,把所有入度为0的顶点入栈。

3 在栈不为空的情形下进行循环:出栈,并打印这个顶点信息,count++。接下来通过循环访问该顶点的邻接表并对弧头的入度in减一,如果in等于0,则需要把该顶点入栈。

4 最后判断count是否等于顶点数

代码如下

  1. int TopologicalSort(GraphVerter G)  
  2. {  
  3. EdgeNode *e;  
  4. int i;  
  5. int top = 0;  
  6. int gettop;  
  7. int count = 0;  
  8. int *stack;  
  9. stack = (int *)malloc(G.numvertexes * sizeof(int));   // 创建栈
  10. for(i = 0; i < G.numvertexes; i++)  
  11. {  
  12. if(G.verter[i]->in == 0)  
  13. stack[++top] = i;  // 入度为0的顶点入栈
  14. }  
  15. while(top != 0)   // 栈不为空的情况下循环出栈、处理
  16. {  
  17. gettop = stack[top--];  
  18. printf("%d",G.verter[gettop]->data);  
  19. count++;  
  20. for(e = G.verter[gettop]->firstedge; e ; e = e->next)  
  21. {  
  22. G.verter[e->adjvex]->in--;  //弧头顶点的入度-1
  23. if(G.verter[e->adjvex]->in == 0)  // -1后如果为0,则入栈
  24. stack[++top] = e->adjvex;  
  25. }  
  26. }  
  27. if(count < G.numvertexes)   // count == G.numvertexes 代表所有顶点都在拓扑序列
  28. return 0;  
  29. else  
  30. return 1;  

7. 关键路径

拓扑排序主要解决一个工程是否能顺序进行的问题。关键路径是解决工程完成需要的最短时间问题。

(1) 定义

l AOE

在一个表示工程的带权有向图中,用顶点表示事件,用有向图的边表示活动,用边上的权值便是活动持续的时间。这种有向图边表示活动的网,称之为AOE网。

AOV网和AOE网的区别:

AOV网用顶点表示事件,它只描述活动之间的制约关系。

AOE网是建立在活动之间制约关系没有矛盾的基础之上。再来分析整个工程需要多少时间。或者为了缩短工程的所需时间,需要加快那些活动的问题。

l 关键活动

路径上各个活动(弧)所持续的时间之和称为路径长度。从源点到汇点具有最大的长度的路径叫做关键路径。在关键路径上的活动称为关键活动。只有缩短关键路径上的关键活动的时间,才可以减少工期的长度。

(2) 算法思想

 

 

 

四个必要的参数,前面两个针对顶点,后面两个针对边

事件最早发生时间etvearliest time of vertex顶点Vi的最早发生时间。

事件最晚发生时间ltvlastest time of vertex

顶点Vi最晚发生的时间,超出则会延误整个工期。

活动的最早开工时间eteearliest time of edge

Eg最早发生时间。

活动的最晚开工时间ltelastest time if edge

Eg最晚发生时间。不推迟工期的最晚开工时间。

 

 

 

 

最早发生时间:假设起点是vo,则我们称从v0到vi的最长路径的长度为vi的最早发生时间理解:Vi代表一个事件,它发生意味着它所依赖的所有的事情都发生。即从Vo出发的所有线路都到达Vi处。既然所有都发生,那么路径最长的路径也都发生了。所以,这是Vi的最早发生时间

同时,vi的最早发生时间也是所有以vi为尾的弧所表示的活动的最早开始时间每个事件最早开始时间就是事件的弧的起点时间的醉倒发生时间)。使用e(i)表示活动ai最早发生时间,除此之外,我们还定义了一个活动最迟发生时间,使用l(i)表示,不推迟工期的最晚开工时间。我们把e(i)=l(i)的活动ai称为关键活动,因此,这个条件就是我们求一个AOE-网的关键路径的关键所在了。

我们现在要求的就是每弧所对应的e(i)和l(i),求这两个变量的公式是

e(i)=ve(j)  

l(i)=vl(k)-dut(<j,k>) 

 

变量介绍

首先我们假设活动ai)是弧<j,k>上的活动,j为弧尾顶点,k为弧头(有箭头的一边), vej)代表的是弧尾j的最早发生时间, vlk)代表的是弧头k的最迟发生时间 dut<j,k>)代表该活动要持续的时间,既是弧的权值

 

算法思想

要准备两个数组,a:最早开始时间数组etvb:最迟开始时间数组。(针对顶点即事件而言

1.从源点V0出发,令etv[0](源点)=0,按拓扑有序求其余各顶点的最早发生时间etv[i]1 i n-1)。同时按照上一章

拓扑排序的方法检测是否有环存在。

2.从汇点Vn出发,令ltv[n-1] = etv[n-1],按拓扑排序求各个其余各顶点的最迟发生时间ltv[i]n-2 i 2;

3.根据各顶点的etvltv数组的值,求出弧(活动)的最早开工时间和最迟开工时间,求每条弧的最早开工时间和最迟开工时间是否相等,若相等,则是关键活动。

注意:12 完成点(事件)的最早和最迟。3根据事件来计算活动最早和最迟,从而求的该弧(活动)是否为关键活动。

 

 

(3) 关键路径算法

① 改进的拓扑算法,在计拓扑排序的时候计算出每个顶点的最早发生时间。

  1. int TopplogicalSort(GraphAdjList *g)  
  2. {  
  3. int count=0;  
  4. eNode *e=NULL;    
  5. StackType *stack=NULL;  
  6. StackType top=0;  
  7. stack = (StackType *)malloc((*g).numVextexs*sizeof(StackType));    
  8. int i;  
  9. //初始化拓扑序列栈  
  10. g_topOfStk = 0;  
  11. //开辟拓扑序列栈对应的最早开始时间数组  
  12. g_etv = (int *)malloc((*g).numVextexs*sizeof(int));  
  13. //初始化数组  
  14. for (i=0;i<(*g).numVextexs;i++)  
  15. g_etv[i]=0;        
  16. //开辟拓扑序列的顶点数组栈  
  17. g_StkAfterTop = (int *)malloc(sizeof(int)*(*g).numVextexs);  
  18. //入度为0的顶点入栈  
  19. for (i=0;i<(*g).numVextexs;i++)  
  20. if (!(*g).adjList[i].numIn)  
  21. stack[++top] = i;      
  22. while(top)  
  23. {  
  24. int geter = stack[top];  
  25. top--;    
  26. //把拓扑序列保存到拓扑序列栈,为后面做准备 stack最早出栈g_StkAfterTop的放在栈底。stack最后出栈的元素放在 g_StkAfterTop的栈顶
  27. g_StkAfterTop[g_topOfStk++] = geter;    
  28. count++;    
  29. //获取当前点出度的点,对出度的点的入度减一(当前点要出图)。  
  30. //获取当前顶点的出度点表  
  31. e = (*g).adjList[geter].fitstedge;  
  32. while(e)          {  
  33. int eIdx = e->idx;  
  34. //选取的出度点的入度减一  
  35. int crntIN = --(*g).adjList[eIdx].numIn;  
  36. if (crntIN == 0)  
  37. //如果为0,则说明该顶点没有入度了,是下一轮的输出点。  
  38. stack[++top] = eIdx;        
  39. //求出关键路径  顶点的最早发生时间
  40. if ((g_etv[geter] + e->weigh) > g_etv[eIdx])  
  41. {                  g_etv[eIdx] = g_etv[geter] + e->weigh;              }  
  42. e = e->next;  
  43. }  
  44. }  
  45. if (count < (*g).numVextexs)  {//如果图本身就是一个大环,或者图中含有环,这样有环的顶点不会进栈而被打印出来。  
  46. return false;    }  
  47. else{  
  48. printf("finish\n");  
  49. return true;    }  
  50. }  

② 关键路径代码

  1. void CriticalPath(GraphAdjList g)  
  2. {  
  3. int i;  
  4. int geter;  
  5. eNode *e = NULL;  
  6. g_topOfStk--;  
  7. //1.初始化最迟开始时间数组(汇点的最早开始时间(初值))  
  8. g_ltv = (int *)malloc(sizeof(int)*g.numVextexs);  
  9. for (i=0;i<g.numVextexs;i++)  
  10. {  
  11. g_ltv[i] = g_etv[g.numVextexs-1];  
  12. }  
  13. //2.求每个点的最迟开始时间,从汇点到源点推。  
  14. while (g_topOfStk)  
  15. {  
  16. //获取当前出栈(反序)的序号  
  17. geter = g_StkAfterTop[g_topOfStk--];  
  18. //对每个出度点  
  19. if (g.adjList[geter].fitstedge != NULL)  
  20. {  
  21. e = g.adjList[geter].fitstedge;  
  22. while(e != NULL)  
  23. {  
  24. int eIdx = e->idx;  
  25. if (g_ltv[eIdx] - e->weigh < g_ltv[geter])  
  26. {  
  27. g_ltv[geter] = g_ltv[eIdx] - e->weigh;  
  28. }  
  29. e = e->next;  
  30. }  
  31. }  
  32. }  
  33. int ete,lte;//活动最早开始和最迟开始时间  
  34. printf("start:->");  
  35. //3.求关键活动,即ltv和etv相等的  
  36. for (i=0;i<g.numVextexs;i++)  
  37. {  
  38. if (g.adjList[i].fitstedge)  
  39. {  
  40. e = g.adjList[i].fitstedge;  
  41. while(e)  
  42. {  
  43. int eIdx = e->idx;  
  44. //活动(i->eIdx)最早开始时间:事件(顶点) i最早开始时间  
  45. ete = g_etv[i];  
  46. //活动(i->eIdx)最迟开始时间:事件(顶点) eIdx 最迟开始时间 减去 活动持续时间  
  47. lte = g_ltv[eIdx] - e->weigh;  
  48. if (ete == lte)  
  49. {  
  50. printf("(%c - %c)->",g_init_vexs[i],g_init_vexs[eIdx]);  
  51. }  
  52. e= e->next;  
  53. }  
  54. }  
  55. }  
  56. printf(" end\n");  
  57. }  

版权声明
本文为[IT迷途小书童]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/maopneo/p/13958543.html

Scroll to Top