数据结构实验六,七,八

1、实验六图的遍历一、实验目的1、熟悉图的各种存储结构及其构造算法2、熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索 的两种形式（递归和非递归）和广度优先搜索的算法。3、应用图的遍历算法求解各种简单路径问题。4、理解教科书中讨论的各种图的算法。二、实验预备知识本实验的重点：深度优先搜索和广度优先搜索。图的遍历：和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条 搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法 的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。 它们对无向图和有向图均适用。图的深度优先遍历：假设给定初始状态图G中的所有顶点均未曾访 问过。

2、在G中任选一顶点v出发，首先访问出发点v，并将其标记为已访 问过，然后依次从v出发搜索v的每个邻接点。若该邻结点未曾访问过， 则以该邻结点为新的出发点继续进行深度优先遍历，直至图中所有和点v 有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点，则 另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶 点均被访问为止。(b)图G深度优先过程深度优先遍历序列：v1v2v4v5v3v6v7图的广度优先遍历：设初始状态图G中的所有顶点均未访问过。在G 中任选一顶点v,首先访问出发点v,接着依次访问v的所有邻接点，然 后再依次访问与邻接的所有未曾访问过的顶点，并使“先被访问的顶点 的邻

3、接点”先于“后被访问的顶点的邻接点”被访问。依此类推，直至 图中所有和点v有路径相通的顶点都已访问到。若此时图中尚有顶点未 被访问，则另选图中的一个未被访问的顶点作起始点，重复上述过程， 直到图中所有顶点都被访问到为止。(d)图G厂度优先搜索过程广度悠闲遍历序列：v1v2v3v4v5v6v7v8v9三、实验要求1、掌握图的遍历思想以及其特点。2、选择程序上机进行调试找出问题、保存和打印出程序的运行结果。3、上机学会运用图的思想解决实际问题。4、课后尝试自己编写程序并上机运行得出结果。深度遍历图，邻接表加递归#include#include#include#define MAX 100typed

4、ef struct Linknodeint adjvex;/int infO;struct Linknode *next;LinkNode;typedef struct Vexnodeint 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()create();/print();DFS(2,

5、2,-1);void create()int i,tempi;LinkNode *p,*q;freopen(intxt,r,stdin);freopen(outtxt”,w,stdout);scanf(%d,&Gvexnum); scanf(%c,&temp);for(i=0;iGvexnum;i+)scanf(%d,&Gadjlisti.vexdata);Gadjlisti.first=NULL; scanf(%c”,&temp);for(i=0;iadjvex=tempi;q=G.adjlisti.first;G.adjlisti.first=p; p-next=q; scanf(%d,&

6、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=Gadjlistu.first;if(u=v )for(i=0;iadjvex;if(pretemp=0)DFS(temp,v,d);p=p-next;preu=0;d-;void print_path(int pre,int v)if(prev!=v)print_path(pre,prev);printf(%

7、d ,v);实验七最小生成树一、实验目的1、图的邻接矩阵、邻接表和边集数组表示。2、掌握建立图的邻接矩阵的算法，由邻接矩阵转换为邻接表和边集数组 的算法。3、熟悉最小生成树的构造。4、熟悉并掌握求图的最小生成树的普里姆算法克鲁斯卡尔算法。二、实验预备知识掌握图的概念、图的邻接矩阵表示法和邻接表表示法、图的深度和 广度优先遍历、生成树和最小生成树、树的最短路径、拓扑排序。有向图：若图G中的每条边都是有方向的，则称G为有向图。无向图：若图G中的每条边都是没有方向的，则称G为无向图。完全图：有1/2条边的图无向图称为完全图。恰有n(n-1)条边的有向图称 为有向完全图，恰有n(n-1)/2条边的无向

8、图称无向完全图。连通图：图中G中任意两个顶点V、VV、V、和Vj连通的，则G称为连通图v2v2v4v4v5v5v3v3连通图。度：顶点V的度是和V相关联的边的数目。v1强连通图：在有向图G中，如果对于每一对vVM、V、的，从Vi到 Vj和从的到V、都存在路径，则 G 是强连通图。V1 TOC o 1-5 h z 无向图的路径：在无向图G中，若存在一个顶点序列v ,v，v ,.，v， p 1112imv，使得（v，v ），（v，v ），.，（v.，v ）均属于E（G），则称顶点v到 qp 111112im qpvq存在一条路径。有向图的路径:在有向图G中，路径也是有向的，它由E（G）中的有向边v

9、p，v ，v，v ， .，v，v组成。1111121m q路径长度：路径长度定义为该路径上边的数目。子图：设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)带权图三、实验要求(d )最小生成树1、认真阅读和掌握本实验的内容。2、从实验本上选择一个程序上机调试。3、得出正确的程序

10、后，运行程序输入一个图形，保存和打印出程序运行 的结果，并进行程序的性能分析。4、请重新编写一个程序并上机进行调试，得出结果后总结出程序的特点。最小生成树：prim#include#include#include #define MAX 100 typedef struct degeint vexl;int vex2;int weight;Edge;typedef struct linknodeint vex;int weight;struct linknode * next;LINKNODE;typedef struct nodeint data;struct linknode * firs

11、t;NODE;typedef struct cdint 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(outtxt,w”,stdout);scanf(%d,&tempcount);w

12、hile(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 *p;for(i=0;igraphcount;i+)prin

13、tf(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;for(j=0;jgraphcount;j+)if(closedgej.lowcost!=0

14、 & 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;for(i=0;igraphcount;i+)for(j=0;jgraphcount;j+)GRAPHij=MAX;f

15、or(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;void kruskal();int main()int i;freopen(intxt”,r”,stdin);freopen(out.tx

16、t,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 ij,k,tempu,tempv,s1,s2;for(i=0;iEcount;i+) vseti=i;k=1;j=0;while(kEcount & jEcount)tempu=Ej.u;tempv=Ej.v;s1=vsettempu;s2=vsettempv;if(s1!=s2)printf(u=%d,v=%d,weight=%dnn,tempu,tempv,Ej.weight); k+;for(i=0;idata=x;s-left=NULL;s-right=NULL;insert(b,s);while (x!=1);在二叉排序树b中查找x的过程为：若b是空树，则搜索失败，否则2)若x等于b的根结点的数据域之值，则查找成功；否则3)若x小于b的根结点的数据域之值，则搜索左子树；否则4)查找右子树。实验源程序算法如下：btree *