【大话数据结构】第七章-图_有向图的生成树

七、图

1.图的定义

图 (Gragh) 是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

对于图的定义，需要注意几个地方：

• 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素我们称之为顶点（Vertex）。
• 线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。而图中，不允许没有顶点。
• 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

1.1 各种图定义

无向边：若顶点v_i到v_j之间的边没有方向，则称这条边为无向边 (Edge)，用无序偶对(v_i, v_j)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。如下图就是一个无向图，由于是无方向的，连接顶点A与D的边，可以表示成无序对(A,D)，也可以写成(D,A)。

对于此无向图G₁来说，G₁=(V₁,{E₁})，其中顶点集合V₁={A,B,C,D}；边集合E₁={ (A,B) , (B,C) , (C,D) , (D,A) , (A,C) }。

有向边：若从顶点v_i到v_j的边有方向，则称这条边为有向边，也称为弧(Arc)。用有序偶<v_i, v_j>来表示，v_i称为弧尾(Tail)，v_j称为弧头(Head)。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。如下图就是一个有向图。连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A, D>表示弧，注意不能写成<D, A>。

对于此有向图G₂来说，G₂=(V₂,{E₂})，其中顶点集合V₂={A,B,C,D}；弧集合E₂={ <A,D> , <B,A> , <C,A> , <B,C> }。

注：无向边用小括号"()“表示，而有向边用尖括号”<>"表示。

==在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。==这里我们只讨论简单图，下面两种图不属于我们要讨论范畴。

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n×(n-1)/2条边。如下图。

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n×(n-1)条边，如图。

有很少条边或弧的图称为稀疏图，反之称为稠密图。

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。下图就是一张带权的图。

假设有两个图G1=(V1,{E2})和G2=(V2,{E2})，如果V1包含于V2且E1包含于E2，则称G1为G2的子图。如下图带底纹的图均为左侧无向图与有向图的子图。

1.2 图顶点与边间关系

对于无向图G=(V,{E})，如果边(v₁,v₂)∊E，则称顶点v₁和v₂互为邻接点，即v₁和v₂相邻接。边(v₁,v₂)依附于顶点v₁和v₂，或者说(v₁,v₂)与顶点v₁和v₂相关联。顶点v₁的度是和v₁相关联的边的数目，记为TD(v₁)。

对于有向图G=(V,{E})，如果弧<v₁,v₂>∊E，则称顶点v₁邻接到顶点v₂，顶点v₂邻接自顶点v₁。弧<v₁,v₂>和顶点v₁，v₂相关联。以顶点v为头的弧的数目称为v的入度，记为ID(v)；以v为尾的弧的数目称为v的出度，记为OD(v)；顶点v的度为TD(v) = ID(v) + OD(v)。

无向图G=(V,{E})中从顶点v₁到顶点v₂的路径是一个顶点序列（v₁=v_i,0,v_i,1···,v_i,m=v₂），其中(v_i,j-1,v_i,j)∊E，1≤j≤m。

路径的长度是路径上的边或弧的数目。

第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

1.3 连通图相关术语

在无向图G中，如果从顶点v₁到顶点v₂有路径，则称v₁和v₂是连通的。如果对于图中任意两个顶点v_i、v_j∊V，v_i和v_j都是连通的，则称G是连通图。无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调：

• 要是子图
• 子图要是连通的
• 连通子图含有极大顶点数
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

在有向图G中，如果对于每一对v_i、v_j∊V、v_i≠v_j，从v_i到v_j和从v_j到v_i都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

现在我们再来看连通图的生成树定义。

所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。对有向树的理解比较容易，所谓入度为0其实就相当于树中的根结点，其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

1.4 图的定义与术语总结

图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。

图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。

图上的边或弧上带权则称为网。

图中顶点存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环。当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。

无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

2.图的抽象数据类型

ADT 图（Graph）
Data
    顶点的有穷非空集合和边的集合。
