实验3 图的建立与操作

1、实验3 图的建立与操作一、实验目的和要求在熟悉图的存储、遍历、及其应用的基础上，通过键盘输入数据，建立一个无向图的邻接表，输出该邻接表，并计算每个顶点的度。达到巩固图的存储思想及其存储实现。二、实验内容完成下图的邻接表表示，并计算每个顶点的度。附加要求：进行深度优先和广度优先遍历三、实验提示类型定义（邻接表存储） #define MAX_VERTEX_NUM 8 /顶点最大个数 typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int weight; /边的权ArcNode; /表结点 #define VertexType cha

2、r /顶点元素类型typedef struct VNodeint degree;/顶点的度，入度 VertexType data;ArcNode *firstarc;VNode/*头结点*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices;int vexnum,arcnum;/顶点的实际数，边的实际数ALGraph;2实验步骤1）输入图中顶点信息，完成邻接表的VNode内容的初始化。2）根据图中边的信息，把各边的信息链到firstarc指针链上，同时统计degree3）输出邻接表。3. 代码#include stdafx.h#inc

3、lude#include#define WeightMax 100#define UNDRIECT#define MAXDATA 100#define MAXVEX 10/#define WEIGHTTREE/using namespace std;/typedef char DataType;struct ENodeint tailvex,headvex; int weight;struct ENode *tailnext,*headnext;struct VerNodeDataType data;ENode *firstin; ENode *firstout;/typedef VerNod

4、e AdjListMAXVEX;struct MGraphsVerNode adjListMAXVEX;/ENode *edgeListMAXVEXMAXVEX;int numNode,numEdge; ; / /int LocateVex(MGraphs G,DataType data)int i=0; for( i=0;iG.numNode;+i) if(G.adjListi.data=data) return i; return -1;/the build graph/one construct/void CreatALGraph(MGraphs &G) int weight; int

5、i,j; DataType vi,vj; ENode *e; coutplease input the numNode and numEdgeG.numNodeG.numEdge; coutplese input the node informationendl; for(i=0;iG.adjListi.data; G.adjListi.firstin=NULL; G.adjListi.firstout=NULL; for(int k=0;kG.numEdge;k+) coutplease input the the node of edge vi,vj,weight if it has we

6、ight;vivj;#ifdef WEIGHTREE cinweight;#endif i=LocateVex(G,vi); j=LocateVex(G,vj); e=new ENode; e-tailvex=j; e-headvex=i; e-headnext=G.adjListj.firstin; e-tailnext=G.adjListi.firstout;#ifdef WEIGHTREE e-weight=weight; #else e-weight=100; #endif G.adjListj.firstin=G.adjListi.firstout=e; /G.edgeListij=e; void FindInDegree(MGraphs G,int *a)int i=0;int DegCou=0;for( i=0;iMAXDATA;i+)ai=0; for( i=0;iheadnext; e=G.adjListi.firstout; while(!(e=NULL) DegCou+; e=e-tailnext; ai=ai+DegCou; / int _tmain(int argc, _TCHAR* argv) MGraphs g; CreatALGraph(g); int degree