一、图的基本概念

 

图(Graph)——图G是由两个集合 V(G) 和E(G) 组成的，记为 G=(V,E)，其中：V(G) 是顶点的非空有限集， E(G) 是边的有限集合，边是顶点的无序对或有序对。

图不能是空图

1.图的术语和定义

1）有向图

若E是有向边的有限集合时，则图G为有向图。弧是顶点的有向对，记为<v，w>，其中v，w∈V，v称为弧尾，w称为弧头，<v，w>称为从v到w的弧

2）无向图

若E是无向边的有限集合时，则图G为无向图。边是顶点的无向对，记为(v，w)或(w，v)，其中v，w∈V

3）简单图

一个图G若满足不存在重复边和环，那么称图G为简单图。

4）完全图

每个顶点之间都存在边的图。无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条弧

5)子图，生成子图

设有两个图G1=(V1,E1)，G2(V2,E2)，若V2是V1的子集且E2是E1的子集，则称G2是G1的子图。若V2=V1，则称G2是G1的生成子图。

6）连通，连通图，连通分量

在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图。无向图中的极大连通子图称为连通分量。如果图是非连通图，最多可以有条边

7）强连通图，强连通分量

在有向图中，如果有一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分类。

8）生成树，生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

9）顶点的度，入度和出度

在无向图中，顶点v的度是指依附于顶点v的边的条数，记为TD(v)。对于n个顶点，e条边的无向图，度之和为边数的2倍。

在有向图中，顶点v的度分为入度和出度，入度是以顶点v为终点的弧的数目，记为ID(v)；出度是以顶点v为起点的有向边的数目，记为OD(v)。

10）边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带权值的图称为带权图，也称网。

11）稠密图，稀疏图

边数很少的图称为稀疏图，反之称为稠密图。一般当图G满足|E|<|V|log|V|时，可以将G视为稀疏图。

12）路径，路径长度和回路

顶点Vp到Vq之间的一条路径是指顶点序列Vp，Vi1，Vi2，...，Vim，Vq。路径上的边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。

13）简单路径，简单回路

在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

14）距离

从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离

15）有向树

一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。

16）欧拉图

经过图中每条边一次且仅一次行遍所有顶点的回路(回到起点)称为欧拉回路，具有欧拉回路的图称为欧拉图。

17）哈密顿图

经过图中所有顶点仅一次的回路称为哈密顿回路，这种图叫哈密顿图。

2.图的存储

1）邻接矩阵法

用一个一维数组存储图中顶点信息，用一个二维数组存储图中边的信息。存储顶点之间邻接关系的二维数组称为邻接矩阵。

#define MaxVertexNum 100
typedef struct{char Vex[MaxVertexNum];int Edge[MaxVertexNum][MaxVertexNum];int vexnum,arcnum;
}MGraph;

所需存储空间

无向图的邻接矩阵一定是对称矩阵并且唯一，因此在实际存储中只需存储上(下)三角

对于无向图，邻接矩阵的第i行非零元素的个数正好是顶点i的度

对于有向图，邻接矩阵的第i行非零元素个数是顶点i的出度，第i列非零元素个数是顶点i的入度 

适合稠密图

设图G的邻接矩阵为A，的非零元素等于顶点i到顶点j的长度为n的路径数目。

2）邻接表法

对图G的每个顶点建立一个单链表，单链表中的结点表示依附于顶点vi的边

typedef struct edge_node
{int adjvex;struct edge_node *next;
}edge;
typedef struct vertex_node
{char data;edge *first_edge;
}vertex;
typedef struct
{vertex adjlist[1000];int numVertex;int numEdge;
}GraphAdjList;

无向图存储空间为，有向图存储空间为

适合稀疏图

3）十字链表

在有向图邻接表中，找某一点的入度需要遍历整个边集，改用十字链表，增加头域连接弧头相同的边。

typedef  struct  ArcBox
{   int   tailvex,  headvex;   // 弧尾、弧头在表头数组中位置struct   arcnode   *hlink；  // 指向弧头相同的下一条弧struct   arcnode   *tlink;      // 指向弧尾相同的下一条弧
} ArcBox;
typedef  struct  VexNode
{  VertexType   data; // 存与顶点有关信息ArcBox *firstin；  // 指向以该顶点为弧头的第1个弧结点ArcBox *firstout;  // 指向以该顶点为弧尾的第1个弧结点
} VexNode;
VexNode  OLGraph[M];

