数据结构-实验6图的存储和遍历

实验6.1实现图的存储和遍历

一， 实验目的

掌握图的邻接矩阵和邻接表存储以及图的邻接矩阵存储的递归遍历。

二， 实验内容

6.1实现图的邻接矩阵和邻接表存储

编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：

（1）建立如教材图7.9所示的有向图G的邻接矩阵，并输出。 （2）由有向图G的邻接矩阵产生邻接表，并输出。

（3）再由（2）的邻接表产生对应的邻接矩阵，并输出。 6.2 实现图的遍历算法

（4）在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。

（5）利用非递归算法重解任务（4）。

（6）在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。

三，源代码及结果截图

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream.h> #include<malloc.h>

#define MAX_VERTEX_NUM 20 typedef char VRType;

typedef int InfoType; // 存放网的权值 typedef char VertexType; // 字符串类型

typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网} /*建立有向图的邻接矩阵*/ typedef struct ArcCell {

VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻;对带权图

则为权值类型

InfoType *info; //该弧相关信息的指针(可无)

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {

VertexType vexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵

int vexnum,arcnum;;//图的当前顶点数和弧数 GraphKind kind;//图的种类标志

}MGraph;

/* 顶点在顶点向量中的定位*/ int LocateVex(MGraph &M,VRType v1){

int i;

for(i=0;i<M.vexnum;i++) }

void CreateGraph(MGraph &M)//建立有向图的邻接矩阵 {

int i,j,k,w; VRType v1,v2;

M.kind=DN;printf("构造有向网:\n");

printf("\n输入图的顶点数和边数(以空格作为间隔):"); scanf("%d%d",&M.vexnum,&M.arcnum); printf("输入%d个顶点的值(字符):",M.vexnum); getchar();

for(i=0;i<M.vexnum;i++) //输入顶点向量

if(v1==M.vexs[i])return i; return -1;

{

}

scanf("%c",&M.vexs[i]);

}

printf("建立邻接矩阵:\n"); for(i=0;i<M.vexnum;i++)

for(j=0;j<M.vexnum;j++) { }

printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n"); for(k=0;k<M.arcnum;++k)// 构造表结点链表 { }

cin>>w>>v1>>v2; i=LocateVex(M,v1); j=LocateVex(M,v2); M.arcs[i][j].adj=w; M.arcs[i][j].adj=0; M.arcs[i][j].info=NULL;

//按邻接矩阵方式输出有向图 void PrintGraph(MGraph M) {

int i,j;

printf("\n输出邻接矩阵:\n"); for(i=0; i<M.vexnum; i++) {

printf("%10c",M.vexs[i]);

for(j=0; j<M.vexnum; j++) printf("%2d",M.arcs[i][j].adj); printf("\n"); } }

// 图的邻接表存储表示 typedef struct ArcNode {

int adjvex;

// 该弧所指向的顶点的位置

struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info;

// 网的权值指针）

}ArcNode; // 表结点 typedef struct VNode {

VertexType data;

// 顶点信息

// 第一个表结点的地址,指向第一条依附该顶点的弧的

ArcNode *firstarc;

指针

}VNode,AdjList[MAX_VERTEX_NUM];// 头结点 typedef struct {

AdjList vertices;

int vexnum,arcnum; // 图的当前顶点数和弧数 int kind;

// 图的种类标志

}ALGraph;

void CreateMGtoDN(ALGraph &G,MGraph &M){

//由有向图M的邻接矩阵产生邻接表 int i,j; ArcNode *p; G.kind=M.kind;

G.vexnum=M.vexnum; G.arcnum=M.arcnum;

for(i=0;i<G.vexnum;++i){//构造表头向量 }

G.vertices[i].data=M.vexs[i];

G.vertices[i].firstarc=NULL;//初始化指针

}

for(i=0;i<G.vexnum;++i)

for(j=0;j<G.vexnum;++j)

if(M.arcs[i][j].adj){ }

p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;

p->nextarc=G.vertices[i].firstarc; p->info=M.arcs[i][j].info; G.vertices[i].firstarc=p;

void CreateDNtoMG(MGraph &M,ALGraph &G){

//由邻接表产生对应的邻接矩阵 int i,j; ArcNode *p;

M.kind=GraphKind(G.kind);

M.vexnum=G.vexnum; M.arcnum=G.arcnum; for(i=0;i<M.vexnum;++i)

M.vexs[i]=G.vertices[i].data;

for(i=0;i<M.vexnum;++i){

p=G.vertices[i].firstarc;

while(p){

M.arcs[i][p->adjvex].adj=1;

p=p->nextarc; }//while

for(j=0;j<M.vexnum;++j) }

if(M.arcs[i][j].adj!=1)

M.arcs[i][j].adj=0;

}//for

//输出邻接表

void PrintDN(ALGraph G){

int i; ArcNode *p;

printf("\n输出邻接表：\n"); printf("顶点:\n"); for(i=0;i<G.vexnum;++i)

printf("%2c",G.vertices[i].data);

printf("\n弧:\n"); for(i=0;i<G.vexnum;++i){

p=G.vertices[i].firstarc;

while(p){

}

printf("%c→%c(%d)\t",G.vertices[i].data,G.vertices[p->adjvex].data,p->info); p=p->nextarc;

printf("\n"); }

int visited[MAX_VERTEX_NUM]; void(*VisitFunc)(char* v);

// 访问标志数组(全局量)

}//for

// 函数变量(全局量)

// 从第v个顶点出发递归地深度优先遍历图G。 /* 查找第1个邻接点 */ int FirstAdjVex(MGraph &M,int v) { }

int m;

for(m=0;m<M.vexnum;++m)< …… 此处隐藏：3101字，全部文档内容请下载后查看。喜欢就下载吧 ……