上机实习题五 图实验目的掌握图的基本存储方法。
掌握有关图的操作算法并用高级语言实现。
熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构以及有着密切的联系。
熟练掌握图的两种搜索路径的遍历方法。
实验内容如果以无向网表示n个城市之间的通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通信网的总造价最低。
[实现提示] 这是一个求连通的带权无向图（及网络）的最小代价生成树的问题。建立图的邻接距阵，然后以prime算法来求最小生成树。
[算法实现] 这里给出由R.C.Prim提出的求最小代价生成树的算法。设图的顶点集合V有n个顶点，prim算法粗略的描述如下：
设置一个顶点的集合S1和一个边的集合TE,S1和TE的初始状态皆为空集。
选中图中的一个顶点k（从此顶点开始求最小代价生成树），将k加入集合S1。
重复下列步骤，直至选取了n-1条边：
①选取一条加权最小的边（x,y）,其中x□S1,Y□S1。
②将顶点y加入集合S1，边（x,y）加入集合TE。
下面是用邻接表做为数据结构实现prim算法的程序。
#ingclude <stdio.h>
#define n 5/* n为顶点数*/
#define max 1000.0
typedef struct node
{………}//代码
typedef struct
{………}//代码
float gali [n] [n]={{0,2,12,10,max},{2,0,8,max,9},{12,8,0,6,3,},{10,max,6,0,7},{max,9,3,7,0}};
typedef vesnode Graph[n];
Grapg G;
Void prim(vexnode Gp [ ],int k)/*用邻接表实现prim算法*/
{int v2link[n],vset[n],parent[n],w[n];
edgenode *ptr;
int x,s,ecount,I,y,z,f;
s=-1;
v2link[n]=-1;
ecount=0;
for(I=0;I<n;I++)
if(i!=k) vset[i]=3;
while(ecount <n-1)
{ptr=G[x].link;
while(ptr!=Null)
{ y=ptr->no;
if((vset[y]==2)&&(ptr->wgt<w[y]))/*y在集合v2*/
{
parent[y]=x;
w[y]=ptr->wgt;
}
if (vset[y]==3) /*y在集合v3*/
{
vset[y]=2;
v2link[y]=s;
s=y;
parent[y]=x;
w[y]=ptr->wgt;
}
ptr=ptr->next;
}
if(s==-1)
break; /*无最小代价生成树*/
z=x=s;
y=v2link[x];
f=-1;
while(y!=-1)
{if (w[y]<w[x])
{x=y;
f=z;
}
z=y;
y=v2link[y];
}
if(f==-1)
s=v2link[x];
else
v2link[f]=v2link[x];
vset[x]=1;
ecount ++; /*边数记数*/
}
printf(“\nroot%c:\t”,G[k].vtx); /*输出结点*/
for(I=0;I<n;I++)
{
if(I!=k)
{
printf(G[I].vtx);
f=parent[I];
printf(“G[f].vtx);
}
}
//建立邻接表
void creatlist(vexnode ga[])
{
int I,j,k,e,w;
edgenode *se;
for(I=0;I<n;I++)
{
ga[I].vtx=’a’+I;
for(j=0;j<n;j++)
{
if((gali[I][j]<max)&&(gali[I][j]!=0))
{
se=(edgenode*)malloc(sizeof(*se));
se->no=j;
se->next=ga[I].link;
se->wgt=gali[I][j];
ga[I].link=se;
}
}
}
}
main()
{
int I;
edgenode *ve;
creatlist(G);
for(I=0;I<n;I++)
{
printf(G[I].vtx);
ve=G[I].link;
while(ve!=null)
{
printf(ve->no,ve->wgt);
ve=ve->next;
}
}
prim(G,4);
return 0;
}
软件专业的学生要学一系列的课程，其中有些课程必须在其先修课程之后才能学习，具体关系见下表：
课程编码
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1 C2
C4
汇编语言
C1
C5
语言的设计和分析
C3 C4
C6
计算机原理
C11
C7
编译原理
C3C5
C8
操作系统
C3C6
C9
高等数学
无
C10
线性代数
C9
C11
普通物理
C9
C12
数值分析
C1 C9 C10
假使每门课程的学识为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。
[实现提示]以停电代表课程，弧代表课程的先后修关系，按表中条件建立有向无环图的邻接表结构并统计得到初始化的入度为0的顶点，利用拓扑排序算法来进行课程安排。假定一个进修班的学生必须完成所列的全部课程。在这里，课程代表活动，学习每门课程的先决条件是学完它的全部先修课，如“遍以技术”课程就必须先修它的两门先修课程“数据结构”和“算法语言”之后,“高等数学”课程则可以在后修课程之前随时安排，因为它是基础课程。
通常我们把这种顶点代表活动，边代表活动间先后关系的有向图称为顶点活动网，简称阿Aov网。一个Aov网应该是一个有向图，既不因该带有回路，因为若带有回路，则回路的所有活动都无法进行。
在Avo网中，若不存在回路，则所有活动课排列成一个线性序列，使每个活动的所有前驱活动都排列在该活动的前面，我们称为拓扑序列Topological orde由Aov网构造拓扑序列的过程叫做拓扑排序。Aov网的拓扑序列不是唯一的，满足上述定义的任一 线性序列都称作它的拓扑序列。
由Aov网构造拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序进行每一项活动，就能够保证在开始每一项活动时，他的所有前驱活动都已完成，从而使得整个工程安顺序进行由构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
选择一个入度为0的顶点并输出之；
从网中删除该顶点及所有从该顶点出发的边。
循环结束时，若输出的顶点数小于网中的顶点数，则输出有回路错误信息，否则输出的顶点序列就是一种拓扑序列为了在计算机上实现拓扑排序算法，Aov网采用邻接表表示叫方便，不过要在表头结点结构中增加一个保存顶点入度的域。在进行拓扑排序中，为了把拓扑排序都保存起来，而且又便于插入、删除和节省存储，最好的方法是把他们链成一个栈。另一方面，当一个顶点入度为0时，邻接表中的对应表结点中的入度域(indegree)就没有用了，可正好利用它作为链栈单元使用，来保储存下一个入度为0的顶点序号，通过所有入度为0的表头结点中的入度域就可以把 入度为0的顶点（对应表头结点）都静态链结起来。在这个链栈中，栈顶指针top指向第一个入度为0的顶点vi(对应表头向量中的第I个分量，即vi的表头结点)，vi的表头结点的如度域指向第二个入度为0的顶点vj,以此类推，、最后一个入度为0的表头结点的如度域应置为0（即空指针），表示栈底。
采用邻接表作为实现上述算法的数据结构。算法首先扫描邻接表，求出图中每一个顶点的如度存于数组IN中，然后将所有入度为0的顶点组成一个链表并作为链接存储的栈进行操作，top指向栈顶。
[算法实现]
typedef struct node
{
int no;
float wgt;
struct node *next;
}edgennode;
typedef struct
{
char vtx;
edgenode *link;
}vexnode;
typedef vexnode Graph [n];
Graph G;
//拓扑排序
void topolo(Graph g)
{
int top,count,I,j;
char k;
edgenode *p;
int IN[n];
for(I=0;I<n;I++)//数组初始化
IN[I]=0;
for(I=0;I<n;I++)//求图中个顶点的入度
{p=g[I].link;
while(p!=null)
{
j=p->no;
IN[j]++;
P=p->next;
}
}
top=-1;
for(I=0;I<n;I++)//将入度为0的顶点组成一个栈
if(IN[I]==0)
{
IN[I]=top;
Top=I;
}
count=0;
while(top>=0)
{
k=g[top].vtx;
printf(k);//输出顶点
p=g[top].link;
top=IN[top];
count++;
while(p!=null)
{
j=p->no;
IN[j]--;
If(IN[j]==0)//将入度为0的顶点插入栈中
{
IN[j]=top;
Top=j;
}
p=p->next;
}
}
if(count<n)
printf(“\n the network has a cycle”);
}
3.
typedef struct node
{
int no;
float wgt;
struct node *next;
}
edgenode;
typedef struct
{
char vtx;
edgenode*link;
}vexnode;
typedef vexnode Graph[n];
/floyd算法，求最短路径
void floyd(Graph G,float A[n][n],int p[n][n])
{
int I,j,k;
for(I=0;I<n;I++)
for(j=0;j<n;j++)
{
A[I][j]=G[I][j];
P[I][j]=-1;
}
for(k=0;k<n;k++)
for(I=0;I<n;I++)
for(j=0;j<n;j++)
if(A[I][k]+A[k][j])
{
p[I][j]=A[I][k]+A[k][j];
}
}
假设以一个带权有向图表示某一区域的公交线路网，途中顶点表示一些区域中的重要场所，弧代表以有的公交线路，弧上的权代表该线路上的票价（或搭乘所要的时间）。试设计一个交通指南系统，直到来咨询者以最低的票价活最少的时间从区域中的某一场所到达另一场所。
[实现提示] 该问题可以归结为一个求带权有向图中顶点间最短路径的问题。分别建立以票价后搭乘时间为权的邻结矩阵，以FLOYD算法来求最短路经济起路径长度。
设图G=(V,E)的顶点集合V={0,1,…., n-1},图用邻接矩阵表示。一开始，若弧〈I,矩阵A进行n次迭代来计算每队顶点间的最短路径，迭代过程中得到的一个矩阵序列A0,A1,…..,An,矩阵元素An[i,j]的值即为从顶点I到顶点j的最短路径长度。首先在路径（I,j）中插入顶点0，考虑路径（I,0,j），若该路径存在，即图中有弧<I,0>和<0,j>,比较路径（I,j）和路径（I,0,j）的长度，取长度最短者为当前求得的从顶点I到顶点j且中间顶点编号不大于0的最短路径，、记为（I,…..j）,其长度存于A1[I,j]中，然后再考虑路径（I,…,1,…j）,由于 （I,…..j）和（I,…,1,…j）是从顶点I到顶点1即从顶点1到顶点j中间顶点编号不大于1的最短路径，比较路径(I,…,1)和路径 （I,…,1,…j）的长度，若后者较短，则路径（I,…,1,…j）即为当前求得的从顶点I到顶点j中间顶点编号不大于1的最短路径,其长度存于A2[I,j]中，………，以此类推，逐个插入图的每个顶点，最后必将求得顶点I到顶点j且中间顶点编号不大于n-1的最短路径。在k+1次迭代时，矩阵Ak+1[I,j]的值为：
A k+1[I,j]=min
其中A k+1[I,j]表示经过k+1次迭代后得到的值，他等于从I到j中间顶点编号不大于k的最短长度。
下面是R.W.FLOYD的求每段顶点之间最短路径算法的C语言程序。程序中矩阵A用来进行n次迭代，矩阵P用来纪录路径。P[I,j]为迭代过程中当前得到的从顶点I到顶点j的最短路径上最后被插入的那个顶点。
掌握有关图的操作算法并用高级语言实现。
熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构以及有着密切的联系。
熟练掌握图的两种搜索路径的遍历方法。
实验内容如果以无向网表示n个城市之间的通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通信网的总造价最低。
[实现提示] 这是一个求连通的带权无向图（及网络）的最小代价生成树的问题。建立图的邻接距阵，然后以prime算法来求最小生成树。
[算法实现] 这里给出由R.C.Prim提出的求最小代价生成树的算法。设图的顶点集合V有n个顶点，prim算法粗略的描述如下：
设置一个顶点的集合S1和一个边的集合TE,S1和TE的初始状态皆为空集。
选中图中的一个顶点k（从此顶点开始求最小代价生成树），将k加入集合S1。
重复下列步骤，直至选取了n-1条边：
①选取一条加权最小的边（x,y）,其中x□S1,Y□S1。
②将顶点y加入集合S1，边（x,y）加入集合TE。
下面是用邻接表做为数据结构实现prim算法的程序。
#ingclude <stdio.h>
#define n 5/* n为顶点数*/
#define max 1000.0
typedef struct node
{………}//代码
typedef struct
{………}//代码
float gali [n] [n]={{0,2,12,10,max},{2,0,8,max,9},{12,8,0,6,3,},{10,max,6,0,7},{max,9,3,7,0}};
typedef vesnode Graph[n];
Grapg G;
Void prim(vexnode Gp [ ],int k)/*用邻接表实现prim算法*/
{int v2link[n],vset[n],parent[n],w[n];
edgenode *ptr;
int x,s,ecount,I,y,z,f;
s=-1;
v2link[n]=-1;
ecount=0;
for(I=0;I<n;I++)
if(i!=k) vset[i]=3;
while(ecount <n-1)
{ptr=G[x].link;
while(ptr!=Null)
{ y=ptr->no;
if((vset[y]==2)&&(ptr->wgt<w[y]))/*y在集合v2*/
{
parent[y]=x;
w[y]=ptr->wgt;
}
if (vset[y]==3) /*y在集合v3*/
{
vset[y]=2;
v2link[y]=s;
s=y;
parent[y]=x;
w[y]=ptr->wgt;
}
ptr=ptr->next;
}
if(s==-1)
break; /*无最小代价生成树*/
z=x=s;
y=v2link[x];
f=-1;
while(y!=-1)
{if (w[y]<w[x])
{x=y;
f=z;
}
z=y;
y=v2link[y];
}
if(f==-1)
s=v2link[x];
else
v2link[f]=v2link[x];
vset[x]=1;
ecount ++; /*边数记数*/
}
printf(“\nroot%c:\t”,G[k].vtx); /*输出结点*/
for(I=0;I<n;I++)
{
if(I!=k)
{
printf(G[I].vtx);
f=parent[I];
printf(“G[f].vtx);
}
}
//建立邻接表
void creatlist(vexnode ga[])
{
int I,j,k,e,w;
edgenode *se;
for(I=0;I<n;I++)
{
ga[I].vtx=’a’+I;
for(j=0;j<n;j++)
{
if((gali[I][j]<max)&&(gali[I][j]!=0))
{
se=(edgenode*)malloc(sizeof(*se));
se->no=j;
se->next=ga[I].link;
se->wgt=gali[I][j];
ga[I].link=se;
}
}
}
}
main()
{
int I;
edgenode *ve;
creatlist(G);
for(I=0;I<n;I++)
{
printf(G[I].vtx);
ve=G[I].link;
while(ve!=null)
{
printf(ve->no,ve->wgt);
ve=ve->next;
}
}
prim(G,4);
return 0;
}
软件专业的学生要学一系列的课程，其中有些课程必须在其先修课程之后才能学习，具体关系见下表：
课程编码
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1 C2
C4
汇编语言
C1
C5
语言的设计和分析
C3 C4
C6
计算机原理
C11
C7
编译原理
C3C5
C8
操作系统
C3C6
C9
高等数学
无
C10
线性代数
C9
C11
普通物理
C9
C12
数值分析
C1 C9 C10
假使每门课程的学识为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。
[实现提示]以停电代表课程，弧代表课程的先后修关系，按表中条件建立有向无环图的邻接表结构并统计得到初始化的入度为0的顶点，利用拓扑排序算法来进行课程安排。假定一个进修班的学生必须完成所列的全部课程。在这里，课程代表活动，学习每门课程的先决条件是学完它的全部先修课，如“遍以技术”课程就必须先修它的两门先修课程“数据结构”和“算法语言”之后,“高等数学”课程则可以在后修课程之前随时安排，因为它是基础课程。
通常我们把这种顶点代表活动，边代表活动间先后关系的有向图称为顶点活动网，简称阿Aov网。一个Aov网应该是一个有向图，既不因该带有回路，因为若带有回路，则回路的所有活动都无法进行。
在Avo网中，若不存在回路，则所有活动课排列成一个线性序列，使每个活动的所有前驱活动都排列在该活动的前面，我们称为拓扑序列Topological orde由Aov网构造拓扑序列的过程叫做拓扑排序。Aov网的拓扑序列不是唯一的，满足上述定义的任一 线性序列都称作它的拓扑序列。
由Aov网构造拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序进行每一项活动，就能够保证在开始每一项活动时，他的所有前驱活动都已完成，从而使得整个工程安顺序进行由构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
选择一个入度为0的顶点并输出之；
从网中删除该顶点及所有从该顶点出发的边。
循环结束时，若输出的顶点数小于网中的顶点数，则输出有回路错误信息，否则输出的顶点序列就是一种拓扑序列为了在计算机上实现拓扑排序算法，Aov网采用邻接表表示叫方便，不过要在表头结点结构中增加一个保存顶点入度的域。在进行拓扑排序中，为了把拓扑排序都保存起来，而且又便于插入、删除和节省存储，最好的方法是把他们链成一个栈。另一方面，当一个顶点入度为0时，邻接表中的对应表结点中的入度域(indegree)就没有用了，可正好利用它作为链栈单元使用，来保储存下一个入度为0的顶点序号，通过所有入度为0的表头结点中的入度域就可以把 入度为0的顶点（对应表头结点）都静态链结起来。在这个链栈中，栈顶指针top指向第一个入度为0的顶点vi(对应表头向量中的第I个分量，即vi的表头结点)，vi的表头结点的如度域指向第二个入度为0的顶点vj,以此类推，、最后一个入度为0的表头结点的如度域应置为0（即空指针），表示栈底。
采用邻接表作为实现上述算法的数据结构。算法首先扫描邻接表，求出图中每一个顶点的如度存于数组IN中，然后将所有入度为0的顶点组成一个链表并作为链接存储的栈进行操作，top指向栈顶。
[算法实现]
typedef struct node
{
int no;
float wgt;
struct node *next;
}edgennode;
typedef struct
{
char vtx;
edgenode *link;
}vexnode;
typedef vexnode Graph [n];
Graph G;
//拓扑排序
void topolo(Graph g)
{
int top,count,I,j;
char k;
edgenode *p;
int IN[n];
for(I=0;I<n;I++)//数组初始化
IN[I]=0;
for(I=0;I<n;I++)//求图中个顶点的入度
{p=g[I].link;
while(p!=null)
{
j=p->no;
IN[j]++;
P=p->next;
}
}
top=-1;
for(I=0;I<n;I++)//将入度为0的顶点组成一个栈
if(IN[I]==0)
{
IN[I]=top;
Top=I;
}
count=0;
while(top>=0)
{
k=g[top].vtx;
printf(k);//输出顶点
p=g[top].link;
top=IN[top];
count++;
while(p!=null)
{
j=p->no;
IN[j]--;
If(IN[j]==0)//将入度为0的顶点插入栈中
{
IN[j]=top;
Top=j;
}
p=p->next;
}
}
if(count<n)
printf(“\n the network has a cycle”);
}
3.
typedef struct node
{
int no;
float wgt;
struct node *next;
}
edgenode;
typedef struct
{
char vtx;
edgenode*link;
}vexnode;
typedef vexnode Graph[n];
/floyd算法，求最短路径
void floyd(Graph G,float A[n][n],int p[n][n])
{
int I,j,k;
for(I=0;I<n;I++)
for(j=0;j<n;j++)
{
A[I][j]=G[I][j];
P[I][j]=-1;
}
for(k=0;k<n;k++)
for(I=0;I<n;I++)
for(j=0;j<n;j++)
if(A[I][k]+A[k][j])
{
p[I][j]=A[I][k]+A[k][j];
}
}
假设以一个带权有向图表示某一区域的公交线路网，途中顶点表示一些区域中的重要场所，弧代表以有的公交线路，弧上的权代表该线路上的票价（或搭乘所要的时间）。试设计一个交通指南系统，直到来咨询者以最低的票价活最少的时间从区域中的某一场所到达另一场所。
[实现提示] 该问题可以归结为一个求带权有向图中顶点间最短路径的问题。分别建立以票价后搭乘时间为权的邻结矩阵，以FLOYD算法来求最短路经济起路径长度。
设图G=(V,E)的顶点集合V={0,1,…., n-1},图用邻接矩阵表示。一开始，若弧〈I,矩阵A进行n次迭代来计算每队顶点间的最短路径，迭代过程中得到的一个矩阵序列A0,A1,…..,An,矩阵元素An[i,j]的值即为从顶点I到顶点j的最短路径长度。首先在路径（I,j）中插入顶点0，考虑路径（I,0,j），若该路径存在，即图中有弧<I,0>和<0,j>,比较路径（I,j）和路径（I,0,j）的长度，取长度最短者为当前求得的从顶点I到顶点j且中间顶点编号不大于0的最短路径，、记为（I,…..j）,其长度存于A1[I,j]中，然后再考虑路径（I,…,1,…j）,由于 （I,…..j）和（I,…,1,…j）是从顶点I到顶点1即从顶点1到顶点j中间顶点编号不大于1的最短路径，比较路径(I,…,1)和路径 （I,…,1,…j）的长度，若后者较短，则路径（I,…,1,…j）即为当前求得的从顶点I到顶点j中间顶点编号不大于1的最短路径,其长度存于A2[I,j]中，………，以此类推，逐个插入图的每个顶点，最后必将求得顶点I到顶点j且中间顶点编号不大于n-1的最短路径。在k+1次迭代时，矩阵Ak+1[I,j]的值为：
A k+1[I,j]=min
其中A k+1[I,j]表示经过k+1次迭代后得到的值，他等于从I到j中间顶点编号不大于k的最短长度。
下面是R.W.FLOYD的求每段顶点之间最短路径算法的C语言程序。程序中矩阵A用来进行n次迭代，矩阵P用来纪录路径。P[I,j]为迭代过程中当前得到的从顶点I到顶点j的最短路径上最后被插入的那个顶点。
