图论是计算机研究的一个分支可以写很多关于图论，但图理论的复杂性，程序员面试笔试，也没有有关的许多问题对图论，调查并不深奥。本节介绍大量的图论中的经常性问题，并给出详细的答案。

拓扑排序 DFS BFS DFS BFS 关键路径最短路径

从数学的角度看，拓扑排序被通过任何集总序关系的集合操作上的偏序关系。如果作为节点的图，作为边缘，集上的偏序然后任何偏序集合中的所有元素可以都代表一个有向的图。

拓扑排序是一个有向的图的重要操作。给定一个有向的图 g 和顶点序列 V1、 v2、……，VN 符合下列条件 ︰ 如果在总有向的图 g 是从顶点 VI 和 VJ 前顶点 VI VJ 顶点序列中, 的路径是指此序列作为拓扑序列。一遇到拓扑序列，它是拓扑排序。

图的拓扑排序，可以视为所有顶点沿水平线和成使所有定向的边缘从左到右的序列图中。在许多应用中，用有向无环图来说明事件发生的顺序。

常见的拓扑排序方法如下所示 ︰
（1） 选择没有前驱体中 （在中度 0） 有向的图的顶点和输出它。
（2） 由删删去从顶点顶点从图和各方面的问题。
（3） 重复步骤 （1） 和 (2)，直到目前为止当前的有向的图有是没有前兆的顶点节点或当前的定向关系图中的所有节点都有都输出到目前为止。

需要注意的是一连串的拓扑排序的指示有向无环图并不是唯一。

例如，对于 13-20，拓扑排序将两个序列: {V1、 v2、 V5，v4，v3，v7，V6} 或 {v1、 v2、 V5，v4，v7，v3，V6}

从拓扑排序算法，AOV 网与 n 顶点 e 的边缘，在拓扑排序过程中，搜索到零摄氏度，与顶点生成顶点堆栈所需的时间是 o (n)。在正常情况下，一个有向图具有 n 顶点，每个顶点到堆栈，堆栈，总输出 n 次。顶点到减 1 操作已经执行了 e 时代。因此，拓扑排序的总的时间复杂度为 o (n + e)。

最常见的图形遍历深度优先遍历 （深度优先搜索，DFS） 和广度优先遍历 （广度优先搜索，BFS） 两种方式。类似于树的深度优先算法、 广度优先算法的前序遍历是类似于分层遍历树。

DFS

DFS 是从开始的每个顶点的深度优先遍历，结果是分支路径去不到目前为止，深度遍历和每个顶点只能进行一次访问。执行进程，从图 g 的顶点 v 触发第一次访问节点又不访问沿深度优先遍历的相邻顶点的 v 图 g 和顶点 v 连接到其他路径的顶点的之前经历过为止。在这一点上，如果有其他的图 g 的顶点不从这些顶点作为起点，任何一个访问重复上述过程，直到在图 g 的所有顶点到目前为止都访问。

深度优先搜索算法的具体实现的代码如下所示 ︰

BFS

BFS 也称为广度优先算法，是一种盲目的搜索方法，算法的原型是重要。它的层的层的目标搜索所有顶点在图中，并确保在图表中的所有顶点都只有一次都访问。

int visited[N]; //数组 visited[]表示图中顶点的访问情况，1表示已访问，0表示未访问 void DFS( Graph G, int v ) {     visited[v] = 1;     Visit(v); //表示对顶点v的访问      //函数FirstAdjVex( G,v ) 返回图G中v的第一个邻接点     //函数NextAdjVex( G,v,w )返回图G中v的（相对于w）的下一个邻接顶点，若w是v的最后一个邻接点，则返回空     for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))     {         if(!visited[w])             DFS(G,w); //对v的未被访问过的邻接顶点进行深度优先搜索     } } void DFSSearch( Graph G )//对图G进行深度优先搜索 {     for(v=0;v<G.vexnum; ++v)         visited[v] = 0;     for( v=0;v<G.vexnum; ++v)         if(!visited[v])             DFS(G,v); //对未被访问过的顶点调用DFS }

BFS

