1、数据结构实验六七八实验六 图的遍历一、实验目的1、熟悉图的各种存储结构及其构造算法2、熟练掌握图的两种搜索路径的遍历:遍历的逻辑定义、深度优先搜索的两种形式(递归和非递归)和广度优先搜索的算法。3、应用图的遍历算法求解各种简单路径问题。4、理解教科书中讨论的各种图的算法。二、实验预备知识本实验的重点:深度优先搜索和广度优先搜索。图的遍历:和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。图的深度优先遍历:假设给定初始状态图G中的所有顶点均未
2、曾访问过。在G中任选一顶点v出发,首先访问出发点v,并将其标记为已访问过,然后依次从v出发搜索v的每个邻接点。若该邻结点未曾访问过,则以该邻结点为新的出发点继续进行深度优先遍历,直至图中所有和点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均被访问为止。 (a)无向图 G (b)图G深度优先过程深度优先遍历序列:v1v2v4v5v3v6v7图的广度优先遍历:设初始状态图G中的所有顶点均未访问过。在G中任选一顶点v,首先访问出发点v,接着依次访问v的所有邻接点,然后再依次访问与邻接的所有未曾访问过的顶点,并使“先被
3、访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。依此类推,直至图中所有和点v有路径相通的顶点都已访问到。若此时图中尚有顶点未被访问,则另选图中的一个未被访问的顶点作起始点,重复上述过程,直到图中所有顶点都被访问到为止。(c)无向图G (d)图G广度优先搜索过程广度悠闲遍历序列:v1v2v3v4v5v6v7v8v9三、实验要求1、掌握图的遍历思想以及其特点。2、选择程序上机进行调试找出问题、保存和打印出程序的运行结果。3、上机学会运用图的思想解决实际问题。4、课后尝试自己编写程序并上机运行得出结果。深度遍历图,邻接表加递归#include#include#include#define
4、MAX 100typedef struct Linknode int adjvex; /int info; struct Linknode *next;LinkNode;typedef struct Vexnode int vexdata; LinkNode *first;VexNode;typedef struct int vexnum; VexNode adjlist100;ALGraph;ALGraph G;int preMAX,pathMAX;void create();void print();void DFS(int u,int v,int d);void main() creat
5、e(); /print(); DFS(2,2,-1);void create() int i,tempi; LinkNode *p,*q; freopen(in.txt,r,stdin); /freopen(out.txt,w,stdout); scanf(%d,&G.vexnum); /scanf(%c,&temp); for(i=0;iG.vexnum;i+) scanf(%d,&G.adjlisti.vexdata); G.adjlisti.first=NULL; /scanf(%c,&temp); for(i=0;iadjvex=tempi; q=G.adjlisti.first; G
6、.adjlisti.first=p; p-next=q; scanf(%d,&tempi); void print() int i; LinkNode *p; for(i=0;iadjvex); p=p-next; printf(n); void DFS(int u,int v,int d) int i,temp; LinkNode *p; preu=1; d+; pathd=u; p=G.adjlistu.first; if(u=v ) for(i=0;iadjvex; if(pretemp=0) DFS(temp,v,d); p=p-next; preu=0; d-; void print
7、_path(int pre,int v) if(prev!=v) print_path(pre,prev); printf(%d ,v);实验七 最小生成树一、实验目的1、图的邻接矩阵、邻接表和边集数组表示。2、掌握建立图的邻接矩阵的算法,由邻接矩阵转换为邻接表和边集数组的算法。3、熟悉最小生成树的构造。4、熟悉并掌握求图的最小生成树的普里姆算法克鲁斯卡尔算法。二、实验预备知识掌握图的概念、图的邻接矩阵表示法和邻接表表示法、图的深度和广度优先遍历、生成树和最小生成树、树的最短路径、拓扑排序。有向图:若图G中的每条边都是有方向的,则称G为有向图。无向图:若图G中的每条边都是没有方向的,则称G为无
8、向图。完全图:有1/2条边的图无向图称为完全图。恰有n(n-1)条边的有向图称为有向完全图,恰有n(n-1)/2条边的无向图称无向完全图。连通图:图中G中任意两个顶点Vi、VjV、Vi和Vj连通的,则G称为连通图。度:顶点V的度是和V相关联的边的数目。强连通图:在有向图G中,如果对于每一对Vi,VjV、Vi、Vj,从Vi到Vj和从Vj到Vi都存在路径,则G是强连通图。无向图的路径:在无向图G中,若存在一个顶点序列vp,vi1,vi2,,vim,vq,使得(vp,vi1),(vi1,vi2),(vim,vq)均属于E(G),则称顶点vp到vq存在一条路径。有向图的路径:在有向图G中,路径也是有向
9、的,它由E(G)中的有向边,组成。路径长度:路径长度定义为该路径上边的数目。子图:设G=(V,E)是一个图,若V是V的子集,E是E的子集,且E中的边所关联的顶点均在V中,则G=(V,E)也是一个图,并称其为G的子图。生成树:如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树。最小生成树:权最小的生成树称为G的最小生成树。图中(b)、(c)、(d)都是生成树,权分别是:21、13、9。可以证明(d)为一棵最小生成树。 (a)带权图 (b)生成树 (c)生成树 (d)最小生成树三、实验要求1、认真阅读和掌握本实验的内容。2、从实验本上选择一个程序上机调试。3、得出正确的程序后
10、,运行程序输入一个图形,保存和打印出程序运行的结果,并进行程序的性能分析。4、请重新编写一个程序并上机进行调试,得出结果后总结出程序的特点。最小生成树:prim#include#include#include#define MAX 100typedef struct dege int vex1; int vex2; int weight;Edge;typedef struct linknode int vex; int weight; struct linknode * next;LINKNODE;typedef struct node int data; struct linknode *
11、first;NODE;typedef struct cd int adjvex; int lowcost;CD;NODE GMAX;Edge EMAX;CD closedgeMAX;int GRAPHMAXMAX;int visitedMAX;int graphcount;void printgraph();void convert();void prim(int u);int main() int i; int tempcount,temp; LINKNODE *p; freopen(in.txt,r,stdin); /freopen(out.txt,w,stdout); scanf(%d,
12、&tempcount); while(tempcount!=0) graphcount=tempcount; for(i=0;igraphcount;i+) Gi.data=i; Gi.first=NULL; for(i=0;ivex=temp; scanf(%d,&temp); p-weight=temp; p-next=Gi.first; Gi.first=p; scanf(%d,&temp); scanf(%d,&tempcount); printgraph(); convert(); prim(0); return 0;void printgraph() int i; LINKNODE
13、 *p; for(i=0;igraphcount;i+) printf(data=%d ,Gi.data); p=Gi.first; while(p!=NULL) printf( ,p-vex,p-weight); p=p-next; printf(n); void prim(int u) int i,j,min,p; for(j=0;jgraphcount;j+) if(j!=u) closedgej.adjvex=u; closedgej.lowcost=GRAPHju; closedgeu.lowcost=0; for(i=0;igraphcount-1;i+) p=1; min=MAX
14、; for(j=0;jgraphcount;j+) if(closedgej.lowcost!=0 & closedgej.lowcost min) min=closedgej.lowcost; p=j; printf(-%dn,closedgep.adjvex,p,min); closedgep.lowcost=0; for(j=0;jgraphcount;j+) if(GRAPHpj closedgej.lowcost) closedgej.lowcost=GRAPHpj; closedgej.adjvex=p; void convert() int i,j; LINKNODE *p; f
15、or(i=0;igraphcount;i+) for(j=0;jgraphcount;j+) GRAPHij=MAX; for(i=0;ivex=p-weight; p=p-next; for(i=0;igraphcount;i+) for(j=0;jgraphcount;j+) printf(%dt,GRAPHij); printf(n); 最小生成树:kruskal;#include#include#include#define MAX 100typedef struct edge int u; int v; int weight;Edge;Edge EMAX;int Ecount;voi
16、d kruskal();int main() int i; freopen(in.txt,r,stdin); freopen(out.txt,w,stdout); scanf(%d,&Ecount); for(i=0;iEcount;i+) scanf(%d,&Ei.u); scanf(%d,&Ei.v); scanf(%d,&Ei.weight); kruskal(); return 0;void kruskal() int vsetMAX; int i,j,k,tempu,tempv,s1,s2; for(i=0;iEcount;i+) vseti=i; k=1; j=0; while(k
17、Ecount & jEcount) tempu=Ej.u; tempv=Ej.v; s1=vsettempu; s2=vsettempv; if(s1!=s2) printf(u=%d,v=%d,weight=%dn,tempu,tempv,Ej.weight); k+; for(i=0;idata=x; s-left=NULL; s-right=NULL; insert(b,s); while (x!=1);在二叉排序树b中查找x的过程为:(1)若b是空树,则搜索失败,否则(2)(2)若x等于b的根结点的数据域之值,则查找成功;否则(3)(3)若x小于b的根结点的数据域之值,则搜索左子树;否则(4)(4)查找右子树。 实验源程序算法如下:btree *search(btree*b;ElemTypr x) if(b=NULL) return(NULL); else if(b-data=x) return(b);if(xdata) return(search(b-left));else return(search(b-right);四、实验要求1、根据以上给出算法写出二叉排序树的生成程序。2、根据以上给出算法写出二叉排序树的查找程序。3、写出调试运行的分析和体会。4、写出输出结果和实验报告。五、强化与提高思考题:编写一个从有m个结点其数据域值为rI的二叉树中删除结点x的算法。
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2