数据结构与算法分析学习笔记(7)

图

如果在一个无向图中从每一个顶点到每个其他顶点都存在一条路径，则称该无向图是连通的。具有这样性质的有向图是强连通的。

图的两种表示方法邻接矩阵和邻接表的方法适用于稠密图和稀疏图；

拓扑排序不是唯一的，任意合理的排序都是可以的；

简单的求拓扑的算法是：先找出任意一个没有入边的顶点，然后显示出该顶点，并将它和它的边一起从图中删除，然后，我们对图的其余部分应用同样的方法处理。

 1 //简单的拓扑排序的伪码
 2 void TopSort(Graph G)
 3 {
 4     int Counter;
 5     Vertex V,W;
 6     for(Counter=0;Counter<NumVertex;Counter++)
 7         {
 8             V=FindNewVertexOfIndegreeZero();
 9             if(V==NotAVertex)//如果没有入度为0的节点
10             {
11                 Error("Graph has a cycle");
12                 break;
13             }
14             TopNum[V]=Couner;
15             for each W adjacent to V
16                 Indegree[W]--;
17         }
18 }
19 //该算法寻找入度为0的节点是对Indegree数组的扫描，一共有v次这样的调用，所以时间复杂度为O(V²)；
20 //通过改变保存入度为0节点的改造，加入队列，提高效率；
21 void TopSort(Graph G)
22 {
23     Queue Q;
24     int Counter=0;
25     Vertex V,W;
26     Q=CreateQueue(NumVertex);
27     MakeEmpty(Q);
28     for each Vertex V
29         if(Indegree[V]==0)
30             EnQueue(V,Q);
31     while(!IsEmpty(Q))
32         {
33             V=Dequeue(Q);
34             TopNum[V]=++Counter;
35             for each W adjacent to V
36                 if(--Indegree[w]==0)
37                     Enqueue(W,Q);
38         }
39     if(Counter!=NumVertex)
40         Error("has a cycle");
41     DisposeQueue(Q);
42 }
43 //如果使用邻接表，那么执行此算法的时间是O（E+V）

最短路径算法

给定一个赋权图G=（V,E）和一个顶点S作为输入，找出S到G中每个其他顶点的最短路径；

当前还不存在找出从S到一个顶点的路径比找出S到所有顶点路径更快的算法；

广度优先遍历算法：距开始点最近的那些顶点首先被赋值，而最远的那些顶点最后被赋值。类似于树的层次遍历；

 1 //无权最短路算法的伪代码
 2 void Unweight(Table T)//T has been initialized
 3 {
 4     int CurrDist;
 5     Vertex V,W;
 6     for(CurrDist=0;CurrDist<NumVertex;CurrDist++)
 7         for each vertex V
 8             if(!T[V].Known&&T[V].Dist==CurrDist)
 9                 {
10                     T[V].Known=True;
11                     for each W adjacent to V
12                     if(T[W].Dist==Infinity)
13                     {
14                         T[W].Dist=CurrDist+1;
15                         T[W].Path=V;
16                     }
17                 }
18 }

使用邻接表，运行时间是O(E+V)；

解决单源最短路径问题的一般方法叫做Dijskstra算法；（类似贪婪算法）

Edit By SolarJupiter

数据结构与算法分析 学习笔记(7)

数据结构与算法分析学习笔记(7)