上机实习题五图 、实验目的 掌握图的基本存储方法。 2.掌握有关图的操作算法并用高级语言实现 3.熟悉图的各种存储结构及其构造算法,了解实际问题的求解效率与采用何种存储结 构以及有着密切的联系。 4.熟练掌握图的两种搜索路径的遍历方法 二、实验内容 1.如果以无向网表示n个城市之间的通信网络的建设计划,顶点表示城市,边上的权 表示该线路的造价,设计一个方案,使这个通信网的总造价最低 实现提示]这是一个求连通的带权无向图(及网络)的最小代价生成树的问题 建立图的邻接距阵,然后以 prime算法来求最小生成树 [算法实现]这里给出由 R C. Prim提出的求最小代价生成树的算法。设图的顶点 集合Ⅴ有n个顶点,prim算法粗略的描述如下: (1)设置一个顶点的集合S1和一个边的集合TE,S1和TE的初始状态 皆为空集。 (2)选中图中的一个顶点k(从此顶点开始求最小代价生成树),将k 加入集合S1。 (3)重复下列步骤,直至选取了n-1条边: ①选取一条加权最小的边(x,y),其中xS1,Y口Sl。 ②将顶点y加入集合S1,边(x,y)加入集合TE。 下面是用邻接表做为数据结构实现prim算法的程序。 #ingclude # define n5/*n为顶点数*/ #define max 1000.0 typedef struct node ………}//代码 typedef struct ……}//代码 [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 ve Graph(n Grapg G; Void prim( vexnode gp[],intk)/*用邻接表实现prim算法* fint v2linkn), vset[n], parent[n], wIn int x, S, count, I, y, z, f: v2link n=-1 count=0 for(l=0,l<n;1++) if(il=k) vset[[=3 while(acount <n-1)
上机实习题五 图 一、实验目的 1． 掌握图的基本存储方法。 2． 掌握有关图的操作算法并用高级语言实现。 3． 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结 构以及有着密切的联系。 4． 熟练掌握图的两种搜索路径的遍历方法。 二、实验内容 1． 如果以无向网表示 n 个城市之间的通信网络的建设计划，顶点表示城市，边上的权 表示该线路的造价，设计一个方案，使这个通信网的总造价最低。 [实现提示] 这是一个求连通的带权无向图（及网络）的最小代价生成树的问题。 建立图的邻接距阵，然后以 prime 算法来求最小生成树。 [算法实现] 这里给出由 R.C.Prim 提出的求最小代价生成树的算法。设图的顶点 集合 V 有 n 个顶点，prim 算法粗略的描述如下： （1） 设置一个顶点的集合 S1 和一个边的集合 TE,S1 和 TE 的初始状态 皆为空集。 （2） 选中图中的一个顶点 k（从此顶点开始求最小代价生成树），将 k 加入集合 S1。 （3） 重复下列步骤，直至选取了 n-1 条边： ①选取一条加权最小的边（x,y）,其中 x□S1,Y□S1。 ②将顶点 y 加入集合 S1，边（x,y）加入集合 TE。 下面是用邻接表做为数据结构实现 prim 算法的程序。 #ingclude #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)
iptr=G x]. link i y=ptr->no if(veby]=2)&&(pr->wgtwgt f( wetly]=3)/*y在集合v3* 2 sy parenty]=x; wy=ptr->wgt break,/*无最小代价生成树* y=v2linkIx fif (wly]<wxD) f=z y=v2linkly] ink x] 2link[f]=-v2link(x] vset[]=I count +t /*边数记数* printf("Inroot%c:t”G[k]vtx,/输出结点* for(l=0l<n;1++) if(ll=k) printf(G[]. vtx);
{ptr=G[x].link; while(ptr!=Null) { y=ptr->no; if((vset[y]==2)&&(ptr->wgtwgt; } 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);
printf("G(f].vtx) ∥立邻接表 id creatlist( vexnode gaD) r(I=0,1<n;1++) ga[l]. vtx=a'+I if(gali[l[l<max)&&(gali[l[=o)) se=(edgenode")malloc(sizeof(se)) ga[. link; ga[l].link= for(l=0;<n;I++) printf(G[I]. vtx) ve=G[l link
f=parent[I]; printf(“G[f].vtx); } } //建立邻接表 void creatlist(vexnode ga[]) { int I,j,k,e,w; edgenode *se; for(I=0;Ino=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;Ino,ve->wgt); ve=ve->next; } }
prim(G, 4) return o 2.软件专业的学生要学一系列的课程,其中有些课程必须在其先修课程之后才能学 习,具体关系见下表: 课程编码 课程名称 先决条件 程序设计基础 离散数学 C3 数据结构 CI C2 汇编语言 语言的设计和分析 C3 C4 C 计算机原理 11 编译原理 C3C5 C8 操作系统 C3C6 高等数学 性代数 普通物理 C12 数值分析 Cl C9 C10 假使每门课程的学识为一学期,试为该专业的学生设计教学计划,使他们能在最短的时 间内修完这些课程。 实现提示]以停电代表课程,弧代表课程的先后修关系,按表中条件建立有向无环图 的邻接表结构并统计得到初始化的入度为0的顶点,利用拓扑排序算法来进行课程安 排。假定一个进修班的学生必须完成所列的全部课程。在这里,课程代表活动,学习每 门课程的先决条件是学完它的全部先修课,如“遍以技术”课程就必须先修它的两门先 修课程“数据结构”和“算法语言”之后,“高等数学”课程则可以在后修课程之前随 时安排,因为它是基础课程。 通常我们把这种顶点代表活动,边代表活动间先后关系的有向图称为顶点活动网,简称 阿Aov网。一个Aov网应该是一个有向图,既不因该带有回路,因为若带有回路,则 回路的所有活动都无法进行。 在Avo网中,若不存在回路,则所有活动课排列成一个线性序列,使每个活动 的所有前驱活动都排列在该活动的前面,我们称为拓扑序列 Topological orde由Aov 网构造拓扑序列的过程叫做拓扑排序。Aov网的拓扑序列不是唯一的,满足上述定义 的任一线性序列都称作它的拓扑序列。 由Aov网构造拓扑序列的实际意义是:如果按照拓扑序列中的顶点次序进行每 一项活动,就能够保证在开始每一项活动时,他的所有前驱活动都已完成,从而使得整 个工程安顺序进行 由构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0 的顶点为止。 (1)选择一个入度为0的顶点并输出之
prim(G,4); return 0; } 2． 软件专业的学生要学一系列的课程，其中有些课程必须在其先修课程之后才能学 习，具体关系见下表： 课程编码 课程名称 先决条件 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 的顶点为止。 （1） 选择一个入度为 0 的顶点并输出之；
(2)从网中删除该顶点及所有从该顶点出发的边 循环结束时,若输出的顶点数小于网中的顶点数,则输出有回路错误信息,否则 输出的顶点序列就是一种拓扑序列 为了在计算机上实现拓扑排序算法,Aov网采用邻接表表示叫方便,不过要在表 头结点结构中增加一个保存顶点入度的域。在进行拓扑排序中,为了把拓扑排序都保存 起来,而且又便于插入、删除和节省存储,最好的方法是把他们链成一个栈。另一方面, 当一个顶点入度为0时,邻接表中的对应表结点中的入度域( indegree)就没有用了,可 正好利用它作为链栈单元使用,来保储存下一个入度为0的顶点序号,通过所有入度为 0的表头结点中的入度域就可以把入度为0的顶点(对应表头结点)都静态链结起来 在这个链栈中,栈顶指针top指向第一个入度为0的顶点v对应表头向量中的第I个分 量,即v的表头结点),ⅵ的表头结点的如度域指向第二个入度为0的顶点v以此类推,、 最后一个入度为0的表头结点的如度域应置为0(即空指针),表示栈底 采用邻接表作为实现上述算法的数据结构。算法首先扫描邻接表,求出图中每 个顶点的如度存于数组IN中,然后将所有入度为0的顶点组成一个链表并作为链接存 储的栈进行操作,top指向栈顶。 算法实现] ypedef struct node Int no struct node *next typedef struct char vtx. edgenode *link. i venose typedef vexnode Graph [n Graph G ∥拓扑排序 void topolo( Graph g) int top, count, I, j; de *p; int INn]; for(l=0,1<nl++)∥/数组初始化 for(l=0,1<nI++)求图中个顶点的入度 ip=gIl]. link while(pl=null)
（2） 从网中删除该顶点及所有从该顶点出发的边。 循环结束时，若输出的顶点数小于网中的顶点数，则输出有回路错误信息，否则 输出的顶点序列就是一种拓扑序列 为了在计算机上实现拓扑排序算法，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) {
P=p->next for(l=0l=0) k=glop].vtx; printi(k,/输出顶点 p=glop). link; top=IN topl while(pl=null Jp->no, If(N[j=0)∥将入度为0的顶点插入栈中 INGI=top p-p->nex if(count<n printf("in the network has a cycle) typedef struct node float wgt; struct node *ne
j=p->no; IN[j]++; P=p->next; } } top=-1; for(I=0;I=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;
ypedef struct i vexnode typedef vexnode Graph(n]; /foyd算法,求最短路径 void floyd( Graph G, float A[nJ[n], int p[[)) int l j, k; for(l=0,1和,比较路径(Lj)和路径(L,0j)的长度,取长度最短者为当前求得的 从顶点I到顶点j且中间顶点编号不大于0的最短路径,、记为(I,……j),其长度存 于A1[I中,然后再考虑路径(L,…,1,…j),由于(1,…j)和(L-…,1,…j)是从顶 点I到顶点1即从顶点1到顶点j中间顶点编号不大于1的最短路径,比较路径(,…,1) 和路径(L-…,1,…j)的长度,若后者较短,则路径(1,,1,j)即为当前求得的从 顶点I到顶点j中间顶点编号不大于1的最短路径,其长度存于A2中,…… 以此类推,逐个插入图的每个顶点,最后必将求得顶点I到顶点j且中间顶点编号 不大于n-1的最短路径。在k+1次迭代时,矩阵Ak+1[lj的值为:
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和,比较路径（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]的值为：
Ak+lll,j=min 其中Ak+1表示经过k+1次迭代后得到的值,他等于从I到j中间顶点编号 不大于k的最短长度 下面是 R WFLOYD的求每段顶点之间最短路径算法的C语言程序。程序中矩阵A用来进 行n次迭代,矩阵P用来纪录路径。Pj为迭代过程中当前得到的从顶点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 的最短 路径上最后被插入的那个顶点