第六节：图（上）
6.1 图
1.关于图
图表示的是“多对多”的关系。它包含：
（1）一组顶点：通常用V（Vertex）表示顶点集合。
（2）一组边：通常用E（Edge）表示边的集合，表示顶点与顶点的关系：
①边是顶点对：(v,w)∈E，其中v,w∈V。这是一个双向的。
②有向边：<v,w>，表示从v指向w的边（单行线）。
③不考虑重边和自回路。
其抽象数据类型为：
|
类型名称：图（Graph） 数据对象集：一非空的顶点集合Vertex和一个边集合Edge，每条边用对应的一对顶点表示。 操作集：对于任意的图G Î Graph，顶点v、v1和v2 Î ertex，以及任一访问顶点的函数visit()，操作举例： Graph Create( )：构造并返回一个空图； void Destroy( Graph G )：释放图G占用的存储空间； Graph InsertVertex( Graph G, Vertex v )：返回一个在G中增加了新顶点v的图 Graph InsertEdge( Graph G, Vertex v1, Vertex v2 )：返回一个在G中增加了新边 (v1, v2) 的图； Graph DeleteVertex( Graph G, Vertex v )：删除G中顶点v及其相关边，将结果图返回； Graph DFS（ Graph G, Vertex v, visit()）：在图G中，从顶点v出发进行深度优先遍历； |
图的一些分类：
（1）无向图。边（v, w）等同于边（w, v）。用圆括号“（）”表示无向边。
（2）有向图（Directed Graphs）: 边<v, w>不同于边<w, v>。用尖括号“< >”表示有向边；有向边也称“弧（Arc）”。
（3）简单图（Simple Graphs）:没有重边和自回路的图。
（4）邻接点: 如果（v, w）或 < v, w >是图中任意一条边，那么称v和w互为“邻接点（Adjacent Vertices）”。
（5）路径、简单路径、回路、无环图：
图G中从vp 到 vq 的路径 = { vp, vi1, vi2, ×××, vin, vq } 使得( vp, vi1 ), ( vi1, vi2 ), ×××, ( vin, vq ) 或 < vp, vi1 >, ×××, < vin, vq > 都属于E( G )。
路径长度：路径中边的数量。
简单路径：vi1, vi2, ×××, vin 都是不同顶点。
回路：起点和终点相同（vp = vq ）的路径。
无环图：不存在任何回路的图。
有向无环图：不存在回路的有向图，也称DAG（Directed Acyclic Graph）。
（6）完全图：分为有向完全图（n(n-1)条边）和无向完全图（n(n-1)/2条边）。
（7）度：与顶点v相关的边数。从该点发出的边数为“出度”，指向该点的边数为“入度”。
（8）稠密图、稀疏图：是否满足 |E| > |V|log2|V|，作为稠密图和稀疏图的分界条件。
（9）权（Cost） 、网络（Network）。
（10）图G的子图 G’ ： V( G’ ) Í V( G ) && E( G’ ) Í E( G )。
（11）无向图的顶点连通、连通图、连通分量：如果无向图从一个顶点vi到另一个顶点vj (i≠j)有路径，则称顶点vi和vj是“连通的（Connected）”；无向图中任意两顶点都是连通的，则称该图是“连通图（Connected Graph）”；无向图的极大连通子图称为“连通分量（Connected Component）”。连通分量的概念包含以下4个要点：子图、连通、极大顶点数、极大边数
（12）有向图的强连通图、连通分量：有向图中任意一对顶点vi 和vj (i≠j)均既有从vi到vj的路径，也有从vj到vi的路径，则称该有向图是“强连通图（Strongly Connected Graph）”。有向图的极大强连通子图称为“强连通分量（Strongly Connected Component）”。连通分量的概念也包含前面4个要点。
（13）树、生成树：树是图的特例：无环的无向图。
所谓连通图G的“生成树（Spanning Tree）”，是G的包含其全部n 个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。
生成树有可能不唯一。
当且仅当G满足下面4个条件之一（完全等价）：
① G有n-1条边，且没有环；
② G有n-1条边，且是连通的；
③ G中的每一对顶点有且只有一条路径相连；
④ G是连通的，但删除任何一条边就会使它不连通。
2.表示图——邻接矩阵
邻接矩阵G[N][N]-N个顶点从0到N-1编号。其中G[i][j]=1（若<vi,vj>是G中的边）或0（不是G中的边）。可以看出邻接矩阵有以下特点：
（1）主对角线全为0；
（2）这是一个对称矩阵。
那么，对于无向图来说，怎样可以节省一半空间？
可以用一个长度为N(N+1)/2的1维数组A存储{G00,G10,…,G(n-1)0,…,G(n-1)(n-1)}。则Gij在A中对应的下标是：(i*(i+1)/2+j)。对于网络，只要把G[i][j]的值定义为边<vi,vj>的权重即可。
问题：vi和vj在网络中它们之间没有边该如何表示？
邻接矩阵有以下优点：
（1）直观、简单、好理解；
（2）方便检查任意一对顶点间是否存在边；
（3）方便找任一顶点的所有“邻接点”（有边直接相连的顶点）；
（4）方便计算任一顶点的“度”：
对于无向图来说，对应行（列）非0的元素的个数。对于有向图来说，对应行非0元素的个数是“出度”，对应列非0元素的个数是“入度”。
邻接矩阵的缺点：
（1）浪费空间：存稀疏图有大量无效元素。但是对于稠密图（特别是完全图）还是很合算。
（2）浪费时间：统计系数图中一共有多少条边。
3.表示图——邻接表
邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到一个数组中，就构成了图的邻接表。
一定要够稀疏用邻接表才合算！！！！
邻接表的特点：
（1）方便找任一顶点的所有“邻接点”。
（2）节约稀疏图的空间：需要N个头指针+2E个结点。
（3）方便计算任一顶点的“度”：对于无向图来说是如此，对于有向图来说，这只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”。
6.2 图的遍历
1.深度优先搜索（DFS）
代码实现：
void DFS( Graph G, int V )
{ /* 从第V个顶点出发递归地深度优先遍历图G */
VertexType W;
Visited[V] = TRUE;
VisitFunc(V); /* 访问第V个顶点 */
for( W = FirstAdjV(G, V); W; W = NextAdjV (G, V, W) )
if( !Visited[W] )
DFS(G, W); /* 对V的尚未访问的邻接顶点W递归调用DFS */
}
这段代码的意思是，首先我们开始访问，然后每访问一个节点，都将其标记为True，然后开始访问V的邻接点，如果没访问，那就去访问并且置为True，当看到邻接点都是True时，我们原路返回，若发现没访问过的邻接点，立即去访问；如果没有发现，继续原路返回，直到返回到第一个结点。
若由N个顶点，E跳边，时间复杂度是：
（1）用邻接表存储图：O(N+E)；
（2）用邻接矩阵，有O(N2)。
2.广度优先搜索（BFS）
相当于层序遍历。
void BFS(Graph G)
{ /* 按广度优先遍历图G。使用辅助队列Q和访问标志数组Visited */
Queue *Q; VertexType U, V, W;
for ( U = 0; U < G.n; ++U ) Visited[U] = FALSE;
Q = CreatQueue( MaxSize ); /* 创建空队列Q */
for ( U = 0; U<G.n; ++U )
if (!Visited[U] ) { /* 若U尚未访问 */
Visited[U] = TRUE;
VisitFunc(U); /* 访问U */
AddQ (Q, U); /* U入队列 */
while ( ! IsEmptyQ(Q) ) {
V = DeleteQ( Q ); /* 队头元素出队并置为V */
for( W = FirstAdjV(G, V); W; W = NextAdjV(G, V, W) )
if ( !Visited[W] ) {
Visited[W] = TRUE;
VisitFunc (W); /* 访问W */
AddQ (Q, W);
}
} /* while结束*/
} /* 结束从U开始的BFS */
}
若由N个顶点，E跳边，时间复杂度是：
（1）用邻接表存储图：O(N+E)；
（2）用邻接矩阵，有O(N2)。
6.3 图的应用
1.应用实例：拯救007
如图1所示，如何让007通过这一个个结点（鳄鱼），一步一步跳到岸边呢？这里用深度优先算法更为合适。
原来的总体算法（伪代码）：
void ListComponents(Graph G)
{
for(each V in G)
if(!visited[V]){
DFS(V);
}
}
这里的总体算法（伪代码）：
void Save007(Graph G)
{
for(each V in G)
if(!visited[V]&& FirstJump(V))/*判断是否踩过这个鳄鱼还有是否能够得着*/
{
answer = DFS(V);
if(answer ==YES) break;
}
if(answer ==YES) output("YES");
else output("BYEBYE");
}
DFS部分的伪代码：
int DFS(Vertex V)
{
visited[V] = True;
if(IsSafe(V)) answer = YES;
else{
for(V的每个邻接点W)
if(!visited[W]&& Jump(V,W))
/*Jump计算两个鳄鱼之间距离是否小于007最大跳动距离*/
{
answer=DFS(W);
DFS(W);
}
}
return answer;
}
6.4 图的建立
1.用邻接矩阵表示图
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;/*顶点数*/
int Ne;/*边数*/
WeightType G[MaxVertexNum][MaxVertexNum];
DataType Data[MaxVertexNum];/*存顶点的数据*/
};
typedef PtrToGNode MGraph;/*以邻接矩阵存储的图类型*/
2.初始化图
typedef int Vertex;/*用顶点下标表示顶点，为整型*/
MGraph CreateGraph(int VertexNum)
{
Vertex V,W;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
/*这里默认顶点标号从0开始，到(Graph->Nv-1)*/
for(V=0;V<Graph->Nv;V++)
for(W=0;W<Graph->Nv;W++)
Graph->G[V][W] = 0;/*有向图是INFINITY*/
return Graph;
}
3.插入边
typedef struct ENode *PtrToGNode;
struct ENode
{
Vertex V1,V2;/*有向边<V1,V2>*/
WeightType Weight;/*权重*/
};
typedef PtrToGNode Edge;
void InsertEdge( MGraph Graph, Edge E)
{
/*插入边<V1,V2>*/
Graph->G[E->V1][E->V2]=E->Weight;
/*无向图*/
Graph->G[E->V2][E->V1]=E->Weight;
}
4.建立图
（1）输入格式：Nv Ne
V1 V2 Weight
代码如下：
MGraph BuildGraph()
{
Edge E;
MGraph Graph;
Vertex V;
int Nv,i;
scanf("%d",&Nv);
Graph = CreateGraph(Nv);
scanf("%d",&(Graph->Ne));
if(Graph->Ne!=0)
{
E = (Edge)malloc(sizeof(struct ENode));
for(i=0;i<Graph->Ne;i++){
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
InsertEdge(Graph, E);
}
}
/*如果顶点有数据的话，读入数据*/
for(V=0;V<Graph->Nv;V++)
scanf("%c",&(Graph->Data[V]));
return Graph;
}
但是这样来说太麻烦了，如果不要这么麻烦，一个整体的程序（不再需要子程序）可以如下：
int G[MAXN][MAXN],Nv,Ne;
void BuildGraph()
{
int i,j,v1,v2,w;
scanf("%d",&Nv);
/*CreateGraph*/
for(i=0;i<Nv;i++)
for(j=0;j<Nv;j++)
G[i][j]=0;/*初始化，有向图为无穷*/
scanf("%d", &Ne);/*输入有多少个结点*/
for(i=0;i<Ne;i++)
{
scanf("%d %d %d", &v1,&v2,&w);
/*将边插入*/
G[v1][v2]=w;
G[v2][v1]=w;
}
}
一气呵成。
5.邻接表表示的图结点的结构
邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;/*顶点数*/
int Ne;/*边数*/
AdjList G;/*邻接表*/
};
typedef PtrToGNode LGraph;
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
DataType Data;/*存顶点的数据*/
}AdjList[MaxVertexNum];
/*AdjList是邻接表类型*/
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;/*邻接点下标*/
WeightType Weight;
PtrToAdjVNode Next;/*指向下一个邻接点的指针*/
};
6.邻接表表示的图-建立图
（1）初始化一个由VertexNum个顶点但没有边的图
typedef int Vertex;/*用顶点下标表示顶点，为整型*/
LGraph CreateGraph(int VertexNum)
{
Vertex V,W;
LGraph Graph;
Graph = (LGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne =0;
/*每一个顶点跟着的链表都是空的为没有边*/
for(V=0;V<Graph->Nv;V++)
Graph->G[V].FirstEdge = NULL;
return Graph;
}
（2）向LGraph中插入边
void InsertEdge(LGraph Graph, Edge E)
{
PtrToAdjVNode NewNode;
/*插入边<v1,v2>*/
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->AdjV=E->V2;
NewNode->Weight = E->Weight;
/*将V2插入V1的表头*/
NewNode-Next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;
/*若是无向图，还要插入边<V2,V1>*/
/*为V1建立新的邻接点*/
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->AdjV=E->V1;
NewNode->Weight = E->Weight;
/*将V1插入V2的表头*/
NewNode-Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}
（3）完整建立LGraph
LGraph BuildGraph()
{
LGraph Graph;
/*剩余与邻接矩阵完整版类似*/
}