数据结构-10：图

基本概念

图用来描述对象之间的任意关系。顶点表示对象，边表示对象之间存在联系；如果联系有方向，就得到有向图；如果联系有代价，就得到带权图。和树相比，图允许回路，也允许一个顶点和许多顶点互相连接，因此遍历时必须记录访问状态，避免在环中无限走下去。

无向图

• 路径：在无向图 $G=(V,\{E\})$ 中由顶点 $v_i$ 至 $v_j$ 的顶点序列。
• 回路或环：第一个顶点和最后一个顶点相同的路径。
• 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
• 连通：顶点 vi 至 vj 之间有路径存在。
• 连通图：无向图 $G$ 的任意两点之间都是连通的，则称 $G$ 是连通图。
• 连通分量：极大连通子图。
• 完全图：有 $\frac{n(n-1)}{2}$ 条边的无向图。其中 $n$ 是结点个数。
• 生成树：极小连通子图。包含图的所有 $n$ 个结点，但只含图的 $n-1$ 条边。在生成树中添加一条边之后，必定会形成回路或环。

有向图

• 路径：在有向图 $G=(V,\{E\})$ 中由顶点 $v_i$ 经有向边至 $v_j$ 的顶点序列。
• 回路或环：第一个顶点和最后一个顶点相同的路径。
• 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
• 连通：顶点 vi 至 vj 之间有路径存在
• 强连通图：有向图 $G$ 中任意两个顶点 $v_i$、$v_j$ 都互相可达，则称 $G$ 是强连通图。
• 弱连通：有向图的基图（将有向边变成无向边后形成的图）是连通的。
• 强连通分量：极大强连通子图
• 有向完全图：有 $n(n-1)$ 条边的有向图。其中 $n$ 是结点个数。

其他术语

边的权值，邻接点，无向图结点的度，有向图结点的出度和入度。

图这一章最容易混淆的是“顶点之间是否有边”和“边的方向/权值”。无向图的一条边可以看作两个方向都可走；有向图的一条边只能按箭头方向走；带权图则在边上额外记录代价。后续算法的选择往往取决于这些属性：例如无权最短路径用 BFS，带非负权最短路径用 Dijkstra，依赖关系排序要求图是 DAG。

图的存储

图的存储方式主要在“空间占用”和“查询某条边是否存在的速度”之间取舍。邻接矩阵适合稠密图，判断边是否存在很快；邻接表适合稀疏图，只存真实存在的边，遍历某个顶点的邻接点更省空间。后续 DFS、BFS、拓扑排序等算法的复杂度，都会随存储方式不同而变化。

邻接矩阵

• 设有向图具有 $n$ 个结点，则用 $n$ 行 $n$ 列的布尔矩阵 $A$ 表示该有向图；如果 $i$ 至 $j$ 有一条有向边，$A[i, j] = 1$，如果 $i$ 至 $j$ 没有一条有向边，$A[i, j] = 0$。
• 设无向图具有 $n$ 个结点，则用 $n$ 行 $n$ 列的布尔矩阵 $A$ 表示该无向图；并且 $A[i, j] = 1$，如果 $i$ 至 $j$ 有一条无向边；$A[i, j] = 0$，如果 $i$ 至 $j$ 没有一条无向边。
• 加权图的邻接矩阵：如果 $i$ 至 $j$ 有一条边，则 $A[i, j] = w(i, j)$，其中 $w(i, j)$ 为边的权值；如果 $i$ 至 $j$ 没有一条边，则 $A[i, j] = noEdge$。这样可以避免把合法的 $0$ 权边和“无边”混淆。
• 代码实现

邻接矩阵的优点是判断两点之间是否有边非常直接，只需访问 edge[u][v]。缺点是无论实际边数多少，都要占用 $|V|^2$ 的空间。因此它更适合顶点数不太大、边比较密集，或者需要频繁判断任意两点是否相邻的场景。

template <class TypeOfVer, class TypeOfEdge>
class adjMatrixGraph:public graph<TypeOfVer, TypeOfEdge> {
public:
    adjMatrixGraph(int vSize, const TypeOfVer d[],
        const TypeOfEdge noEdgeFlag);
    void insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w);
    void remove(TypeOfVer x, TypeOfVer y);
    bool exist(TypeOfVer x, TypeOfVer y) const;
    ~adjMatrixGraph();
