实验五图的基本操作.docx
- 文档编号:9880265
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:14
- 大小:164.71KB
实验五图的基本操作.docx
《实验五图的基本操作.docx》由会员分享,可在线阅读,更多相关《实验五图的基本操作.docx(14页珍藏版)》请在冰点文库上搜索。
实验五图的基本操作
实验五图的基本操作
一实验内容
[问题描述]
对给定图,实现图的深度优先遍历和广度优先遍历。
[基本要求]
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。
二、概要设计
算法设计:
要实现上述要求,需要创建一个无向图,在创建图的时候先定义图的邻接表存储表示,另外注意是以用户指定的结点为起点,所以要定义一个LocateVex(ALGraphG,intv)用于查找该点所在位置;在逐边输入的时候,要注意,将两个顶点都要插入图中。
无向图的深度优先遍历,假设初始状态所有顶点都没有被访问,使标志数组visited[]的值为0,一旦被访问,则为1,在深度优先遍历的时候还要判断是否存在邻接点,若存在且没有被访问,则递归调用dfs函数。
在广度优先遍历时,先定义队列的一些相关函数,用于广度优先遍历,先将所有的顶点都设为未被访问,然后将用户指定的结点进队、出队,找该点的位置和未被访问的邻接点,然后输出。
流程图:
模块:
在分析了题目要求后,先将程序分为五个功能函数,分别如下:
首先建立无向图的邻接表存储表示:
typedefstructArcNode
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
//int*info;//该弧相关信息的指针
}ArcNode;
typedefstructVNode
{
chardata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[max];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
//intkind;//图的种类标志
}ALGraph;
LocateVex(ALGraphG,intv):
如果所指定的顶点v存在则返回该结点的存储位置:
for(i=0;v!
=G.vertices[i].data&&i if(i>=G.vexnum)return-1; returni; CreatGraph(ALGraph&G): 在这个函数里,最重要的是逐边输入: for(k=0;k { cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=newArcNode; q=newArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc;//链入第m号链表的前端 G.vertices[i].firstarc=p; q->adjvex=i; q->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=q; } FirstAdjVex(ALGraphG,intv): 找到与v相关的第一个邻接点。 NextAdjVex(ALGraphG,intv,intw): 返回v中相对于w的下一个邻接顶点。 DFS(ALGraphG,intv): 设一个标志数组用来区分是否被遍历过,然后找用户指定的结点,和与该点的邻接点,循环结束条件是知道没有与该点相关的邻接点。 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(! visited[w])DFS(G,w);//对v的尚未访问的邻接顶点递归调用DFS BFSTraverse(ALGraphG): 也要定义访问标识数组,先将用户指定的结点初始化,在设为已访问,输出并进入队列,当队列不为空的时候再输出,,找与该点相关的邻接点,访问并输出。 for(v=0;v if(! visited[v]) {//v尚未访问 visited[v]=1; cout< EnQueue(Q,v);//v入队 while(! QueueEmpty(Q)) { DeQueue(Q,v);//队头元素出队并置为v for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(! visited[w]) {//w为u的尚未访问的邻接顶点 visited[w]=1;//visit(w); cout< EnQueue(Q,w); }//if }//while }//if 三、测试数据 测试一: 顶点为: ABCDE 边信息: ABACADCDBCBD 测试二: 顶点为: ABCDEFGHI 边信息: ABACADBEBCEGDFFHHI 四、结果调试 调试一: 调试二: 五.总结 在进行这个程序的编写时,遇到了种种的问题,首先定位函数不太会写,纠结半天,寻求同学的帮助才解决,还有就是在创建无向图的时候,没有考虑其无向的特征,才耗费了许久的时间。 另外就是在深度优先遍历时,找该点的邻接点函数不会写,之后仔细看了算法后,才明白是寻找依附于该点的第一条指针的顶点信息,再查看该点的下一个指针,并判断其顶点信息不为空,这才解决一大难题。 当然大问题是解决了,但是在进行广度优先遍历时,遇到了问题,就是广度优先遍历的前半部分是正确的,但后半部分是错误的或者有的是正确的,但是复杂的就是错误的,仔细检查了半天,才发现是元素出队列时与进队列的字母表示的不一样,才会造成这样的结果。 这也警告我们在编写程序时,要格外的小心,一个小疏忽就会让程序无法运行或者是运行错误! 六、附录: #include #definemax100 intvisited[max]; typedefstructArcNode { intadjvex;//该弧所指向的顶点的位置 structArcNode*nextarc;//指向下一条弧的指针 }ArcNode; typedefstructVNode { chardata;//顶点信息 ArcNode*firstarc;//指向第一条依附该顶点的弧的指针 }VNode,AdjList[max]; typedefstruct { AdjListvertices; intvexnum,arcnum;//图的当前顶点数和弧数 }ALGraph; typedefstructQNode {chardata; structQNode*next; }QNode,*QueuePtr; typedefstruct {QueuePtrfront; QueuePtrrear; }LinkQueue; intInitQueue(LinkQueue&Q) {Q.front=Q.rear=newQNode; if(! Q.front)return0; Q.front->next=NULL; return1; } intQueueEmpty(LinkQueue&Q) { if(Q.front==Q.rear)return1; else return0; } intEnQueue(LinkQueue&Q,chare) {QNode*p; p=newQNode; if(! p)return0; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return1; } charDeQueue(LinkQueue&Q,int&e) {QNode*p; if(Q.front==Q.rear)return0; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; delete(p); return1; } //////////////////////////////// intLocateVex(ALGraphG,intv) { inti; for(i=0;v! =G.vertices[i].data&&i if(i>=G.vexnum)return-1; returni; } voidCreatGraph(ALGraph&G) { intk,i,j;//m,n, ArcNode*p,*q; cout<<"请输入定点数: "; cin>>G.vexnum;//输入顶点数 cout<<"请输入边数: "; cin>>G.arcnum;//输入边数 charv1,v2; cout<<"输入顶点信息: "; for(i=0;i { cin>>G.vertices[i].data;//顶点信息 G.vertices[i].firstarc=NULL; } cout<<"请输入边的信息"< for(k=0;k { cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=newArcNode; q=newArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc;//链入第m号链表的前端 G.vertices[i].firstarc=p; q->adjvex=i; q->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=q; } } /////////////////////////////////////////// intFirstAdjVex(ALGraphG,intv) { if(! G.vertices[v].firstarc)return0; returnG.vertices[v].firstarc->adjvex; } intNextAdjVex(ALGraphG,intv,intw) {//返回v中相对于w的下一个邻接顶点 ArcNode*p; p=G.vertices[v].firstarc; while(p&&p->adjvex! =w)p=p->nextarc; if(! p->nextarc)return-1; elsereturnp->nextarc->adjvex; } voidDFS(ALGraphG,intv) { intw; visited[v]=1; cout< for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(! visited[w])DFS(G,w);//对v的尚未访问的邻接顶点递归调用DFS } ////////////////////////////////////// voidBFSTraverse(ALGraphG) { intv,w,u;LinkQueueQ; for(v=0;v visited[v]=0; InitQueue(Q);//置空的辅助队列Q for(v=0;v if(! visited[v]) {//v尚未访问 visited[v]=1; cout< EnQueue(Q,v);//v入队 while(! QueueEmpty(Q)) { DeQueue(Q,v);//队头元素出队并置为v for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(! visited[w]) {//w为u的尚未访问的邻接顶点 visited[w]=1;//visit(w); cout< EnQueue(Q,w); }//if }//while }//if } intmain() { ALGraphG; intv; CreatGraph(G); intn,i; charch; cout<<"请输入起始搜索点: "; cin>>ch; for(i=0;i n=LocateVex(G,ch); cout<<"深度优先遍历: "< DFS(G,n); cout< cout<<"广度优先遍历: "< BFSTraverse(G); return0;}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验五 图的基本操作 实验 基本 操作