BFS也称为宽度优先算法，属于一种盲目搜索方法，是很重要的图算法的原型。其目的是逐层搜索图中的所有顶点，且保证图中的所有顶点只被访问过一次。

具体过程如下：在给定图G=（V,E）中，从图G中的某个顶点v出发，访问该顶点后，依次访问所有未被访问过的v的邻接顶点，然后再沿着这些顶点出发，依次访问它们未被访问过的邻接顶点，并且保证先被访问顶点的邻接顶点先于后被访问顶点的邻接顶点而被访问。所有与顶点v有相通路径的顶点都被访问结束后，如果图G中还有其他顶点未被访问过，则从这些顶点中任选一个顶点作为起始顶点，重复上述过程，直到图G中的所有顶点都被访问过为止。

广度优先搜索算法的具体实现代码如下：

int visited[N];//表示顶点的访问情况，1表示已访问，0表示未访问 void BFSSearch( Graph G ) {     for(v=0; v<G.vexnum; ++v )         visited[v] = 0;     InitQueue( Q ) //初始化队列     for( v=0; v<G.vexnum; ++v )         if( !visited[v])         {             visited[v] = 1;             Visit( v );             EnQueue( Q,v );             while( !QueueEmpty(Q) )             {                 Dequeue( Q,u ); //出队                 for( w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w) )                      if(!visited[w])                     {                         visited[w] = 1;                         Visit(w);                         EnQueue(Q,w);                     }              }         } }

关键路径

关键路径是指一个图（AOE）中长度最长（路径上的各个活动所持续的时间之和）的路径。
用e(k)表示活动（即弧）k的最早开始时间
用l(k)表示活动k的最晚开始时间，则把e(k) = l(k)的活动叫做关键活动。关键路径上的所有活动都为关键活动。
由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。

用ve(i)表示事件（即顶点）i的最早开始时间，vl(i)表示事件i的最晚开始时间。如果活动k由弧<m,n>表示，用dut表示该活动的持续时间，则有：

e(k) = ve(m) l(k)=vl(n)-dut(<m,n>)

求解关键路径的具体算法如下（假设图中共有n个顶点）：
（1）从开始顶点v0出发，假设ve(0)=0，然后按照拓扑有序求出其他各顶点i的最早开始时间ve(i)，如果得到的拓扑序列中顶点数目小于图中的顶点数，则表示图中存在回路，算法结束，否则继续执行。
（2）从结束顶点vn出发，假设v1(n-1)=ve(n-1)，然后按拓扑有序求出其他各顶点i的最晚发生时间vl(i)
（3）根据各顶点的最早开始时间ve(i)和最晚开始时间vl(i)依次求出每条弧的最早开始时间e(k)和最晚开始时间l(k)，如果有e(k)=l(k),则为关键活动。关键活动组成的路径则为关键路径。

最短路径

Dijkstra算法原理是对于源顶点v0，首先选择其直接相邻的顶点中长度最短的顶点vi，那么根据已知可得，由v0经过vi到达与vi直接相邻的顶点vj的最短距离dist[j]为matrix[v0][j]与dist[i]+matrix[i][j]中的最小值，即dist[j]=min{ matrix[v0][j], dist[i]+matrix[i][j]}

该算法的实现过程如下（S是已求得最短路径的终点集合，V是所有结点集合）
（1）V-S = 未确定最短路径的顶点的集合，初始时 S={A}，两个结点之间没有边时表示这两点之间的路径长度为无限大
（2）下一条路径的计算方式：首先，求出A到Vi中间只经S中顶点的最短路径，其中，Vi 属于 V-S。然后，将上述的到最短路径与源点A到结点Vi的路径长度进行比较，长度最小者即为源点A到结点Vi的最短路径。最后将所求最短路径的终点（即Vi）加入S中
（3）重复步骤（2），直到求出所有终点的最短路径，即S中的结点数量与V中的结点数量相等。

Dijkstra算法的时间复杂度为O(n^2)，空间复杂度取决于存储方式，邻接矩阵为O(n^2)

除了Dijkstra算法外，Bellman-Ford算法也是一种常见的求解单源最短路径问题的算法。与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数，它的时效性比较好，时间复杂度为O(VE)