Operation
    CreateGragh(*G,V,VR): 按照顶点集V和边弧集VR的定义构造图G
    DestroyGragh(*G): 图G存在则销毁
    LocateVex(G,u): 若图G中存在顶点u，则返回图中的位置
    GetVex(G,v): 返回图G中顶点v的值
    PutVex(G,v,value): 将图G中顶点v赋值value
    FirstAdjVex(G,*v): 返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空
    NextAdjVex(G,v,*w): 返回顶点v相对于顶点w的下一个邻接顶点，若w是v的最后一个邻接点则返回“空”
    InsertVex(*G,v): 在图G中增添新顶点v
    DeleteVex(*G,v): 删除图G中顶点v及其相关的弧
    InsertArc(*G,v,w): 在图G中增添弧<v,w>，若G是无向图，还需要增添对称弧<w,v>
    DeleteArc(*G,v,w): 在图G中删除弧<v,w>，若G是无向图，还需要删除对称弧<w,v>
    DFSTraverse(G): 对图G中进行深度优先遍历，在遍历过程对每个顶点调用
    HFSTraverse(G): 对图G中进行广度优先遍历，在遍历过程对每个顶点调用
endADT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.图的存储结构

3.1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

对于无向图：

对于有向图：

对于带有权的网图：

邻接矩阵存储的结构代码：

typedef char VertexType;             // 顶点类型应由用户定义
typedef int EdgeType;                // 边上的权值类型应由用户定义
#define MAXVEX 100                   // 最大顶点数，应由用户定义
#define INFINITY 65535               // 用65535来代表∞
typedef struct {
    VertexType vexs[MAXVEX];         // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];    // 邻接矩阵，可看作边表
    int numVertexes, numEdges;       // 图中当前的顶点数和边数
}MGragh;
1
2
3
4
5
6
7
8
9

无向网图的创建代码：

void CreateMGragh(MGragh *G) {
    int i,j,k,w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVertexes, &G->numEdges);
    for (i=0; i<G->numVertexes; i++)
        scanf(&G->vexs[i]);
    for (i=0; i<G->numVertexes; i++)
        for (j=0; j<G->numVertexes; j++)
            G->arc[i][j] = INFINITY;            // 邻接矩阵初始化
    for (k=0; k<G->numEdges; k++) {             // 读入 numEdges 条边，建立邻接矩阵
        printf("输入(vi, vj)上的下标i，下标j和权w:\n");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];            // 因为是无向图，矩阵对称
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2 邻接表

由于对于边数相对顶点较少的图，使用邻接矩阵会浪费存储空间。所以对于这种情况的图，我们可以使用邻接表。邻接表是一种数组与链表相结合的存储方法。

对于无向图：

对于有向图：

对于带权值的网图：

邻接表存储的结构代码：

typedef char VertexType;               // 顶点类型应由用户定义
typedef int EdgeType;                  // 边上的权值类型应由用户定义

typedef struct EdgeNode {              // 边表结构
    int adjvex;                        // 邻接点域，存储该顶点对应的下标
    EdgeType weight;                   // 用于存储权值，对于非网图可以不需要
    struct EdgeNode *next;             // 链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode {            // 顶点表结点
    VertexType data;                   // 顶点域，存储顶点信息
    EdgeNode *firstedge;               // 边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes,numEdges;          // 图中当前顶点数和边数
}GraphAdjList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

无向图的邻接表创建代码：