private:
    TypeOfEdge **edge;    //存放邻接矩阵
    TypeOfVer *ver;       //存放结点值
    TypeOfEdge noEdge;    //邻接矩阵中的∞值
    int find(TypeOfVer v) const {
        for (int i = 0; i < Vers; ++i)
            if (ver[i] == v) return i;
        return -1;
    }
};

template <class TypeOfVer, class TypeOfEdge>
adjMatrixGraph<TypeOfVer, TypeOfEdge>::adjMatrixGraph
(int vSize, const TypeOfVer d[], TypeOfEdge noEdgeFlag)
{
    int i, j;
    Vers = vSize;
    Edges = 0;
    noEdge = noEdgeFlag;  // 边不存在的标记，若边有权重，可设置特殊值。

    //存放结点的数组初始化
    ver = new TypeOfVer[vSize];
    for (i=0; i<vSize;++ i) ver[i] = d[i];

    //邻接矩阵初始化
    edge = new TypeOfEdge*[vSize];
    for (i=0; i<vSize; ++ i) {
        edge[i] = new TypeOfEdge[vSize];
        for (j=0; j<vSize; ++j) edge[i][j] = noEdge;
    }
}

template <class TypeOfVer, class TypeOfEdge>
void adjMatrixGraph<TypeOfVer, TypeOfEdge>::insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w)
{
    int u = find(x), v = find(y);
    if (u == -1 || v == -1) return;
    if (edge[u][v] == noEdge) ++Edges; // 只有新增边时才增加边数
    edge[u][v] = w;
}

//Remove：
template <class TypeOfVer, class TypeOfEdge>
void adjMatrixGraph<TypeOfVer, TypeOfEdge>::remove(TypeOfVer x, TypeOfVer y)
{
    int u = find(x), v = find(y);
    if (u == -1 || v == -1 || edge[u][v] == noEdge) return;
    edge[u][v] = noEdge;
    --Edges;
}

邻接表

• 空间 = 结点数 + 边数，时间 $O(|V| + |E|)$。
• 邻接表即每个结点存储一个链表，链表中存储与该结点相邻的结点。
• 代码实现

邻接表只保存真实存在的边，因此对稀疏图更省空间。遍历某个顶点的所有邻居也很自然，只需沿着该顶点的链表走一遍。但如果要判断任意两个顶点 x、y 是否有边，就必须先找到 x 的链表，再在链表中查找 y，不像邻接矩阵那样一步完成。

template <class TypeOfVer, class TypeOfEdge>
class adjListGraph:public graph<TypeOfVer, TypeOfEdge> {
public:
    adjListGraph(int vSize, const TypeOfVer d[]);
    void insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w);
    void remove(TypeOfVer x, TypeOfVer y);
    bool exist(TypeOfVer x, TypeOfVer y) const;
    ~adjListGraph() ;
private:
    struct edgeNode {      //邻接表中存储边的结点类
        int end;           //终点存储下标
        TypeOfEdge weight; //边的权值
        edgeNode *next;
        edgeNode(int e, TypeOfEdge w, edgeNode *n = NULL)
        { end = e; weight = w; next = n;}
    };

    struct verNode{      //保存顶点的数据元素类型
        TypeOfVer ver;   //顶点值
        edgeNode *head;  //对应的单链表的头指针
        verNode(edgeNode *h = NULL) { head = h;}
    };

    verNode *verList;
    int find(TypeOfVer v) const {
        for (int i = 0; i < Vers; ++i)
            if (verList[i].ver == v) return i;
        return -1;
    }
};

template <class TypeOfVer, class TypeOfEdge>
adjListGraph<TypeOfVer, TypeOfEdge>
::adjListGraph(int vSize, const TypeOfVer d[])
{
    Vers = vSize; Edges = 0;
    verList = new verNode[vSize];
    for (int i = 0; i < Vers; ++i) verList[i].ver = d[i];
}

template <class TypeOfVer, class TypeOfEdge>
adjListGraph<TypeOfVer, TypeOfEdge>::~adjListGraph()
{
    int i;
    edgeNode *p;
    for (i = 0; i < Vers; ++i) {
        while ((p = verList[i].head) != NULL) {
            verList[i].head = p->next;
            delete p;
        }
    }
    delete [] verList;
}

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::
insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w)
{
    int u = find(x), v = find(y);
    if (u == -1 || v == -1) return;
    verList[u].head = new edgeNode(v, w, verList[u].head );//插表头
    ++Edges;
}

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::remove(TypeOfVer x,TypeOfVer y)
{
    int u = find(x), v = find(y);
    if (u == -1 || v == -1) return;
    edgeNode *p = verList[u].head, *q;
    if (p == NULL) return; //结点u没有相连的边
    if (p->end == v) {     //单链表中的第一个结点就是被删除的边
        verList[u].head = p->next;
        delete p;
        --Edges;
        return;
    }
    while (p->next != NULL && p->next->end != v) p = p->next;//查找被删除的边
    if (p->next != NULL) { //删除
        q = p->next; p->next = q->next; delete q; --Edges;
    }//同链表删除
}