4）邻接多重表

在无向图邻接表中，同一条边被存储两次，改用邻接多重表，增加jlink指向下一条依附于顶点j的边。

typedef   struct  node
{   VisitIf  mark;   // 标志域，记录是否已经搜索过int  ivex, jvex;  // 该边依附的两个顶点在表头数组中位置struct  EBox   * ilink,  * jlink;  
//分别指向依附于ivex和jvex的下一条边
} EBox;
ypedef   struct  VexBox
{    VertexType   data;              // 存与顶点有关的信息EBox  * firstedge;              // 指向第一条依附于该顶点的边
} VexBox;
VexBox  AMLGraph[M];

3.图的遍历

1）广度优先搜索BFS

思想：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的顶点w1，w2，...，wi，然后依次访问w1，w2，...，wi的所有未被访问过的邻接顶点，重复以上过程直至所有顶点都被访问过。若此时图中还有未被访问的顶点，则另选一个未被访问过的顶点做起始点。

bool visited[MaxVertexNum];
void BFSTraverse(Graph G) {for (int i = 0; i < G.vexnum; i++) visited[i] = false;InitQueue(Q);for (int i = 0; i < G.vexnum; i++) {if (!visited[i]) BFS(G, i);}
}
void BFS(Graph G, int v) {visit(v);visited[v] = true;EnQueue(Q, v);while (!IsEmpty(Q)) {DeQueue(Q, v);for (w = FirstNeighbour(G, v); w >= 0; w = NextNeighbour(G, v, w)) {if (!visited[w]) {visit(w);visited[w] = true;EnQueue(Q, w);}}}
}

空间复杂度

采用邻接表存储时，每个顶点均需被搜索一次，在搜索任一顶点的临接点时，每条边至少访问一次，时间复杂度为

采用邻接矩阵存储时，时间复杂度为

 2）深度优先搜索

首先访问起始顶点v，然后由v出发访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接的且未被访问的任一顶点w2，重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至所有顶点都被访问。

bool visited[MaxVertexNum];
void DFSTraverse(Graph G) {for (int i = 0; i < G.vexnum; i++) visited[i] = false;for (int i = 0; i < G.vexnum; i++) {if (!visited[i]) DFS(G, i);}
}
void DFS(Graph G, int v) {visit(v);visited[v] = true;EnQueue(Q, v);while (!IsEmpty(Q)) {DeQueue(Q, v);for (w = FirstNeighbour(G, v); w >= 0; w = NextNeighbour(G, v, w)) {if (!visited[w]) {DFS(G, w);}}}
}

空间复杂度

采用邻接表存储时，每个顶点均需被搜索一次，在搜索任一顶点的临接点时，每条边至少访问一次，时间复杂度为

采用邻接矩阵存储时，时间复杂度为

3）图的连通性

对于无向图来说，若无向图是连通的，则从任一节点出发，仅需一次遍历就能够访问图中的所有顶点；若是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点。对于有向图来说，若从初始顶点到图中的每个顶点都有路径，则能够访问到图中的所有顶点。

二、图的应用

1.最小生成树(最小连通子图，包含所有顶点，n-1条边)

假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？

1）Prim算法

设 G=(V, GE) 为一个具有 n 个顶点的连通网络，T=(U, TE) 为生成树。

(1) 初始时，U = {u0}，TE = {}；         

(2) 在所有的边 (u, v) 中选择一条权值最小的边，不妨设为(u,v)；         

(3) (u,v) 加入TE，同时将 v 加入U；         

(4) 重复(2)(3)，直到 U=V 为止；

void MiniSpanTree_P(MGraph G, VertexType u)
{//用普里姆算法从顶点u出发构造网G的最小生成树k = LocateVex(G, u);for (j = 0; j < G.vexnum; ++j)  // 辅助数组初始化if (j != k)closedge[j] = { u, G.arcs[k][j] };closedge[k].Lowcost = 0;      // 初始，U＝{u}for (i = 1; i < G.vexnum; ++i){k = minimum(closedge);// 求出加入生成树的下一个顶点(k)printf(closedge[k].Adjvex, G.vexs[k]);// 输出生成树上一条边closedge[k].Lowcost = 0; // 第k顶点并入U集for (j = 0; j < G.vexnum; ++j)// 修改其它顶点的最小边if (G.arcs[k][j] < closedge[j].Lowcost)closedge[j] = { G.vexs[k], G.arcs[k][j] };}
}

