[部分内容由gpt自动生成]

基本概念

(摘自严蔚敏的教材)

【定义】一个图(G)定义为一个偶对(V,E)，记为G=(V,E)。其中： V是顶点(Vertex)的非空有限集合，记为V(G)；E是无序集V&V的一个子集，记为E(G) ，其元素是图的弧(Arc)。其形式化定义为：

G=(V ，E)

V={v|v∈data object}

E={<v,w>| v,w∈V∧p(v,w)}

P(v,w)表示从顶点v到顶点w有一条直接通路。

弧(Arc) ：表示两个顶点v和w之间存在一个关系，用顶点偶对<v,w>表示。通常根据图的顶点偶对将图分为有向图和无向图。

有向图(Digraph)： 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是有序的，称图G是有向图。在有向图中，若 <v,w>∈E(G) ，表示从顶点v到顶点w有一条弧。 其中：v称为弧尾(tail)或始点(initial node)，w称为弧头(head)或终点(terminal node) 。

无向图(Undigraph)： 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是无序的，称图G是无向图。在无向图中，若<v,w>∈E(G)，则<w,v>∈E(G)，即E(G)是对称，则用无序对(v,w)表示v和w之间的一条边(Edge)，因此(v,w) 和(w,v)代表的是同一条边。

例1：设有有向图G1和无向图G2，形式化定义分别是：

(src: 严蔚敏教材)

G1=(V1 ，E1)

V1={a,b,c,d,e}

E1={<a,b>,<a,c>, <a,e>,<c,d>,<c,e> ,<d,a>,<d,b>,<e,d>}

G2=(V2 ，E2)

V2={a,b,c,d}

E2={(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)}

图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。

有很少边或弧的图（e<n㏒n）的图称为稀疏图，反之称为稠密图。

权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。

顶点的邻接(Adjacent)：对于无向图G=(V，E)，若边(v,w)∈E，则称顶点v和w 互为邻接点，即v和w相邻接。边(v,w)依附(incident)与顶点v和w 。

对于有向图G=(V ，E)，若有向弧<v,w>∈E，则称顶点v “邻接到”顶点w，顶点w“邻接自”顶点v ，弧<v,w> 与顶点v和w“相关联”。

顶点的度、入度、出度：对于无向图G=(V，E)，vi∈V，图G中依附于vi的边的数目称为顶点vi的度(degree)，记为TD(vi)。

对有向图G=(V，E)，若vi∈V ，图G中以vi作为起点的有向边(弧)的数目称为顶点vi的出度(Outdegree)，记为OD(vi)；以vi作为终点的有向边(弧)的数目称为顶点vi的入度(Indegree)，记为ID(vi)。顶点vi的出度与入度之和称为vi的度，记为TD(vi)。即 TD(vi)=OD(vi)+ID(vi)

路径(Path)、路径长度、回路(Cycle) ：对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。

对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。

或路径是图G中连接两顶点之间所经过的顶点序列。即

(src:严蔚敏教材)

路径上边或有向边(弧)的数目称为该路径的长度。

在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。

图的存储结构

由于图G=(V,E)，是顶点和边的二元组。因此在存储时，除了要存储边集E外，还要存储顶点集V。一般情况下，顶点集V用顺序存储结构，而边集E则根据情况，采用顺序存储结构或者链式存储结构。

2.1 图的顺序存储结构

边集E表示的是顶点之间的关系，因此用二维数组进行存储，也称为邻接矩阵(Adjacency Matrix)。对于拥有n个顶点的图G，它的邻接矩阵是n*n的方阵，其中的元素定义为：

下图展示了采用顺序存储结构表示的结果，包括了顶点集、边集的存储。

图的顺序存储——邻接矩阵 (src: )

typedef char Vertex[20]; /* 顶点的数据类型，字符串 */

typedef struct SeqGraph {

Vertex *vertex; /* 顶点集 */

int c; /* capacity */

int n_v; /* number of vertex */

int *adjMatrix; /* adjacency matrix */

int **fastAddr; /* i*n+j => [i][j] */

} SeqGraph;

/* 创建最多n个顶点的图 */

int createSeqGraph(SeqGraph *g, int n);

/* 图g插入顶点v */

int insertVertexSeqGraph(SeqGraph *g, Vertex v);

/* 图g插入边(u,v) */

int insertEdgeSeqGraph(SeqGraph *g, Vertex u, Vertex v);

/* 图的销毁 */

void destroySeqGraph(SeqGraph *g);

2.2 图的链式存储结构

