树、图及其应用——图遍历的演示
实验五/第二组
数据结构
课 程 实 验 报 告
姓名：陈东 学号：070612146
安 庆 师 范 学 院 2012 计 算 机 卓 越 班
1/7
树、图及其应用——图遍历的演示
实验五/第二组
目
录
一、【实验目的】.......................................................................................................3 二、【问题描述】.......................................................................................................3 三、【基本要求】.......................................................................................................3 四、【实验环境】.......................................................................................................3 五、【测试数据及其结果】.......................................................................................4 六、【实验源代码】...................................................................................................5
安 庆 师 范 学 院 2012 计 算 机 卓 越 班
实验五/第二组
7/7
Windows XP, VC++6.0
安 庆 师 范 学 院 2012 计 算 机 卓 越 班
3/7
树、图及其应用——图遍历的演示
五、【测试数据及其结果】
实验五/第二组
安 庆 师 范 学 院 2012 计 算 机 卓 越 班
4/7
树、图及其应用——图遍历的演示
实验五/第二组
六、【实验源代码】
#include<iostream.h> #include<stdio.h> #define MAX_VRTEX_NUM 20 struct edgenode{
二、【问题描述】
很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个 程序，演示在连通图的无向图上访问全部结点的操作。
三、【基本要求】
以邻接多重表为储存结构，实现连通无向图的深度优先和广度优先 遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列 和相应生成树的边集。
四、【实验环境】
dfsAdjoin(GL,visited,j,n); p=p->next; } } void bfsAdjoin(adjlist GL,bool*& visited,int i,int n) //从初始点出发广度优先搜索邻接表 GL 表示的图 { const int MaxLength=30; int q[MaxLength]={0}; int t=0,rear=0;
安 庆 师 范 学 院 2012 计 算 机 卓 越 班
2/7
树、图及其应用——图遍历的演示
实验五/第二组
一、【实验目的】
本次实习主要突出了数据结构加操作的程序设计观点，但根据这两 种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作 是其它众多操作的基础。本实习单元还希望达到熟悉各种储存结构的特 性，以及如何应用树和图结构解决具体问题等目的。
cout<<"|-|->|"<<p->adjvex-1; cout<<"|^|";
cout<<endl; } //输出邻接表 } void dfsAdjoin(adjlist GL,bool*& visited,int i,int n) //从初始点出发深度优先搜索邻接表 GL 表示的图 { cout<<i<<' '; visited[i]=true; edgenode* p=GL[i]; while(p!=NULL){ int j=p->adjvex; if(!visited[j])
int adjvex; edgenode * next; }; //定义邻接表的边结点类型 typedef edgenode **adjlist; //定义邻接表类型
void InitGAdjoin(adjlist&GL,int n) //初始化图的邻接表 {
GL=new edgenode*[n]; for(int i=1;i<=n;i++)GL[i]=NULL; } void CreateAdjoin(adjlist &GL,int n)
cout<<j<<' '; visited[j]=true; rear=(rear+1)%MaxLength; q[rear]=j; } p=p->next; } } }
int main() {
int i,n,m; cout<<"=============="<<endl; cout<<"输入图的顶点数:"; cin>>n; bool*visited=new bool[n]; adjlist gl; InitGAdjoin(gl,n); CreateAdjoin(gl,n); cout<<"=============="<<endl; cout<<"请输入起点:"<<endl; cin>>m; cout<<"图的深度优先遍历序列:"<<endl; for(i=1;i<=n;i++) visited[i]=false; dfsAdjoin(gl,visited,m,n); cout<<endl<<"=============="<<endl; cout<<"图的广度优先遍历序列:"<<endl; for(i=1;i<=n;i++) visited[i]=false; bfsAdjoin(gl,visited,m,n); cout<<endl; return 0; }
安 庆 师 范 学 院 2012 计 算 机 卓 越 班
5/7
树、图及其应用——图遍历的演示
//建立图的邻接表 {
int i,j,k,e; cout<<"输入图的总边数："; cin>>e; //建立无向图 for(k=0;k<e;k++){
cout<<"输入第"<<k+1<<"条边的起点和终点序号！"<<endl; cin>>i>>j; edgenode*p=new edgenode; p->adjvex=j; p->next=GL[i]; GL[i]=p; p=new edgenode; p->adjvex=i; p->next=GL[j]; GL[j]=p; } cout<<endl<<"=============="<<endl; cout<<"图的邻接表为:"<<endl; for(i=1;i<=n;i++){ edgenode*p=GL[i]; cout<<i-1<<" |"<<"V"<<i; for(p=GL[i];p!=NULL;p=p->next)
安 庆 师 范 学 院 2012 计 算 机 卓 越 班
实验五/第二组
6/7
树、图及其应用——图遍历的演示
cout<<i<<' '; visited[i]=true; q[++rear]=i; while(front!=rear){
front=(front+1)%MaxLength; int k=q[front]; edgenode* p=GL[k]; while(p!=NULL){ int j=p->adjvex; if(!visited[j]){