template <class TypeOfVer, class TypeOfEdge>
bool adjListGraph<TypeOfVer, TypeOfEdge>
::exist(TypeOfVer x, TypeOfVer y) const
{
    int u = find(x), v = find(y);
    if (u == -1 || v == -1) return false;
    edgeNode *p = verList[u].head;
    while (p !=NULL && p->end != v) p = p->next;
    if (p == NULL) return false; else return true;
}

深度优先搜索（dfs）

1. 选中第一个被访问的顶点；
2. 对顶点作已访问过的标志；
3. 依次从顶点的未被访问过的第一个、第二个、第三个…… 邻接顶点出发，进行深度优先搜索；
4. 如果还有顶点未被访问，则选中一个起始顶点，转向 2；
5. 所有的顶点都被访问到，则结束。

DFS 的行为像“先一路走到底，走不动再回退”。递归调用本身就是隐式栈：当前路径上的顶点会暂时停在调用栈中，直到它的邻居全部访问完毕才返回。外层 for 循环的作用是处理非连通图，如果某个连通分量已经遍历完，但还有顶点没访问，就从新的顶点重新启动一次 DFS。

代码实现

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::dfs() const
{
    bool *visited = new bool[Vers];
    int i;
    for (i = 0; i < Vers; ++i) visited[i] = false;
    cout << "当前图的深度优先遍历序列为：" << endl;
    for (i = 0; i < Vers; ++i) {
        if (visited[i] == true) continue;
        dfs(i, visited);//调用私有DFS函数
        cout << endl;
    }
    delete[] visited;
}

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::dfs
(int start, bool visited[]) const
{
    edgeNode *p = verList[start].head;
    cout << verList[start].ver << '\t';
    visited[start] = true;
    while (p != NULL){ //注意邻接表和邻接矩阵此处的实现细节
        if (visited[p->end] == false) dfs(p->end, visited); // 递归访问尚未访问的邻接点
        p = p->next; // 检查下一条邻接边
    }
}

效率分析

• 如果图是用邻接表来表示，则时间代价和顶点数 $|V|$ 及边数 $|E|$ 相关，即 $O(|V|+|E|)$。
• 如果图是用邻接矩阵来表示，则所需要的时间是 $O(|V|^2)$。

差异来自“找邻居”的方式。邻接表只遍历真实存在的边，所以稀疏图更省；邻接矩阵每访问一个顶点都要扫描整行，即使很多位置没有边也要检查。

广度优先搜索（bfs）

1. 记录每个结点是否已被访问。
2. 将当前被访问结点的后继结点，依次放入一个队列。
3. 重复取队列的队头元素进行处理，直到队列为空。对出队的每个元素，首先检查该元素是否已被访问。如果没有被访问过，则访问该元素，并将它的所有的没有被访问过的后继入队。
4. 检查是否还有结点未被访问。如果有，重复上述两个步骤.

BFS 的行为像“从起点一圈一圈向外扩散”。队列中保存的是已经发现但尚未展开邻居的顶点。由于队列先进先出，距离起点边数较少的顶点会先被处理，所以 BFS 可以直接用于无权图的最短路径层次搜索。

代码实现

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::bfs() const
{
    bool *visited = new bool[Vers];
    int currentNode, i;
    linkQueue<int> q;
    edgeNode *p;
    for (i = 0; i < Vers; ++i) visited[i] = false;
    cout << "当前图的广度优先遍历序列为："
         << endl;
    //记录每个结点是否已被访问
    for (i = 0; i < Vers; ++i)
    {
        if (visited[i] == true) continue;
        //此算法缺省从0下标结点开始遍历
        q.enQueue(i);
        while (!q.isEmpty())
        {
            currentNode = q.deQueue();
            if (visited[currentNode] == true) continue;
            cout << verList[currentNode].ver << '\t';
            visited[currentNode] = true;
            p = verList[currentNode].head;
            while (p != NULL)
            {
                if (visited[p->end] == false) q.enQueue(p->end);
                p = p->next;
            }
        }
        cout << endl;
    }
    delete[] visited;
}

