实验3--图的基本操作

实验3图的基本操作实验的目的1 .必须掌握图的各种存储结构，特别是熟悉邻接矩阵和邻接表的存储结构。2 .扫描是图的各种应用算法的基础，必须掌握图的深度优先扫描和宽度优先扫描算法，复习堆栈和队列的应用。3 .一种把握把邻接矩阵作为存储结构的生成图的最小生成树的算法。实验内容1 .输入顶点数、边数、每个顶点的值和每个边的信息，构筑无向图表g，用邻接矩阵存储图表。2 .输入顶点的数量、边的数量、每个顶点的值、每个边的信息，构筑无向图表g，用邻接表存储该图表3 .深度优先扫描在第一步骤中构建的地图g并输出获得的节点序列函数说明1 .类型结构arcint adjvex；struct arc *next； ArcNode；typedef struct VexNodeint vertex；ArcNode *firstarc；VerNode；typedef ver node adj list 最大节点； /邻接表的节点类型*/2 .创建2.voidacreatadjlist(adjlistgl)/*图的相邻表*/3.voidfstability(adjlistgl，int v) /*从初始点v开始以深度优先显示在邻接表GL中的图*/4. void BfsAdjlist(AdjList GL，int v) /*从第一个点v开始，优先横穿相邻表GL的显示的图*/实验过程实验代码#include#include#includeusing namespace std；typedef struct edgenodePK PS；edgenode *next；edgenode； /定义表节点typedef struct vexnode字符串数据；edgenode* link；vexnode，AdjList100；/定义头部节点typedef structAdjList vertices；int vexnum，arcnum；ALGraph；/定义图int LocateVex(ALGraph G，string u )举止for(int i=0； iG.vexnumG.arcnum；请输入“计数”点： ；for(i=0； iG.verticesi.data；G.verticesi.link=NULL；以下输入边(V1，V2 ):；coutv1v2；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=新边缘节点；p-adjvex=i；p-next=G.verticesj.link；G.verticesj.link=p；以下以下/制作图第一次调整(algraph g，int v )举止edgenode *p=G.verticesv.link；PR K返回p-adjvex；else返回- 1；以下/是否头脑，如果是，返回nextint NextAdjVex(ALGraph G，int v，int w )举止edgenode* p=G.verticesv.link；while(p )举止if(p-adjvex=w )break；p=p-next；以下PS (PS adjvex！=w |！ p-next )返回- 1；返回p -下一个调整；/下一个节点bool visited10； /数组，保存是否访问过PS PS (PS，PK )举止visitedv=true；cout=0； w=下一个调整(g，v，w ) )PS (！ visitedw )DFS(G，w )/深度voidfstabs(algraphs )举止for(int i=0； PS；for(int i=0； i=0； w=下一个调整(g，v，w ) )举止PS (！ visited