图的遍历实验报告.doc

图的遍历班级：计算机09级网络工程2班 姓名：+ 学号：0925113018完成日期：2010.12.30题目：编制一个创建有向图和无向图然后对它们进行遍历的程序。一、需求分析1、用邻接矩阵和邻接表的形式表示图，创建图。（设计中其中用邻接表表示的图内没有权重，用邻接矩阵表示的图内有权重。）2、输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。（设计中其中用邻接表表示的节点的值只能是数字，但用邻接矩阵表示的节点的值可以是字母。）3、 本程序只求出用邻接矩阵表示的无向图的深度遍历，和用邻接表表示的无向图的深度和广度遍历4、程序执行命令为：（1）输入图；（2）输出图；（3）输出遍历。二、概要设计/邻接矩阵typedef struct ArcCell int adj; ArcCell *info;ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum;MGraph;/邻接表typedef struct ArcNode /定义边结点 int adjvex; ArcNode *nextarc;ArcNode;typedef struct VNode /定义顶点结点 char data; ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct /定义无向图 AdjList vertices; int vexnum,arcnum;ALGraph;typedef struct node /定义结点 char data; node *next;*Link;typedef struct /定义链表 Link head,tail; int len;LinkList;/关于邻接表图的操作int InitList(LinkList &L)/构造一个带头结点和尾结点的空的线性链表Lvoid add(LinkList &L,int e)/在线性链表L的结尾添加一个结点void Delete(LinkList &L,int &e)/出列，并将出列的元素值用e返回void ArcAdd(ALGraph &G,int m,int n)/在无向图中添加以m,n为顶点的边void CreateDG(ALGraph &G) /创建无向图void show(ALGraph G) /在屏幕上输入无向图的邻接表存储形式void VisitFunc(char a) /对无向图的数据进行访问的函数int FirstAdjVex(ALGraph G,int v)/返回v的第一个邻接顶点。若顶点在G中没有邻接表顶点，则返回“空”。int NextAdjVex(ALGraph G,int v,int w) /返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“回”。bool visitMAX_VERTEX_NUM;void DFS(ALGraph G,int v)/从第v个顶点出发递归地深度优先遍历图G。void DFSTraverse(ALGraph G)/对图G作深度优先遍历。void BFSTraverse(ALGraph G)/对图G作广度优先遍历。/关于邻接矩阵的操作int LocateVex(MGraph G,char v)int FirstAdjVex(MGraph G,int v)int NextAdjVex(MGraph G,int v,int w)void CreatUDG(MGraph &G)/邻接矩阵的无向图的创建void CreatDG(MGraph &G)/有向图邻接矩阵的创建bool visitedMAX_VERTEX_NUM;void DFS(MGraph G,int v)void DFSTraverse(MGraph G,int v)void print1(MGraph G)三、详细设计/邻接表的创建void CreateDG(ALGraph &G) /创建无向图 cout请输入顶点个数和边数：G.vexnumG.arcnum; cout请输入顶点值:endl; for(int i=1;it; G.verticesi.data=t; G.verticesi.firstarc=NULL; int m,n; for(int k=1;k=G.arcnum;k+) cout请输入第k条边的两个顶点:mn; if(m=G.vexnum&n0&n0) ArcAdd(G,m,n); ArcAdd(G,n,m); else coutERROR.endl; /在屏幕上输入无向图的邻接表存储形式void show(ALGraph G) cout无向图的创建完成,该图的邻接表表示为:endl; ArcNode *p; for(int i=1;i=G.vexnum;i+) if(G.verticesi.firstarc=NULL) coutiG.verticesi.dataNULLendl; else p=G.verticesi.firstarc; coutiG.verticesi.data; while(p-nextarc!=NULL) coutadjvex; p=p-nextarc; coutadjvexNULLendl; void DFSTraverse(ALGraph G)/对图G作深度优先遍历。 cout深度优先搜索的结果为:endl; for(int v=1;v=G.vexnum;v+) visitv=false; for(int m=1;m=G.vexnum;m+) if(!visitm) DFS(G,m); coutendl;void BFSTraverse(ALGraph G)/对图G作广度优先遍历。 cout广度优先搜索的结果为:endl; LinkList Q; int u; for(int m=1;m=G.vexnum;m+) visitm=false; InitList(Q);/借助辅助队列。 for(int v=1;v=1;w=NextAdjVex(G,u,w) if(!visitw) visitw=true; VisitFunc(G.verticesw.data); add(Q,w); coutendl;void CreatUDG(MGraph &G)/邻接矩阵的无向图的创建int i,j,k,w;char v1,v2;cout请输入顶点个数和边数:G.vexnumG.arcnum; cout请输入G.vexnum个顶点的值:endl; for(i=0;iG.vexsi; for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) G.arcsij.adj=0; G.=NULL; for( k=1;k=G.arcnum;+k) cout请输入第k条边的两个顶点值和它们的权重：v1v2w; i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij.adj=w; G.arcsji=G.arcsij; void DFSTraverse(MGraph G,int v)/对邻接矩阵图的递归深度遍历visitedv=true;coutG.vexsv=0;w=NextAdjVex(G,v,w)/=if(!visitedw) DFSTraverse(G,w);四、调试分析在写邻接矩阵的NextAdjVex功能的时候，i从w开始，但是遍历到一半就停止了，后来发现第W个已经遍历过了，所以一直在循环遍历第W个，所以改成w+1。在写邻接矩阵无向图的深度优先遍历时，for(i