效率分析

• 如果图是用邻接表来表示，则时间代价和顶点数 $|V|$ 及边数 $|E|$ 相关，即 $O(|V|+|E|)$。
• 如果图是用邻接矩阵来表示，则所需要的时间是 $O(|V|^2)$。

BFS 和 DFS 的复杂度形式相同，但访问顺序不同。DFS 借助递归栈沿一条路径深入，BFS 借助队列按层扩展；选择哪一种更多取决于问题需要路径深度信息还是层次距离信息。

拓扑排序

拓扑排序只适用于有向无环图（DAG）。它要做的不是按大小排序，而是在所有依赖关系都被满足的前提下，给顶点排出一个线性顺序。例如课程先修关系、任务依赖关系、编译依赖关系都可以用拓扑排序描述。如果图中存在环，环上的任务互相等待，就不可能得到合法拓扑序。

排序过程

1. 第一个输出的结点（序列中的第一个元素）：必须无前驱，即入度为 0。
2. 后驱：必须等到它的前驱输出之后才输出。
3. 无前驱及后件的结点：任何时候都可输出。
4. 逻辑删除法：当某个节点被输出后，就作为该节点被删除。所有以该节点作为前驱的所有节点的入度减 1。

排序实现

1. 计算每个结点的入度，保存在数组 inDegree 中；
2. 检查 inDegree 中的每个元素，将入度为 0 的结点入队；
3. 不断从队列中将入度为 0 的结点出队，输出此结点，并将该结点的后继结点的入度减 1；如果某个邻接点的入度为 0，则将其入队。

拓扑排序可以理解为不断挑选“当前没有前置依赖”的任务。inDegree 记录每个顶点还有多少前驱没有被输出；当一个顶点出队并输出时，相当于这项任务完成了，因此它指向的后继顶点少了一个未完成前驱。若最后输出数量少于顶点数，说明剩下的顶点互相依赖，图中存在环。

代码实现

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::topSort( ) const
{
    linkQueue<int> q;
    edgeNode *p;
    int current, i, outputCount = 0, *inDegree = new int[Vers];
    for (i = 0; i < Vers; ++i) inDegree[i] = 0;
    for (i = 0; i < Vers; ++i)
        for (p = verList[i].head; p != NULL; p = p->next)
            ++inDegree[p->end];
    for (i = 0; i < Vers; ++i) if (inDegree[i] == 0) q.enQueue(i);
    cout << "拓扑排序为：" << endl;
    while( !q.isEmpty( ) ){
        current = q.deQueue( );
        ++outputCount;
        cout << verList[current].ver << '\t';
        for (p = verList[current].head; p != NULL; p = p->next)
            if( --inDegree[p->end] == 0 ) q.enQueue( p->end );
    }
    if (outputCount < Vers) cout << "存在环，无法得到完整拓扑序列";
    cout << endl;
    delete[] inDegree;
}

效率分析

• 如果图以邻接表表示，计算入度需要 $O(|V|+|E|)$ 的时间，搜索入度为 $0$ 的结点需要 $O(|V|)$ 的时间。每个结点入一次队、出一次队。每出一次队，需要检查它的所有后继结点，因此也需要 $O(|V|+|E|)$ 的时间。所以总的执行时间也是 $O(|V|+|E|)$。

如果最终输出的顶点数少于 $|V|$，说明仍有顶点因为环而无法变成零入度，这时图不存在合法拓扑序。

关键路径

关键路径用于分析带持续时间的工程网络：哪些活动决定了整个工程最短完成时间，哪些活动有延迟余量。它建立在拓扑序之上，因为只有在依赖关系无环时，才能从起点向终点逐步计算最早时间，再从终点反向计算最迟时间。

如果某条活动的最早开始时间和最迟开始时间相同，就说明它没有可拖延空间；这类活动串起来就是关键路径。关键路径上的任何延误都会直接推迟整个工程完成时间。

关键路径的概念

• AOE 网络：顶点表示事件，有向边的权值表示某个活动的持续时间，有向边的方向表示事件发生的先后次序。
• AOE 网络可用于描述整个工程的各个活动之间的关系，活动安排的先后次序。在此基础上，可以用来估算工程的完成时间以及那些活动是关键的活动。
• 完成整项工程至少的时间：起点到终点的最长路径，即关键路径。
• 影响工程进度的活动：活动时间余量为 0 的活动，称为关键活动。