Prim算法的时间复杂度为，不依赖于|E|，适用于求解边稠密的图的最小生成树。

2）Kruskal算法

设连通网 N = ( V, { E } )。

① 初始时最小生成树只包含图的 n 个顶点，每个顶点为一棵子树（构成一个连通分量）；

② 选取权值较小且所关联的两个顶点不在同一连通分量的边，将此边加入最小生成树中；

③ 重复② n-1 次，即得到包含 n 个顶点和 n-1 条边的最小生成树。

Kruskal算法采用堆来存放边的集合时，时间复杂度为，因此Kruskal算法适合于边稀疏的而顶点多的图。

2.最短路径

1）对于无权图，可以使用广度优先搜索查找最短路径

2）Dijkstra算法

辅助集合S： 当前已经得到最短路径的顶点集合 初始时，S={V0}

辅助数组Dist Dist[k] 表示 “当前”所求得的从源点到顶点 k 的最短路径

Dist[k] = <源点到顶点 k 的弧上的权值> 或者= 沿着“当前”最短路径到顶点 k的路径长度

假设“当前”最短路径为源点到顶点j的路径 则，Dist[k] =“当前”最短路径长度+ <顶点j到顶点 k 的弧上的权值>

①初始化S={v0}

V0和k之间存在弧： Dist[k]＝G.arcs[v0][k]

V0和k之间不存在弧： Dist[k]＝无穷

② 在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。

③ 依次修改其它尚未确定最短路径的顶点Dist[k]值。

假设求得最短路径的顶点为u，则 Dist[k] ＝min( Dist[k], Dist[u] + G.arcs[u][k] )

重复②③n-1次，直到所有的顶点都在S中

#define MaxVertexNum 100
#define MAXN 0xffff    
typedef struct {char Vex[MaxVertexNum];int Edge[MaxVertexNum][MaxVertexNum];int vexnum, arcnum;
}MGraph;
void Dijkstra(MGraph M, int dist[]) {int visited[MaxVertexNum];for (int i = 0; i < M.vexnum; i++) {visited[i] = 0;}int flag = 0;while (flag != M.vexnum) {int d = MAXN;int v = -1;for (int i = 0; i < M.vexnum; i++) {if (dist[i] < d&&visited[i] == 0) {d = dist[i];v = i;}}if (d == MAXN) {break;}visited[v] = 1;flag++;for (int i = 0; i < M.vexnum; i++) {if (visited[i] == 0 && dist[v] + M.Edge[v][i] < dist[i]) {dist[i] = dist[v] + M.Edge[v][i];}}}
}
int main()
{MGraph M;int x, y, dis;char a, b, c;scanf("%d,%d,%c", &M.vexnum, &M.arcnum, &c);getchar();					//读取换行符for (int i = 0; i < M.vexnum; i++)//初始化{for (int j = 0; j < M.vexnum; j++){M.Edge[i][j] = (i == j) ? 0 : MAXN;}}for (int i = 0; i < M.arcnum; i++){scanf("<%c,%c,%d>", &a, &b, &dis);getchar();x = a - 'a';//把字符转化为数字来算y = b - 'a';if (M.Edge[x][y] > dis)M.Edge[x][y] = dis;}int num = c - 'a';int dist[MaxVertexNum];for (int i = 0; i < M.vexnum; i++) {dist[i] = M.Edge[num][i];}Dijkstra(M,dist);for (int i = 0; i < M.vexnum; i++){printf("%c:%d\n", i + 'a', dist[i]);//记得转回字符}//system("pause");return 0;
}

时间复杂度

 值得注意的是，边上带有负权值时，Dijkstra算法并不适用。

3）Floyd算法求各顶点之间的最短路径问题

