图的建立及应用.doc

实验4 图的遍历及应用一、 实验目的1) 掌握图的邻接矩阵存储；2) 利用邻接矩阵存储图；3) 掌握图的邻接表存储；4) 利用邻接表存储图并实现图的遍历；二、 实验内容已知图1，分别用邻接矩阵，邻接表表示两种表示法创建g1,g2.DA3 0 1 0 1 Edges= 1 0 1 1 BC 0 1 0 0 1 0 0 1图1无向图无向图对应的邻接表表示如下图所示： 序号 0A 1 3 B1 0 2 3 112C D 3 0 1 一个无向图的邻接表表示1、利用邻接矩阵存储图1。要求：数据元素类型ElemType 取char。实现如下算法：1）利用邻接矩阵存储一个图；2、利用邻接表存储图1并实现图的遍历。要求：数据元素类型ElemType 取char。实现如下算法：1）利用邻接表存储一个图；2）输出邻接表；编程代码如下:#include #includeusing namespace std;#define MAXV 30typedef char ElemType ;typedef struct int no; ElemType data; VertexType;typedef struct int edgesMAXVMAXV; int vexnum,arcnum; VertexType vexsMAXV; MGraph;void CreateMGraph(MGraph *G) int i;printf(利用邻接矩阵创建图n输入顶点数:);scanf(%d,&G-vexnum);printf(请输入顶点：n); for(i=0;ivexnum;i+) scanf(%cn,&G-vexsi.data); printf(输入边数:);fflush(stdin); scanf(%d,&G-arcnum); for(i=0;ivexnum;i+) for(int j=0;jvexnum;j+) G-edgesij=0; for(int k=0;karcnum;k+) int i,j; printf(输入边（vi,vj）上的下标i,下标jn); scanf(%d,%d,&i,&j); G-edgesji=G-edgesij=1; void printfMG(MGraph *G)printf(输出邻接矩阵n);for(int i=0;ivexnum;i+)for(int j=0;jvexnum;j+)if(i=j)printf( 0 );elseprintf( %d ,G-edgesij);printf(n);typedef struct ANode int adjvex; struct ANode *nextarc; ArcNode; typedef struct Vnode ElemType data; ArcNode *firstarc; VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist; int vexnum,arcnum; ALGraph; void CreateALGraph(ALGraph *G) printf(利用邻接表创建图n输入顶点数:); scanf(%d,&G- vexnum); printf(输入边数:); scanf(%d,&G-arcnum); printf(输入顶点：n); for(int i=0;ivexnum;i+) cin G-adjlisti.data; G-adjlisti.firstarc=NULL; fflush(stdin); for(int k=0;karcnum;k+) int i,j; printf(输入边（vi,vj）上的顶点序号：n); scanf(%d,%d,&i,&j); ArcNode *e; e=new ArcNode; e-adjvex=j; e-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=e; e=new ArcNode; e-adjvex=i; e-nextarc=G-adjlistj.firstarc; G-adjlistj.firstarc=e; void printfALG(ALGraph *G) ArcNode *p; int i; printf(输出邻接表n); for (i=0;ivexnum;i+) printf(%c,G-adjlisti.data); p=G-adjlisti.firstarc; while (p) printf(-%d,p-adjvex); p=p-nextarc; printf(-n); int main() MGraph G; CreateMGraph(&G);