第6章 图

本章中介绍下列主要内容：
　　 1.图的定义
　　 2.图的存储结构
　　 3.图的遍历操作
　　 4.图的几个典型应用问题
课时分配：
1、2两个学时，3两个学时，4四个学时,上机两个学时
重点、难点：
图的遍历操作、典型应用问题

第一节 图的定义

1．定义
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。
在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。
若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。
以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。
在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和<vj,vi>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条边，我们又将具有n(n-1)/2条边的无向图称作无向完全图。
与顶点v相关的边的条数称作顶点v的度。 路径长度是指路径上边或弧的数目。
若第一个顶点和最后一个顶点相同，则这条路径是一条回路。
若路径中顶点没有重复出现，则称这条路径为简单路径。
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。
在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
2．图的基本操作
基本操作：
（1）创建一个图结构 CreateGraph(G)
（2）检索给定顶点 LocateVex(G,elem)
（3）获取图中某个顶点 GetVex(G,v)
（4）为图中顶点赋值 PutVex(G,v,value)
（5）返回第一个邻接点 FirstAdjVex(G,v)
（6）返回下一个邻接点 NextAdjVex(G,v,w)
（7）插入一个顶点 InsertVex(G,v)
（8）删除一个顶点 DeleteVex(G,v)
（9）插入一条边 InsertEdge(G,v,w)
（10）删除一条边 DeleteEdge(G,v,w)
（11）遍历图 Traverse(G,v)

第二节 图的存储结构

1．邻接矩阵
1．1 有向图的邻接矩阵
具有n个顶点的有向图可以用一个n×n的方形矩阵表示。假设该矩阵的名称为M，则当<vi,vj>是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。
1．2 无向图的邻接矩阵
具有n个顶点的无向图也可以用一个n×n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i 行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半，这是因为每条边在矩阵中描述了两次

在C 语言中，实现邻接矩阵表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 20
typedef struct graph{
Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int n;
}Graph;
2． 邻接表
边结点的结构为：

adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针 。

elem是顶点内容，firstedge是指向第一条边或弧结点的指针。
在C语言中，实现邻接表表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 30 //最大顶点个数
type struct EdgeLinklist{ //边结点
int adjvex;
struct EdgeLinklist *next;
}EdgeLinklist;
typedef struct VexLinklist{ //顶点结点
Elemtype elem;
EdgeLinklist *firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];
创建有向图和无向图邻接表的算法实现：
（1） 创建有向图邻接表
void Create_adj(AdjList adj, int n)
{
for (i=0;i<n;i++){ //初始化顶点数组
scanf(&adj[i].elem);
adj[i].firstedge=NULL;
}
scanf(&i,&j); //输入弧
while (i) {
s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); //创建新的弧结点
s->adgvex=j-1;
s->next=adj[i-1].firstedge; //将新的弧结点插入到相应的位置
adj[i-1].firstegde=s;
scanf(&i,&j); //输入下一条弧
}
}
（2）创建无向图的邻接表
void Create_adj(AdjList adj, int n)
{
for (i=0;i<n;i++){ //初始化邻接表
scanf(&adj[i].elem);
adj[i].firstedge=NULL;
}
scanf(&i,&j); //输入边
while (i) {
s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));
s1->adgvex=j-1;
s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));
s2->adgvex=i-1;
s1->next=adj[i-1].firstedge;
adj[i-1].firstegde=s1;
s2->next=adj[j-1].firstedge;
adj[j-1].firstegde=s2;
scanf(&i,&j);
}
}

第三节 图的遍历

常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。
1． 深度优先遍历
深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。
下面我们讨论一下如何实现深度优先算法。
为了便于在算法中区分顶点是否已被访问过，需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来设置访问标志，其初始值visited[i]（0≤i≤n-1）为"0"，表示邻接表中下标值为i的顶点没有被访问过，一旦该顶点被访问，将visited[i]置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍历起始点的在邻接表中的下标值，其下标从0开始
visited[v]=1; visite(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测：
int visited[0..n-1]={0,0,...0};
void DFSTraverse(AdjList adj)
{
for (v=0;v<n;v++) if (!visited[v]) DFS(adj,v);
}
2．广度优先遍历
对图的广度优先遍历方法描述为：从图中某个顶点v出发，在访问该顶点v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。
下面我们讨论一下实现广度优先遍历算法需要考虑的几个问题：
（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点访问顺序，就可以利用队列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；
（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍历起始点在邻接表中的下标，邻接表中下标从0开始
InitQueue(Q); //Q是队列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}

第四节 最小生成树问题

1．图的生成树和森林
对于一个拥有n个顶点的无向连通图，它的边数一定多余n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边（弧）组成的图被称为原无向图的生成树。显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。

2．最小生成树
在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。
图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边

下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。
构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。
下面我们考虑一下如何实现这个操作过程的算法。
分析 ：（1）它主要有两项操作：按条件选择一条边和将顶点加入到U集合中；（2）网中的每个顶点不是在U集合中，就是在V-U集合中。为了提高算法的时间、空间效率，我们将为这个算法设计一个辅助数组closedge，用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点，在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值，若该顶点进入U集合，则值为0；另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示：
#define MAX_NUM 10
struct {
int adjvex;
float lowcist;
}closedge[MAX_NUM];
整个算法的执行过程可以描述为：
{ 初始化closedge数组的内容；
选择某个顶点k作为生成树的根结点，并将它加入到U集合中；
重复下列操作n-1次：
①选择一条满足条件的边；
②输出这条边的两个端点；
③修改V-U集合中的顶点信息，即与U集合中构成最小权值的边。
}
假设该网以邻接矩阵的形式给出，则完整的算法为：
void Mini_SpanTree(Graph G,int k,int n)
{//G是网的邻接矩阵，k是生成树根结点的序号，n是网的顶点数目
for (j=0;j<n;j++)
if (j!=k) closedge[j]={k,G[k][j]};
closedge[k].lowcost=0;
for (i=1;i<n;i++)
{
k=minmun(closedge);
printf(k,closedge[k].adjvex);
closedge[k].lowcost=0; //将顶点加入U集合中
for (j=0;j<n;j++)
if (closedge[i]&&G[k][j]<closedge[j].lowcost)
closedge[j]={k,G[k][j]};
}
}

第五节 拓扑排序问题

拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。

拓扑排序的方法：
（1）从图中选择一个入度为0的顶点且输出之；
（2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；
反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。
下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。
下面给出算法实现的基本过程：
{ 将所有入度为0的顶点入栈；
当栈非空时重复执行下列操作：
从栈中退出顶点k；
（1）将k顶点的信息输出；
（2）将与k邻接的所有顶点的入度减1。
}
#define MAX_VERTEX_NUM 30 //最大顶点个数
type struct EdgeLinklist{ //边结点
int adjvex;
struct EdgeLinklist *next;
}EdgeLinklist;
typedef struct VexLinklist{ //顶点结点
Elemtype elem;
int indegree; //记录顶点的入度
EdgeLinklist *firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];
下面是拓扑排序的完整算法。
Status TopologicalSort(AdjList adj)
{
InitStack(s);
for (i=0;i<MAX_VERTEX_NUM-1;i++)
if (adj[i].indegree==0) Push(s,i);
while (!StackEmpty(s)) {
Pop(s,i); printf(i);
for (p=adj[i].firstedge;p;p=p->next) {
adj[i].indegree-=1;
if (adj[i].indegree==0) Push(s,i);
}
}
}