按照顶点序号逐个试探，假设为任意2个顶点已计算出中间节点最大序号为K-1的最短路径，在此基础上进一步计算出任意2个顶点中间节点最大序号为K的最短路径。

①初始时设置一个 n 阶方阵，令其对角线元素为 0，若存在弧 <Vi, Vj>，则对应元素为权值；否则为∞。

②逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。

③所有顶点试探完毕，算法结束。

 

 加入V1点 考察：

<v2, v3> = 2 ,<v2, v1> <v1,v3> = 17

<v3, v2> = ∞,<v3, v1> <v1,v2> = 7

 

 加入V2点 考察：

<v1, v3> = 11             <v1, v2> <v2, v3> = 6            

<v3, v1> = 3             <v3, v2> <v2, v1> = 13

 加入V3点 考察：

<v1, v2> = 4             <v1, v3> <v3, v2> = 13            

<v2, v1> = 6             <v2, v3> <v3, v1> = 5

3.有向无环图

若一个有向图中不存在环，则称为有向无环图，简称DAG图

有向无环图是描述含有公共子式的表达式的有效工具。(编译原理代码优化部分删除公共子表达式)

输入：一个基本块 Bi  

输出：含有下列信息的基本块Bi 的DAG：        

(1) 叶结点、内部结点按统一标记；        

(2) 每个结点有一个标识符表（可空）；  

算法：      

对基本块中每一四元式依次执行以下步骤

1.  构造叶结点；

2.  捕捉已知量，合并常数； //删除原常数结点

3.  捕捉公共子表达式；         //删除冗余的公共子表达式

4.  捕捉可能的无用赋值；     //删除

4. 拓扑排序

AOV网：若用DAG图表示一个工程，用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（Activity On Vertex network），简称AOV网。AOV网中不允许有回路，因为回路意味着某项活动以自己（或者后继）为先决条件。

拓扑排序：把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。       

检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

在有向图中选一个没有前驱的顶点且输出之。

从图中删除该顶点和所有以它为尾的弧。         

重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

int topo_sort(GraphAdjList *map)
{//把入度为0的点加入队列for (int i = 0; i < map->numVertex; i++){if (map->adjlist[i].index == 0){queeu[rear] = i;rear++;}}int count = 0;while (1){edge *p = map->adjlist[queeu[front]].first_edge;front++;		//每次出队一个while (p != NULL)		//出队之后相应的边的点入度减一，判断是否入度为0，为0加入{map->adjlist[p->adjvex].index--;if (map->adjlist[p->adjvex].index == 0){queeu[rear] = p->adjvex;rear++;}p = p->next;}QuickSort(front, rear - 1);	//排序if (rear == front){break;}count++;	//统计输出顶点数}if (count < map->numVertex - 1)		//如果count>num，则必有环{return 0;}return 1;
}

5.关键路径

AOE网：用边表示活动的网。它是有一个带权的有向无环图。顶点表示事件/状态，弧表示活动，权值表示活动持续的时间。路径长度表示路径上各活动持续时间之和，关键路径表示路径长度最长的路径。

算法：

计算“状态(顶点)” 的最早发生时间 ve(j)，“状态(顶点)” 的最迟发生时间 vl(k)

计算活动(弧)”的 最早开始时间 e(i)，活动(弧)”的 最迟开始时间 l(i)

关键活动： e(i)  ＝ l(i)

最早开始时间： ve(源点) = 0； ve(k) = Max{ve(j) + dut(<j, k>)}

最迟开始时间： vl(汇点) = ve(汇点)； vl(j) = Min{vl(k) – dut(<j, k>)}

活动(弧)发生时间的计算公式 假设第 i 条弧为 <j, k> ，则 对第 i 项活动言

e(i) = ve(j)； l(i) = vl(k) – dut(<j,k>)；

按AOE网拓扑序列的顺序，求顶点的ve; 按逆拓扑序列的顺序，求顶点的vl; 由ve、vl, 计算每个活动的e[k]和l[k]； 找出e[k]==l[k]的关键活动

6.连通分量

BFS或DFS

7.邮递员问题*

(1)若是欧拉图，则欧拉回路是最短投递路线

(2)否则，图中有偶数个奇度顶点，只需要把每对奇度点之间沿着最短路径重复走一遍即可。

8.TSP问题*