void CreateALGraph(GraphAdjList *G) {
    int i,j,k;
    EdgeNode *e;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVertexes,&G->numEdges);     // 输入顶点数和边数
    for (i=0; i<G->numVertexes; i++) {               // 读入顶点信息，建立顶点表
        scanf(&G->adjList[i].data);                  // 输入顶点信息
        G->adjList[i].firstedge = NULL;              // 将边表置为空表
        for (k=0; k<G->numEdges; k++) {              // 建立边表
            printf("输入边(vi,vj)上的顶点序号:\n");
            scanf("%d,%d",&i,&j);                    // 输入边 (vi,vj) 上的顶点序号
            /* 头插法 */
            e = (EdgeNode *)malloc(sizeof(EdgeNode));// 向内存申请空间，生成边表结点
            e->adjvex = j;                           // 邻接序号为j
            e->next = G->adjList[i].firstedge;       // 将e指针指向当前顶点指向的结点
            G->adjList[i].firstedge = i;             // 将当前顶点的指针指向e
            
            e = (EdgeNode *)malloc(sizeof(EdgeNode));
            e->adjvex = i;
            e->next = G->adjList[j].firstedge;
            G->adjList[j].firstedge = j;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.3 十字链表

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之逆邻接表解决了入度却不了解出度的情况。所以我们可以使用十字链表把邻接表与逆邻接表结合起来。

顶点表结构如表：

其中，firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

边表结点结构如表：

其中，tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指出边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

如上图，实线箭头指针与之前邻接表相同，这里重点解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于v₀来说，它有两个顶点v₁和v₂的入边，因此v₀的firstin指向顶点v₁的边表结点中headvex为0的结点，如图中①，接着由入边结点的headlink指向下一个入边顶点v₂，如图中②。

十字链表的好处就是把邻接表和逆邻接表整合在一起，这样既容易找到以v_i为尾的弧，也容易找到以v_i为头的弧，因而容易求得顶点的出度和入度。

3.4 邻接多重表

在无向图的应用中，当关注的重点是顶点时，使用邻接表，但当关注的重点是边的操作时，使用邻接多重表更好。

边表结点结构如表：

其中，ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。

如上图，首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同，这样好理解。接着，由于顶点v₀的(v₀,v₁)边的邻边有(v₀,v₃)和(v₀,v₂)。因此⑤⑥的连线就是满足指向下一条依附于顶点v₀的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。

3.5 边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成，如下图。

显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边一次进行处理的操作，而不适合对顶点相关的操作。关于边集数组的应用将在本章后面克鲁斯卡尔(Kruskal)算法中有介绍，这里略。

边数组结构如表：

其中，begin是存储起点下标，end是存储终点下标，weight是存储权值。

4.图的遍历

图的遍历和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。

图的遍历很复杂，因为它的任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此我们需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1。

4.1 深度优先遍历

深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称DFS。

举个例子，我们要求在下左图的迷宫中，从顶点A开始走遍所有的图顶点并作上标记，注意不是简单地看着这样的平面图走，而是如同现实般地在只有高墙和通道的迷宫中去完成任务。

首先我们从顶点A开始，做上标记后，面前有两条路，通向B和F，我们给自己定一个原则，在没有碰到重复顶点的情况下，始终是向右边走，于是走到了B顶点。整个行路过程可以看上右图。此时发现有三条分支，分别通向顶点C、I、G，右手通行原则，使得我们走到了C顶点。就这样，我们一直顺着右手通道走，一直走到F顶点。当我们依然选择右手通道走过去后，发现走回到顶点A了，此时我们退回顶点F，走向从右数的第二条通道，到了顶点G，它有三条通道，发现B和D都已经走过了，于是走到H，当我们面对通向H的两条通道D和E时，发现都已经走过了。

此时我们还没有遍历所有的顶点，所以我们按原路返回。在顶点H处，返回到G，再返回到F，接着返回到E，有一条通往H的通道，验证后再返回到D发现I还没走过，于是走到I标记，后面继续返回，直到返回到A，便完成了遍历任务。

我们会发现，深度优先遍历其实就是一个递归的过程，我们还会发现，转换成上右图后，其实就是一棵树的前序遍历，它从图中某个顶点V出发，访问此顶点，然后从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。

如果我们用的是邻接矩阵的方式，则代码如下：

int visited[MAX];              // 访问标记数组
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGragh G) {
    int i;
    for (i=0; i<G.numVertexes; i++)
        visited[i] = 0;        // 初始化所有顶点为未访问状态
    for (i=0; i<G.numVerteses; i++)
        if (!visited[i])       // 对未访问过的顶点调用DFS，若是连通图，只会执行一次
            DFS(G, i);
}

/* 邻接矩阵的深度优先递归算法 */
void DFS(MGragh G, int i) {
    int j;
    visited[i] = 1;
    printf("%c", G.vexs[i]);   // 打印顶点，也可以其他操作
    for (j=0; j<G.numVertexes; j++)
        if (G.arc[i][j] == 1 && !visited[j])
            DFS(G, j);         // 对未访问的邻接顶点递归调用
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

如果图结构是邻接表结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下：

/* 邻接表的深度遍历操作 */
void DFSTraverse(GraghAdjList GL) {
    int i;
    for (i=0; i<GL->numVertexes; i++)
        visited[i] = 0;         // 初始化所有顶点为未访问状态
    for (i=0; i<GL->numVertexes; i++)
        if (!visited[i])        // 对未访问过的顶点调用DFS，若是连通图，只会执行一次
            DFS(G, i);
}

/* 邻接表的深度优先递归算法 */
void DFS(GraghAdjList GL, int i) {
    EdgeNode *p;
    visited[i] = 1;
    printf("%c", GL->adjList[i].data);  // 打印顶点，也可以其他操作
    p = GL->adjList[i].firstedge;
    while (p) {
        if (!visited[p->adjvex])
            DFS(GL, p->adjvex);         // 对未访问的邻接顶点递归调用
        p = p->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(n²)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图，邻接表结构使得算法在时间效率上大大提高。

对于有向图而言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。

4.2 广度优先遍历

广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层次遍历。我们将下左图稍微变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将与这四个顶点有边的D、H放在第四层，如下右图。此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。

以下是邻接矩阵结构的广度优先遍历算法：

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGragh G) {
    int i,j;
    Queue Q;
    for (i=0; i<G.numVertexes; i++)
        visited[i] = 0;
    InitQueue(&Q);                     // 初始化一个辅助用的队列
    for (i=0; i<G.numVertexes; i++) {  // 对每一个顶点做循环
        if (!visited[i]) {
            visited[i] = 1;            // 设置当前顶点访问过
            printf("%c", G.vexs[i]);   // 打印顶点，也可以其他操作
            EnQueue(&Q, i);            // 将此顶点入队列
            while (!QueueEmpty(Q)) {   // 若当前队列不为空
                DeQueue(&Q, &i);       // 将队中元素出队列，赋值给i
                for (j=0; j<G.numVertexes; j++) {
                    /* 判断其他顶点若与当前顶点存在边且未访问过 */
                    if (G.arc[i][j] == 1 && !visited[j]) {
                        visited[j] = 1;  // 将找到的此顶点标记为已访问
                        printf("%c", G.vexs[j]); // 打印顶点
                        EnQueue(&Q, j);  // 将找到的此顶点入队列
                    }
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

对于邻接表的广度优先遍历，代码与邻接矩阵差异不大，代码如下：

/* 邻接表的广度遍历算法 */
void BFSTraverse(GraghAdjList GL) {
    int i;
    EdgeNode *p;
    Queue Q;
    for (i=0; i<GL->numVertexes; i++)
        visited[i] = 0;
    InitQueue(&Q);
    for (i=0; i<GL->numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            printf("%c",GL->adjList[i].data);
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);
                p = GL->adjList[i].firstedge;
                while (p) {
                    if (!visited[p->adjvex]) {
                        visited[p->adjvex] = 1;
                        printf("%c",GL->adjList[p->adjvex].data);
                        EnQueue(&Q, p->adjvex);
                    }
                    p = p->next;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

对比图的深度优先遍历与广度优先遍历算法，我们发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的，只是视不同情况选择不同的算法。

5.最小生成树

我们把构造连通网的最小代价生成树称为最小生成树。

找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。

5.1 普里姆(Prim)算法

我们先构造如下图的邻接矩阵。

也就是说，现在我们已经有了一个存储结构为MGragh的G。G有9个顶点，它的arc二维数组如上右图所示。数组中我们用65535来代表∞。

于是普里姆（Prim）算法代码如下，其中INFINITY为权值极大值，不放设65535，MAXVEX为顶点个数最大值，此处大于等于9即可。

/* Prim 算法生成最小生成树 */
void MiniSpanTree_Prim(MGragh G) {
    int min,i,j,k;
    int adjvex[MAXVEX];      // 保存相关顶点下标
    int lowcost[MAXVEX];     // 保存相关顶点间边的权值
    lowcost[0] = 0;          // 初始化第一个权值为0，即v0加入生成树
    adjvex[0] = 0;           // 初始化第一个顶点下标为0
    for (i=1; i<G.numVertexes; i++) {  // 循环除下标为0外的全部顶点
        lowcost[i] = G.arc[0][i];  // 将v0顶点与之有边的权值存入数组
        adjvex[i] = 0;       // 初始化都为v0下标
    }
    for (i=1; i<G.numVertexes; i++) {
        min = INFINITY;      // 初始化最小权值为∞
        j = 1;k = 0;
        while (j < G.numVertexes) {
            if (lowcost[j] != 0 && lowcost[j] < min) {  // 如果权值不为0且权值小于min
                min = lowcost[j];  // 则让当前权值称为最小值
                k = j;             // 将当前最小值的下标存入k
            }
            j++;
        }
    }
    printf("(%d,%d)",adjvex[k],k); // 打印当前顶点边中权值最小边
    lowcost[k] = 0;                // 将当前顶点的权值设置为0，表示此顶点已经完成任务
    for (j=1; j<G.numVertexes; j++) {
        /* 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
        if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
            lowcost[j] = G.arc[k][j];    // 将较小权值存入lowcost
            adjvex[j] = k;               // 将下标为k的顶点存入adjvex
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

5.2 克鲁斯卡尔(Kruskal)算法

普里姆算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。我们也可以以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路而已。此时我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码：

/* 对边集数组Edge结构的定义 */
typedef struct {
    int begin;
    int end;
    int weight;
}Edge;
1
2
3
4
5
6

我们将之前的邻接矩阵转化为下右图的边集数组，并且按权值从大到小排序。

于是克鲁斯卡尔（Kruskal）算法代码如下，其中MAXEDGE为边数量的极大值，此处大于等于15即可，MAXVEX为顶点个数最大值，此处大于等于9即可。

/* Kruskal算法生成最小生成树 */
void MiniSpanTree_Kruskal(MGragh G) {
    int i,n,m;
    Edge edges[MAXEDGE];       // 定义边集数组
    int parent[MAXVEX];        // 定义一数组用来判断边与边是否形成环路
    /* 此处省略将邻接矩阵G转化为边集数组edges并按权有小到大排序的代码 */
    for (i=0; i<G.numVertexes; i++)
        parent[i] = 0;         // 初始化数组值为0
    for (i=0; i<G.numEdges; i++) {   // 循环每一条边
    	n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if (n != m) {          // 假如n与m不等，说明此边没有与现有生成树形成环路
            parent[n] = m;     // 将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经在生成树集合中了
            printf("(%d, %d) %d",edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

int Find(int *parent, int f) {  // 查找连线顶点的尾部下标
    while (parent[f] > 0)
        f = parent[f];
    return f;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

6.最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。显然，我们研究网图更有实际意义，就地图来说，距离就是两顶点间的权值之和。而非网图完全可以理解为所有的边的权值都为1的网。

这里讲解两种求最短路径的算法。

6.1 迪杰斯特拉（Dijkstra）算法

#define MAXVEX 9
#define INFINITY 65535
typedef int Patharc[MAXVEX];             // 用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX];      // 用于存储到各点最短路径的权值和
/* Dijkstra 算法，求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v] */
/* P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和 */
void ShortestPath_Dijkstra(MGragh G, int v0, Patharc *P, ShortPathTable *D) {
    int v,w,k,min;
    int final[MAXVEX];                   // final[w]=1表示求得顶点V0至Vw的最短路径
    for (v=0; v<G.numVertexes; v++) {    // 初始化数据
        final[v] = 0;                    // 全部顶点初始化为未知最短路径状态
        (*D)[v] = G.arc[v0][v];          // 将与v0点有连线的顶点加上权值
        (*P)[v] = 0;                     // 初始化路径数组P为0
    }
    (*D)[v0] = 0;                        // v0至v0路径为0
    final[v0] = 1;                       // v0至v0不需要求路径
    /* 开始主循环，每次求得v0到某个v顶点的最短路径 */
    for (v=1; v<G.numVertexes; v++) {
        min = INFINITY;                  // 当前所知离v0顶点的最近距离
        for (w=0; w<G.numVertexes; w++) {   // 寻找离v0最近的顶点
            if (!final[w] && (*D)[w]<min) {
                k = w;
                min = (*D)[w];           // w顶点离v0顶点更近
            }
        }
        final[k] = 1;                    // 将目前找到的最近的顶点置为1
        for (w=0; w<G.numVertexes; w++) {  // 修正当前最短路径及距离
            /* 如果经过v顶点的路径比现在这条路径的长度短的话 */
            if (!final[w] && (min+G.arc[k][w] < (*D)[w])) {
                /* 说明找到了更短的路径，修改D[w]和P[w] */
                (*D)[w] = min + G.arc[k][w];  // 修改当前路径长度
                (*P)[w] = k;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度为O(n³)。

6.2 弗洛伊德（Floyd）算法

typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* Floyd 算法，求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w] */
void ShortestPath_Floyd(MGragh G, Pathmatirx *P, ShortPathTable *D) {
    int v,w,k;
    for (v=0; v<G.numVertexes; v++) {     // 初始化D与P
        for (w=0; w<G.numVertexes; w++) {
            (*D)[v][w] = G.arc[v][w];  // D[v][w]值即为对应点间的权值
            (*P)[v][w] = w;               // 初始化P
        }
    }
    for (k=0; k<G.numVertexes; k++) {
        for (v=0; v<G.numVertexes; v++) {
            for (w=0; w<G.numVertexes; w++) {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    /* 如果经过下标为k顶点路径比原两点间路径更短 */
                    /* 将当前两点间权值设为更小的一个 */、
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];  // 路径设置经过下标为k的顶点
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

求最短路径的显示代码：

for (v=0; v<G.numVertexes; v++) {
    for (w=v+1; w<G.numVertexes; w++) {
        printf("v%d-v%d weight: %d ",v,w,D[v][w]);
        k = P[v][w];            // 获得第一个路径顶点下标
        printf(" path:%d",v);   // 打印源点
        while (k != w) {        // 如果路径顶点下标不是终点
            printf(" -> %d",k); // 打印路径顶点
            k = P[k][w];        // 获得下一个路径顶点下标
        }
        printf(" -> %d\n",w);   // 打印终点
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13

该算法的时间复杂度为O(n³)，如果面临需要求所有顶点至所有顶点的最短路径问题时，弗洛伊德算法应该是不错的选择。

7.拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（Activity On Vertex Network）。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v₁，v₂······，v_n，满足若从顶点v_i到v_j有一条路径，则在顶点序列中顶点v_i必在顶点v_j之前。则我们称这样的顶点序列为一个拓扑序列。

对AOV网进行拓扑排序的基本思路：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

首先我们需要确定一下这个图需要使用数据结构。前面求最小生成树和最短路径时，我们用的都是邻接矩阵，但由于拓扑排序的过程中，需要删除顶点，显然用邻接表会更加方便。因此我们需要为AOV网建立一个邻接表。考虑到算法过程中始终要查找入度为0的顶点，我们在原来顶点表结点结构中，增加一个入度域in，结构如下表。

因此对于下图AOV网，我们可以得到下面的邻接表数据结构。

在拓扑排序算法中，涉及的结构代码如下：

typedef struct EdgeNode {     // 边表结构
    int adjvex;               // 邻接点域，存储该顶点对应的下标
    int weight;               // 用于存储权值，对于非网图可以不需要
    struct EdgeNode *next;    // 链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode {   // 顶点表结构 
    int in;                   // 顶点入度
    int data;                 // 顶点域，存储顶点信息
    EdgeNode *firstedge;      // 边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes,numEdges; // 图中当前顶点数和边数
}graghAdjList, *GraghAdjList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在算法中，还需要辅助的数据结构-栈，用来存储处理过程中入度为0的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点。

下面来看看拓扑排序算法代码：

/* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */
Status TopologicalSort(GraghAdjList GL) {
    EdgeNode *e;
    int i,k,gettop;
    int top = 0;       // 用于栈指针下标
    int count = 0;     // 用于统计输出顶点的个数
    int *stack;        // 建栈存储入度为0的顶点
    stack = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i=0; i<GL->numVertexes; i++)
        if (GL->adjList[i].in == 0)
            stack[++top] = i;   // 将入度为0的顶点入栈
    while (top !=0 ) {
        gettop = stack[top--];  // 出栈
        printf("%d -> ",GL->adjList[gettop].data);  // 打印此顶点
        count++;                // 统计输出顶点数
        for (e=GL->adjList[gettop].firstedge; e; e=e->next) {
            k = e->adjvex;
            if (!(--GL->adjList[k].in))  // 将k号顶点邻接点的入度减1
                stack[++top] = k;        // 若为0则入栈，以便于下次循环输出
        }
    }
    if (count < GL->numVertexes)         // 如果count小于顶点数，说明存在环
        return ERROR;
    else
        return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度O(n+e)

8.关键路径

拓扑排序主要是为了解决一个工程能否顺利进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。因此在前面讲的AOV网的基础上，再来介绍一个新的概念。在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network）。我们把AOE网中没有入边的顶点称之为始点或源点，没有出边的顶点称之为终点或汇点。由于一个工程，总有一个开始，一个结束，所以正常情况下，AOE网只有一个源点一个汇点。

既然AOE网是表示工程流程的，所以它就具有明显的工程的特性。如有在某顶点所代表的事情发生后，从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生。

尽管AOE网与AOV网都是用来对工程建模的，但它们还是有很大的不同，主要体现在AOV网是顶点表示活动的网，它只描述活动之间的制约关系，而AOE网是用边表示活动的网，边上的权值表示活动持续的时间，如下图对比。因此，AOE网是要建立在活动之间制约关系没有矛盾的基础之上，再来分析完成整个工程至少需要多少时间，或者为缩短完成工程所需时间，应当加快哪些活动等问题。

我们把路径上各活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

现在的问题就是要找出关键路径。

想要找到关键路径，我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则不是。

为此我们需要定义如下几个参数。

1. 事件的最早发生时间etv：即顶点v_k的最早发生时间。
2. 事件的最晚发生时间ltv：即顶点v_k的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
3. 活动的最早开工时间ete：即弧a_k的最早发生时间。
4. 活动的最晚开工时间lte：即弧a_k的最晚发生时间，也就是不推迟工期的最晚开工时间。

我们是由1和2可以求得3和4，然后再根据ete[k]是否与lte[k]相等来判断a_k是否是关键活动。

求事件的最早发生时间etv的过程，就是我们从头至尾找拓扑序列的过程，因此，在求关键路径前，需要先调用一次拓扑序列算法的代码来计算etv和拓扑序列列表。为此，我们首先在程序开始处声明几个全局变量。

int *etv,*ltv;      // 事件最早发生时间和最迟发生时间数组
int *stack2;        // 用于存储拓扑序列的栈
int top2;           // 用于stack2的指针
1
2
3

其中stack2用来存储拓扑序列，以便后面求关键路径时使用。

下面是改进过的求拓扑序列算法。

/* 拓扑排序，用于关键路径计算 */
Status TopologicalSort(GraghAdjList GL) {
    EdgeNode *e;
    int i,k,gettop;
    int top = 0;        // 用于栈指针下标
    int count = 0;      // 用于统计输出顶点的个数
    int *stack;         // 建栈将入度为0的顶点入栈
    stack = (int *)malloc(GL->numVertexes*sizeof(int));
    for (i=0; i<GL->numVertexes; i++)
        if (0 == GL->adjList[i].in)
            stack[++top] = i;
    top2 = 0;           // 初始化为0；
    etv = (int *)malloc(GL->numVertexes*sizeof(int));   // 事件最早发生时间
    for (i=0; i<GL->numVertexes; i++)
        etv[i] = 0;     // 初始化为0
    stack2 = (int *)malloc(GL->numVertexes*sizeof(int)); // 初始化
    while (top != 0) {
        gettop = stack[top--];
        count++;
        stack2[++top2] = gettop;     // 将弹出的顶点序号压入拓扑序列的栈
        
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjvex;
            if (!(--GL->adjList[k].in))
                stack[++top]=k;
            if ((etv[gettop] + e->weight) > etv[k])  // 求各顶点事件最早发生时间值
                etv[k] = etv[gettop] + e->weight;
        }
    }
    if (count < GL->numVertexes)
        return ERROR;
    else
        return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

下面来看求关键路径的算法代码：

/* 求关键路径，GL为有向网，输出GL的各项关键活动 */
void CriticalPath(GraghAdjList GL) {
    EdgeNode *e;
    int i,gettop,k,j;
    int ete, lte;        // 声明活动最早发生时间和最迟发生时间变量
    TopologicalSort(GL); // 求拓扑序列，计算数组etv和stack2的值
    ltv=(int *)malloc(GL->numVertexes*sizeof(int));   // 事件最晚发生时间
    for (i=0; i<GL->numVertexes; i++)
        ltv[i] = etv[GL->numVertexes-1];    // 初始化ltv
    while (top2 != 0) {
        gettop = stack2[top2--];            // 将拓扑排序出栈，后进先出
        for (e = GL->adjList[gettop].firstedge; e; e=e->next) {
            k = e->adjvex;
            if (ltv[k]-e->weight < ltv[gettop])// 求各顶点事件最晚发生时间ltv
                ltv[gettop] = ltv[k] - e->weight;
        }
    }
    for (j=0; j<GL->numVertexes; j++) {  // 求ete，lte和关键活动
        for (e=GL->adjList[j].firstedge; e; e=e->next) {
            k = e->adjvex;
            ete = etv[j];              // 活动最早发生时间
            lte = etv[k] - e->weight;  // 活动最迟发生时间
            if (ete == lte)            // 两者相等即在关键路径上
                printf("<v%d,v%d> length: %d ,",GL->adjList[j].data, GL->adjList[k].data, e->weight);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时间复杂度O(n+e)。

实践证明，通过这样的算法对于工程的前期工期估算和中期的计划调整都有很大的帮助。不过注意，如果是多条关键路径，则单是提高一条关键路径上的关键活动的速度并不能使整个工程缩短工期，而必须提高同时在几条关键路径上的活动速度。