对图中的每个顶点vi都分别建立一个对应的单链表(对无向图称为“边表”，对有向图称为“出边表”）来存储所有邻接与顶点vi的边(对于有向图而言是指以vi为尾的弧)，边表中的每个结点分别对应于邻接于顶点vi的一条边。边表中的每个结点主要包含两个域，其中邻接点域(adj_vex)指示与顶点vi邻接的点在图中的位置，链域(next_edge)指示下一条边或弧的结点。如果是带权图，还可以再加一个域weight，表示从vi到adj_vex这条边的权值。

对于图中的所有顶点信息，用一个一维数组（称为"顶点表"）来存放。对于顶点表中的每个顶点单元，需要存放:该顶点信息值(data)、一个指向由邻接于该顶点的所有的边组成的边表的头指针(first_edge)。

图的链式存储——邻接表 (src: )

typedef char Vertex[20]; /* 顶点的数据类型，字符串 */

typedef struct AdjLinkedNode {

int adjvex;

struct AdjLinkedNode *next;

}AdjLinkedNode;

typedef struct LinkedGraph {

Vertex *vertex; /* 顶点集 */

int c; /* capacity */

int n_v; /* number of vertex */

AdjLinkedNode *adjHeaders;

} LinkedGraph;

/* 创建最多n个顶点的图 */

int createLinkedGraph(LinkedGraph *g, int n);

/* 图g插入顶点v */

int insertVertexLinkedGraph(LinkedGraph *g, Vertex v);

/* 图g插入边(u,v) */

int insertEdgeLinkedGraph(LinkedGraph *g, Vertex u, Vertex v);

/* 图的销毁 */

void destroyLinkedGraph(LinkedGraph *g);

图的遍历

图的遍历(Travering Graph)：从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是各种图的操作的基础。

图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。解决办法：在遍历过程中记下已被访问过的顶点。设置一个辅助向量Visited[n](n为顶点数)，其初值为0，一旦访问了顶点vi后，使Visited[i]为1或为访问的次序号。

图的遍历算法有深度优先搜索算法和广度优先搜索算法。

3.1 深度优先搜索算法

类似于二叉树的先序/中序/后序遍历，不同的地方在于：二叉树的结点只有固定的左右两个孩子，图的邻接点需要从邻接矩阵/邻接表中罗列出来。

void traverseSeqGraphInner(SeqGraph *g, int u, int visited[],

int (*func)(Vertex v))

{

int v;

if (visited[u] == 1) {

return;

}

/* visit u */

visited[u] = 1;

/* printf("%d: %s\n", u, g->vertex[u]); */

func(g->vertex[u]);

/* 访问顶点u的邻接点v */

for(v=0; v<g->n_v; v++) {

if (g->adjMatrix[u*g->c + v]>0) {

traverseSeqGraphInner(g, v, visited, func);

}

}

}

/* 图的遍历 */

void traverseSeqGraph(SeqGraph *g, int (*func)(Vertex v))

{

int i, *visited; /* 到此一游 */

visited = (int *)malloc(sizeof(int) * g->n_v);

for(i=0; i<g->n_v; i++) {

visited[i] = 0;

}

/* 解决非连通图问题 */

for(i=0; i<g->n_v; i++) {

traverseSeqGraphInner(g, i, visited, func);

}

}

3.2 广度优先搜索算法

与树的广度优先遍历一样，需要通过队列来实现。

（代码略）

图的生成树算法、最短路径算法

为了介绍生成树的概念，先补充几个图相关的概念：

子图和生成子图：设有图G=(V，E)和G’=(V’，E’)，若V’∈V且E’ ∈E ，则称图G’是G的子图；若V’=V且E’ E，则称图G’是G的一个生成子图。

生成树：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。

如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。

最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。

4.1 最小生成树的Prime算法与最短路径的Dijkstra算法

这两个算法非常相像，尽管用于解决不同的问题。它俩可以归入动态规划（Dynamic Programming）中，由当前状态选择最优，然后更新下一步的状态。

这两个问题，都是把图中的顶点集V划分为两个集合，一个是已经解决的顶点集U，剩余的未解决顶点集V-U。

对于每个顶点，都记录下它们的解决代价，分别用costs[]和dist[]数组来表示每个顶点的生成代价和最短距离。需要注意的是，costs[]和dist[]数组，记录的是从集合U到顶点v的代价，而不是源点直接到v的代价（源点到顶点v的解决方案，可能会经过集合U中的若干顶点）。

算法的执行采用贪心算法，每次从未解决的顶点集中挑选一个最小代价，把它归入已解决的顶点集U中，然后更新剩余V-U中的解决代价，如下图所示。

这两个问题的区别在于，代价的计算方式不一样而已。

下面是这两个算法的求解过程表示。

普里姆(Prime)算法的求解过程如下（从顶点V0开始）

Dijkstra算法的求解过程如下（从顶点V0开始）：

4.2 最小生成树的Kruskal算法

其思想是，从最小代价的边挑选起，只要不形成回路即可。新挑选的一条边是否形成回路，关键是看这条边关联的两个顶点，是否已经在同一棵树上（一棵树上的任意两个顶点都是可达的，新增一条边即可形成回路）。

树的存储采用简单的双亲表示法，很容易找到每个顶点所在树的树根，进而判断两个顶点是否在同一棵树上。

算法的解决过程如下：

4.3 所有顶点之间最短距离的Floyd算法

假设顶点Vk处于某对顶点的最短路径上，考虑从图中把Vk删除的情况。假设顶点Vi和Vj都与顶点Vk相邻。Vi到Vj的最短距离，有可能经过Vk，也有可能不经过。

注意，上述的公式中，使用的是dist数组而不是edge数组。随着顶点的删除，会逐步构建出一个新的全连接图（任意两点都有边相连），该图的边权值就是原图中这两个顶点的最短距离。每次dist[i][j]的更新，都意味着新图中一条边的生成，或者权值的更新。

算法的执行，只需要把所有Vk删除即可。每次删除时，要考虑在新图中所有与Vk相邻的顶点Vi和Vj。

求解过程如下：

第五节 有向图的关键路径