算法：图的相干算法

1. 图的遍历算法

图的遍历是指从某个顶点出发，沿着某条搜刮路径对图中的全部顶点举行访问且只访问次的过程。
图的遍历算法是求解图的连通性标题、拓扑排序及求关键路径等算法的根本。
图的遍历要比树的遍历复杂得多。由于图的任一个结点都大概与别的顶点相毗邻，以是在访问了某个顶点之后，大概沿着某路径又回到该结点上，为了克制对顶点举行重复访问，在图的遍历过程中必须记下每个已访问过的顶点。深度优先搜刮和广度优先搜刮是两种遍历图的根本方法。
1.1 深度优先搜刮

类似树的先根遍历，在第一次颠末一个顶点时就举行访问利用。遍历步调如下：

• 设置搜刮指针 p，使p指向顶点。
  
• 访问p所指顶点，并使p指向与其相毗邻的且尚未被访问过的顶点。
  
• 若p所指顶点存在，则重复步调(2)，否则实行步调(4)。
  
• 沿着刚才访问的序次和方向回溯到一个尚有毗邻顶点且未被访问过的顶点，并使p指向这个未被访问的顶点，然后重复步调(2)，直到全部的顶点均被访问为止。
  

1. int visited[MaxN] = {0};  //调佣遍历算法前设置所有的顶点都被访问过
2. void Dfs(Graph G, int i)
3. {
4.         EdgeNode *t; int j;
5.         printf("%d",i);               //访问序号为i的顶点
6.         visited[i] = 1;               //序号为i的顶点已被访问过
7.         t = G.Vertices[i].firstarc;   //取顶点i的第一个邻接顶点
8.         while(t!=NULL){               //检查所有与顶点i相邻接的顶点
9.         j=t->adjvex;                 //顶点j为顶点i的一个邻接顶点
10.         if(visited[j]==0)           //若顶点j未被访问则从顶点j出发进行深度优先搜索
11.                 Dfs(G,j);
12.         t=t->nextarc;              //取顶点i的下一个邻接顶点
13.         }
14. }

复制代码

1.2 广度优先搜刮

图：广度优先搜刮
图的广度优先搜刮方法为:从图中的某个顶点v出发，在访问了之后依次访问v的各个未被访问过的毗邻点，然后分别从这些毗邻点出发依次访问它们的毗邻点，并使“先被访问的顶点的毗邻点”先于“后被访问的顶点的毗邻点”被访问，直到图中全部已被访问的顶点的毗邻点都被访问到。若此时尚有未被访问的顶点，则另选图中的一个未被访问的顶点作为出发点，重复上述过程，直到图中全部的顶点都被访问到为止。
广度优先遍历图的特点是尽大概先举行横向搜刮，即开始访问的顶点的毗邻点也先被访问。为此，引入队列来生存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队列中，当队头顶点出队时，就访问其未被访问的毗邻点并令这些毗邻顶点入队。

1. void Bfs(Graph G)
2. {
3.         EdgeNode *t; int i,j,k;
4.         int visited[MaxN]={0};          //调用遍历算法前设置所有的顶点都没有被访问过
5.         initQueue(Q);                  //创建一个空队列
6.         for(i=0;i<G.Vnum;i++)
7.         {
8.                 if(!visited[i]){               //顶点i未被访问过
9.                         enQueue(Q,i);
10.                         printf("%d",i);visited[i]=1;    //访问顶点i并设置已访问标志
11.                         while(!isEmpty(Q)){            //若队列不空，则继续取顶点进行广度优先搜索
12.                                 deQueue(Q,k);
13.                                 t=G.Vertices[k].firstarc;
14.                                 for(;t;t=t->nextarc){      //检查所有与顶点K相邻接的顶点
15.                                         j=t->adjvex;           //顶点j是顶点k的一个邻接顶点
16.                                         if(visited[j]==0){     //若顶点j未被访问过，将j加入队列
17.                                                 enQUeue(Q,j);
18.                                                 printf("%d",j);    //访问序号为j的顶点并设置已访问标志
19.                                                 visited[j]=1;
20.                                         }
21.                                 }
22.                         }
23.                 }
24.         }
25. }

复制代码

2. 最小天生树求解算法

天生树：设图G=（V，E）是个连通图，如果其子图是一棵包罗G的全部顶点的树，则该子图称为G的天生树。
对于有n个顶点的连通图，至少有 n-1 条边，而天生树中恰好有 n-1条边，以是连通图的天生树是该图的极小连通子图。若在图的天生树中恣意加一条边，则一定形成回路。
图的天生树不是唯一的。对于非连通图而言，每个联通分量中的顶点集和遍历时走过的边集一起构成多少棵天生树，把它们称为非连通图的天生树丛林。
最小天生树：对于连通网来说，边是带权值的，天生树的各边也带权值，于是就把天生树各边的权值总和称为天生树的权,把权值最小的天生树称为最小天生树。求解最小天生树有很多现实的应用。普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两种常用的求解最小天生树算法。
普里姆(Prim)算法

克鲁斯卡尔(Kruskal)算法

3. 拓扑排序

在工程范畴，一个大的工程项目通常被分别为很多较小的子工程(称为运动)，当这些子工程都完成时，整个工程也就完成了。若以顶点表现运动，用有向边表现运动之间的优先关系,则称如许的有向图为以顶点表现运动的网(Activity On Vertex network,AOV 网)。在有向网中若从顶点                                       v                         i                                  v_i               vi​到顶点                                       v                         j                                  v_j               vj​有一条有向路径，则顶点                                       v                         i                                  v_i               vi​是                                       v                         j                                  v_j               vj​的前驱，顶点                                       v                         j                                  v_j               vj​是                                       v                         i                                  v_i               vi​的后继。若                              <                               v                         i                              ,                               v                         j                              >                          <v_i,v_j>               <vi​,vj​>是网中的一条弧，则顶点                                       v                         i                                  v_i               vi​是                                       v                         j                                  v_j               vj​的直接前驱，顶点                                       v                         j                                  v_j               vj​是                                       v                         i                                  v_i               vi​的直接后继。AOV 网中的弧表现了运动之间的优先关系，也可以说是一种运动举行时的制约关系。
在 AOV 网中不应出现有向环、回路若存在的话，则意味着某项运动必须以自身使命的完成为先决条件，显然这是谬妄的。因此，若要检测一个工程分别后是否可行，起首就应查抄对应的AOV 网是否存在回路。检测的方法是对其 AOV 网举行拓扑排序。

对一个有向图举行拓扑排序的效果会有两种环境：

• 一种是全部顶点已输出，此时整个拓扑排序完成，分析网中不存在回路;
  
• 另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法举行下去。
  

4. 最短路径算法

狄克斯特拉算法

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金