实验3--图的基本操作(共6页).docx
精选优质文档-倾情为你奉上实验3 图的基本操作实验目的1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2. 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。3. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普里姆算法。实验内容1. 输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2. 输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3. 深度优先遍历第一步中构造的图G，输出得到的节点序列函数说明1. typedef struct arc int adjvex; struct arc *next;ArcNode;typedef struct VexNodeint vertex; ArcNode *firstarc;VerNode;typedef VerNode AdjListMAXNODE; /邻接表的结点类型 */2. void CreatAdjlist(AdjList GL) /* 建立图的邻接表 */3. void DfsAdjlist(AdjList GL,int v) /* 从初始点v出发深度优先遍历邻接表GL表示的图 */4. void BfsAdjlist(AdjList GL,int v) /*从初始点v出发广度优先遍历邻接表GL表示的图*/实验过程实验代码#include <iostream>#include <string>#include <queue>using namespace std;typedef struct edgenodeint adjvex;edgenode *next;edgenode;/定义表结点typedef struct vexnodestring data;edgenode* link;vexnode, AdjList100;/定义头结点typedef structAdjList vertices;int vexnum, arcnum;ALGraph;/定义图int LocateVex(ALGraph G, string u)for(int i=0; i<G.vexnum; i+)if(G.verticesi.data=u)return i;return -1;/定位void Create(ALGraph &G)string v1, v2;int i, j, k; cout<<” 开始建图 “<<cout<<"请输入结点个数，边数："cin>>G.vexnum>>G.arcnum; cout<<"请输入点："for(i=0; i<G.vexnum; i+)cin>>G.verticesi.data;G.verticesi.link=NULL;cout<<"输入边（V1，V2）："cout<<endl;for(k=0; k<G.arcnum; k+)cin>>v1>>v2;i=LocateVex(G, v1);j=LocateVex(G, v2);edgenode *p=new edgenode;p->adjvex=j;p->next=G.verticesi.link;G.verticesi.link=p; p=new edgenode;p->adjvex=i;p->next=G.verticesj.link;G.verticesj.link=p;/创建图int FirstAdjVex(ALGraph G, int v)edgenode *p=G.verticesv.link;if(p)return p->adjvex;elsereturn -1;/头与否，是的话返回nextint NextAdjVex(ALGraph G, int v, int w)edgenode* p=G.verticesv.link;while(p) if(p->adjvex=w)break;p=p->next;if(p->adjvex!=w | !p->next)return -1;return p->next->adjvex;/下一个结点bool visited10;/数组，保存是否访问过void DFS(ALGraph G, int v)visitedv=true;cout<<G.verticesv.data<<" "for(int w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w) )if(!visitedw)DFS(G, w);/深度void DFSS(ALGraph G)for(int i=0; i<G.vexnum; i+)visitedi=false;for(i=0; i<G.vexnum; i+)if(!visitedi)DFS(G, i);/深度优先准备与调用void BFS(ALGraph G)queue<int> q;for(int i=0; i<G.vexnum; i+)visitedi=false;for(i=0; i<G.vexnum; i+)if(!visitedi)q.push(i);visitedi=true;while(!q.empty()int v=q.front();q.pop();cout<<G.verticesv.data<<" "for(int w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w)if (!visitedw)q.push(w);visitedw=true;/广度void main()ALGraph G;Create(G);cout<<"深度优先遍历结果："<<endl;DFSS(G);cout<<endl;cout<<"广度优先遍历结果："<<endl;BFS(G);cout<<endl;/主函数代码调试1.此时的edgenode前漏掉了new,所以表达非法；2.此处应改为edgenode* p=G.verticesv.link;3. 将所有错误修改后运行出以下结果，发现没有广度优先遍历的结果仔细检查广度优先遍历的函数之后发现此处循环的结束条件出错，应改为while(!q.empty()实验结果专心-专注-专业
