数据结构与算法：图

图论是计算机研究的一个重要分支，有关图论的内容可以写很多，但正是因为图论的这种复杂性，在程序员面试笔试中，有关图论的问题并不多见，考察的也并不深奥。本节内容涉及一些经常出现的图论问题，并给予详细的解答。

• 拓扑排序
• 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

最常见的图的遍历方式有深度优先遍历（Depth First Search，DFS）与广度优先遍历（Breadth First Search， BFS）两种。图的深度优先算法类似于树的先根遍历，图的广度优先算法类似于树的层次遍历。

DFS

DFS是从每一个顶点开始的深度优先遍历，结果都是对该分支路径深入遍历到不能再深入为止，且每个顶点只能被访问一次。具体实现过程为从图G中某个顶点v触发，先访问该结点，然后一次沿着未被访问过的v的邻接顶点进行深度优先遍历，直到图G中和顶点v之间有相连路径的其他顶点都被访问过为止。此时，如果图G中还有其他顶点未被访问过，则从这些顶点中任选一个作为起始顶点，重复上述过程，直到图G中的所有顶点都被访问过为止。

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

int visited[N]; //数组 visited[]表示图中顶点的访问情况，1表示已访问，0表示未访问
void DFS( Graph G, int v )
{
    visited[v] = ;
    Visit(v); //表示对顶点v的访问

    //函数FirstAdjVex( G,v ) 返回图G中v的第一个邻接点
    //函数NextAdjVex( G,v,w )返回图G中v的（相对于w）的下一个邻接顶点，若w是v的最后一个邻接点，则返回空
    for(w=FirstAdjVex(G,v);w>=;w=NextAdjVex(G,v,w))
    {
        if(!visited[w])
            DFS(G,w); //对v的未被访问过的邻接顶点进行深度优先搜索
    }
}
void DFSSearch( Graph G )//对图G进行深度优先搜索
{
    for(v=;v<G.vexnum; ++v)
        visited[v] = ;
    for( v=;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=; v<G.vexnum; ++v )
        visited[v] = ;
    InitQueue( Q ) //初始化队列
    for( v=; v<G.vexnum; ++v )
        if( !visited[v])
        {
            visited[v] = ;
            Visit( v );
            EnQueue( Q,v );
            while( !QueueEmpty(Q) )
            {
                Dequeue( Q,u ); //出队
                for( w=FirstAdjVex(G,u); w>=; w=NextAdjVex(G,u,w) ) 
                    if(!visited[w])
                    {
                        visited[w] = ;
                        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)