利用正向拓扑排序求事件结点（顶点）最早发生时间

• 利用拓扑排序算法求事件结点的最早发生时间的执行步骤：

1. 设每个结点（始发边）的最早发生时间为 $0$，将入度为零的结点进栈。
2. 将栈中入度为零的结点 $V$ 取出，并压入另一栈，用于形成逆向拓扑排序的序列。
3. 根据邻接表找到结点 $V$ 的所有的邻接结点，将“结点 $V$ 的最早发生时间 + 活动的权值”得到的和同邻接结点的原最早发生时间进行比较；如果该值大，则用该值取代原最早发生时间。另外，将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。
4. 反复执行 2、3；直至栈空为止。

关键路径寻找过程

• 找出每个顶点的最早发生时间和最迟发生时间
• 最早发生时间：每个直接前驱的最早发生时间加上从该前驱到该顶点的活动时间的最大者（正向拓扑排序）
• 最迟发生时间：每个直接后继的最迟发生时间减去顶点到该直接后继的活动时间的最小者就是该顶点的最迟发生时间。（逆向拓扑排序：可以理解为将图中的箭头全部取反，以结束事件为起点进行正向拓扑排序，时间从最早发生时间开始减去权值）
• 找出两个时间相等的顶点就是关键路径上的顶点。

关键路径的直觉是：某些事件没有任何时间余量，只要它们延迟，整个工程就一定延迟。ee 表示事件最早能在什么时候发生，是从起点向终点推出来的最长前缀时间；le 表示不影响总工期的前提下最晚能什么时候发生，是从终点沿逆拓扑序反推出来的时间。若 ee[v] == le[v]，说明顶点 v 没有浮动空间。

算法实现

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>
::criticalPath( ) const
{
    TypeOfEdge *ee = new TypeOfEdge[Vers],
               *le = new TypeOfEdge[Vers];
    int *top = new int[Vers], *inDegree = new int[Vers];
    TypeOfEdge projectLength;
    linkQueue<int> q;
    int i;
    edgeNode *p;

    // 找出拓扑序列，放入数组top
    for (i = 0; i < Vers; ++i) inDegree[i] = 0;
    for (i = 0; i < Vers; ++i) { //计算每个结点的入度
        for (p = verList[i].head; p != NULL; p = p->next)
            ++inDegree[p->end];
    }
    for (i = 0; i < Vers; ++i) //将入度为0的结点入队
        if (inDegree[i] == 0) q.enQueue(i);

    i = 0;
    while( !q.isEmpty( ) ) {
        top[i] = q.deQueue( ); // 记录拓扑序中的下一个顶点
        for (p = verList[top[i]].head; p != NULL; p = p->next)
            if( --inDegree[p->end] == 0 ) q.enQueue( p->end );
        ++i;
    }
    if (i < Vers) {
        cout << "图中存在环，无法求关键路径" << endl;
        delete[] ee; delete[] le; delete[] top; delete[] inDegree;
        return;
    }

    // 找最早发生时间
    for (i = 0; i < Vers; ++i) ee[i] = 0;
    for (i = 0; i < Vers; ++i) { // 找出最早发生时间存于数组ee
        for (p = verList[top[i]].head; p != NULL; p = p->next)
            if (ee[p->end] < ee[top[i]] + p->weight )
                ee[p->end] = ee[top[i]] + p->weight;
    }

    // 找最晚发生时间
    projectLength = ee[top[Vers - 1]];
    for (i = 0; i < Vers; ++i)
        if (ee[i] > projectLength) projectLength = ee[i];
    for (i = 0; i < Vers; ++i) le[i] = projectLength;
    for (i = Vers - 1; i >= 0 ; --i) // 找出最晚发生时间存于数组le
        for (p = verList[top[i]].head; p != NULL; p = p->next)
            if(le[p->end] - p->weight < le[top[i]] )
                le[top[i]] = le[p->end] - p->weight;

    // 找出关键路径
    for (i = 0; i < Vers; ++i)
        if (le[top[i]] == ee[top[i]])
            cout << "(" << verList[top[i]].ver
                 << ", " << ee[top[i]] << ") ";
    delete[] ee; delete[] le; delete[] top; delete[] inDegree;
}