第 6章 图本章中介绍下列主要内容：
图的定义
图的存储结构
图的遍历操作
图的几个典型问题退出
6.1 图的定义
6.2 图的存储结构
6.3 图的遍历
6.4 最小生成树问题
6.5 拓扑排序问题
6.1 图的定义
6.1.1 定义图 是由结点的有穷集合 V和边的集合 E组成。其中，
为了与树形结构加以区别，在图结构中常常将结点称为 顶点,边 是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
图 6-1
(a) (b)
在上面两个图结构中，一个是 有向图,即每条边都有方向，另一个是 无向图,即每条边都没有方向。
在有向图中，通常将边称作 弧,含箭头的一端称为 弧头,另一端称为 弧尾,记作 <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都有路径，则称该图为 强连通图 ；否则，
将其中的极大连通子图称为 强连通分量 。
6.1.2 图的基本操作基本操作：
（ 1）创建一个图结构 CreateGraph(G)
（ 2）检索给定顶点 LocateVex(G,item)
（ 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)
6.2 图的存储结构
6.2.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”的个数的一半，这是因为每条边在矩阵中描述了两次。
图 6-4
图 6-5
在 C 语言中，实现邻接矩阵表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 20
typedef struct graph{
EntryType
item[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int n;
}Graph;
6.2.2 邻接表边结点的结构为：
a d jv e x n e x t
adjvex是该边或弧依附的顶点在数组中的下标，
next是指向下一条边或弧结点的指针。
图 6-6
item是顶点内容,firstedge是指向第一条边或弧结点的指针。
在 C语言中，实现邻接表表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 30 //最大顶点个数
type struct EdgeNode{ //边结点构成一维数组的顶点结构为：
it e m f ir s t e d g e
int adjvex;
struct EdgeNode *next;
}EdgeNode;
typedef struct VexNode{ //顶点结点
EntryType item;
EdgeNode *firstedge;
}VexNode,AdjList[MAX_VERTEX_NUM];
创建有向图和无向图邻接表的算法实现：
(1)创建有向图邻接表
void Create_adj(AdjList adj,int n)
{
for (i=0;i<n;i++){ //初始化顶点数组
scanf(&adj[i].item);
adj[i].firstedge=NULL;
}
scanf(&i,&j); //输入弧
while (i) {
s=(EdgeNode*)malloc(sizeof(EdgeNode));
//创建新的弧结点
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].item);
adj[i].firstedge=NULL;
}
scanf(&i,&j); //输入边
while (i) {
s1=(EdgeNode*)malloc(sizeof(EdgeNode));
s1->adgvex=j-1;
s2=(EdgeNode*)malloc(sizeof(EdgeNode));
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);
}
}
6.3 图的遍历常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。
6.3.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].item);
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);
}
6.3.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].item); 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].item);
EnQueue(Q,w->adjvex); }
}
}
6.4 最小生成树问题
6.4.1 图的生成树和森林对于一个拥有 n个顶点的无向连通图，它的边数一定多余 n-1条。若从中选择 n-1条边，使得无向图仍然连通，则由 n个顶点及这 n-1条边（弧）组成的图被称为原无向图的 生成树 。显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。
图 6-10
图 6-11
图 6-12
图 6-13
6.4.2 最小生成树在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为 权 。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作 网 。
图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但 n个结点的生成树一定有 n-
1条边。
图 6-14
图 6-15
下面我们计算一下上面两棵生成树的权值之和。
第一棵生成树的权值总和是,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]};
}
}
6.5 拓扑排序问题拓扑排序是有向图的一个重要操作。在给定的有向图 G中，若顶点序列 vi1,vi2,...,vin满足下列条件：若在有向图 G中从顶点 vi到顶点 vj有一条路径，则在序列中顶点 vi必在顶点 vj之前，便称这个序列为一个 拓扑序列 。
求一个有向图拓扑序列的过程称为 拓扑排序 。
举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。
课 程 代号课程名称 先修课程
c1 高等数学
c2 计算机基础
c3 离散数学 c 1,c 2
c4 数据结构 c 2,c 3
c5 程序设计 c2
c6 编译原理 c 4,c 5
c7 操作系统 c 4,c 9
c8 普通物理 c1
c9 计算机原理 c8
图 6-16
拓扑排序的方法：
（ 1）从图中选择一个入度为 0的顶点且输出之；
（ 2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；
反复执行这两个步骤，直到所有的顶点都被输出，
输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为 0的顶点，选择注：表中 c1~c9列表示的是每个顶点的入度。
下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。
下面给出算法实现的基本过程：
{ 将所有入度为 0的顶点入栈；
当栈非空时重复执行下列操作：
从栈中退出顶点 k；
（ 1） 将 k顶点的信息输出；
（ 2） 将与 k邻接的所有顶点的入度减 1。
}
#define MAX_VERTEX_NUM 30 //最大顶点个数
type struct EdgeNode{ //边结点
int adjvex;
struct EdgeNode *next;
}EdgeNode;
typedef struct VexNode{ //顶点结点
EntryType item;
int indegree; //记录顶点的入度
EdgeNode *firstedge;
}VexNode,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);
}
}
}
图的定义
图的存储结构
图的遍历操作
图的几个典型问题退出
6.1 图的定义
6.2 图的存储结构
6.3 图的遍历
6.4 最小生成树问题
6.5 拓扑排序问题
6.1 图的定义
6.1.1 定义图 是由结点的有穷集合 V和边的集合 E组成。其中，
为了与树形结构加以区别，在图结构中常常将结点称为 顶点,边 是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
图 6-1
(a) (b)
在上面两个图结构中，一个是 有向图,即每条边都有方向，另一个是 无向图,即每条边都没有方向。
在有向图中，通常将边称作 弧,含箭头的一端称为 弧头,另一端称为 弧尾,记作 <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都有路径，则称该图为 强连通图 ；否则，
将其中的极大连通子图称为 强连通分量 。
6.1.2 图的基本操作基本操作：
（ 1）创建一个图结构 CreateGraph(G)
（ 2）检索给定顶点 LocateVex(G,item)
（ 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)
6.2 图的存储结构
6.2.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”的个数的一半，这是因为每条边在矩阵中描述了两次。
图 6-4
图 6-5
在 C 语言中，实现邻接矩阵表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 20
typedef struct graph{
EntryType
item[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int n;
}Graph;
6.2.2 邻接表边结点的结构为：
a d jv e x n e x t
adjvex是该边或弧依附的顶点在数组中的下标，
next是指向下一条边或弧结点的指针。
图 6-6
item是顶点内容,firstedge是指向第一条边或弧结点的指针。
在 C语言中，实现邻接表表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 30 //最大顶点个数
type struct EdgeNode{ //边结点构成一维数组的顶点结构为：
it e m f ir s t e d g e
int adjvex;
struct EdgeNode *next;
}EdgeNode;
typedef struct VexNode{ //顶点结点
EntryType item;
EdgeNode *firstedge;
}VexNode,AdjList[MAX_VERTEX_NUM];
创建有向图和无向图邻接表的算法实现：
(1)创建有向图邻接表
void Create_adj(AdjList adj,int n)
{
for (i=0;i<n;i++){ //初始化顶点数组
scanf(&adj[i].item);
adj[i].firstedge=NULL;
}
scanf(&i,&j); //输入弧
while (i) {
s=(EdgeNode*)malloc(sizeof(EdgeNode));
//创建新的弧结点
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].item);
adj[i].firstedge=NULL;
}
scanf(&i,&j); //输入边
while (i) {
s1=(EdgeNode*)malloc(sizeof(EdgeNode));
s1->adgvex=j-1;
s2=(EdgeNode*)malloc(sizeof(EdgeNode));
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);
}
}
6.3 图的遍历常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。
6.3.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].item);
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);
}
6.3.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].item); 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].item);
EnQueue(Q,w->adjvex); }
}
}
6.4 最小生成树问题
6.4.1 图的生成树和森林对于一个拥有 n个顶点的无向连通图，它的边数一定多余 n-1条。若从中选择 n-1条边，使得无向图仍然连通，则由 n个顶点及这 n-1条边（弧）组成的图被称为原无向图的 生成树 。显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。
图 6-10
图 6-11
图 6-12
图 6-13
6.4.2 最小生成树在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为 权 。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作 网 。
图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但 n个结点的生成树一定有 n-
1条边。
图 6-14
图 6-15
下面我们计算一下上面两棵生成树的权值之和。
第一棵生成树的权值总和是,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]};
}
}
6.5 拓扑排序问题拓扑排序是有向图的一个重要操作。在给定的有向图 G中，若顶点序列 vi1,vi2,...,vin满足下列条件：若在有向图 G中从顶点 vi到顶点 vj有一条路径，则在序列中顶点 vi必在顶点 vj之前，便称这个序列为一个 拓扑序列 。
求一个有向图拓扑序列的过程称为 拓扑排序 。
举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。
课 程 代号课程名称 先修课程
c1 高等数学
c2 计算机基础
c3 离散数学 c 1,c 2
c4 数据结构 c 2,c 3
c5 程序设计 c2
c6 编译原理 c 4,c 5
c7 操作系统 c 4,c 9
c8 普通物理 c1
c9 计算机原理 c8
图 6-16
拓扑排序的方法：
（ 1）从图中选择一个入度为 0的顶点且输出之；
（ 2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；
反复执行这两个步骤，直到所有的顶点都被输出，
输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为 0的顶点，选择注：表中 c1~c9列表示的是每个顶点的入度。
下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。
下面给出算法实现的基本过程：
{ 将所有入度为 0的顶点入栈；
当栈非空时重复执行下列操作：
从栈中退出顶点 k；
（ 1） 将 k顶点的信息输出；
（ 2） 将与 k邻接的所有顶点的入度减 1。
}
#define MAX_VERTEX_NUM 30 //最大顶点个数
type struct EdgeNode{ //边结点
int adjvex;
struct EdgeNode *next;
}EdgeNode;
typedef struct VexNode{ //顶点结点
EntryType item;
int indegree; //记录顶点的入度
EdgeNode *firstedge;
}VexNode,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);
}
}
}
