实验3--图的基本操作

1、实验3 图的基本操作实验目的1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2. 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。3. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普里姆算法。实验内容1. 输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2. 输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3. 深度优先遍历第一步中构造的图G，输出得到的节点序列函数说明1. typedef struct arc int adjvex; st

2、ruct 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表示的图*

3、/实验过程实验代码#include #include #include 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

4、=0; iG.vexnum; i+)if(G.verticesi.data=u)return i;return -1;/定位void Create(ALGraph &G)string v1, v2;int i, j, k; cout” 开始建图 “;coutG.vexnumG.arcnum; cout请输入点：;for(i=0; iG.verticesi.data;G.verticesi.link=NULL;cout输入边（V1，V2）：;coutendl;for(k=0; kv1v2;i=LocateVex(G, v1);j=LocateVex(G, v2);edgenode *p=new

5、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

6、.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;coutG.verticesv.data=0; w=NextAdjVex(G, v, w) )if(!visitedw)DFS(G, w);/深度void DFSS(ALGraph G)for(int i=0; iG.vexnum; i

7、+)visitedi=false;for(i=0; iG.vexnum; i+)if(!visitedi)DFS(G, i);/深度优先准备与调用void BFS(ALGraph G)queue q;for(int i=0; iG.vexnum; i+)visitedi=false;for(i=0; iG.vexnum; i+)if(!visitedi)q.push(i);visitedi=true;while(!q.empty()int v=q.front();q.pop();coutG.verticesv.data=0; w=NextAdjVex(G, v, w)if (!visitedw)q.push(w);visitedw=true;/广度void main()ALGraph G;Create(G);cout深度优先遍历结果：endl;DFSS(G);coutendl;cout广度优先遍历结果：endl;BFS(G);coutendl;/主函数代码调试1.此时的edgenode前漏掉了new,所以表达非法；2