实验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)

if(M.arcs[v][m].adj)

return m;

return -1;

/* 查找下一个邻接点 */

int NextAdjVex(MGraph &M,int v,int w) {

int j;

for(j=w+1;j<M.vexnum;j++) if (M.arcs[v][j].adj)

return j;

return -1; } void DFS(MGraph &M,int v) { }

void visits(MGraph &M,int &v) { }

void DFSTraverse(MGraph &M,int v) { //对图M作深度优先遍历。

int w;

printf("%c ",M.vexs[v]); visited[v]=1;

for(w=FirstAdjVex(M,v);w>=0;w=NextAdjVex(M,v,w)) // 访问第W个顶点

if(!visited[w])//对v的尚未访问的邻接点w递归调用DFS

DFS(M,w);

v=-1;

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

if(!visited[i])

v=i;

int i;

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

}

visited[i]=0;// 访问标志数组初始化

while(v>=0 && v<M.vexnum)// 对尚未访问的顶点调用DFS { }

DFS(M,v); visits(M,v);

void BFSTraverse(MGraph &M,int v)// {

按广度优先非递归遍历图M

int queue[MAX_VERTEX_NUM],front=0,rear=0; int i,w,u;

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

visited[i]=0;

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

if(!visited[i]) {

visited[i]=1;

printf("%4c",M.vexs[v]); queue[rear]=i;

rear=(rear+1)%MAX_VERTEX_NUM; while(front!=rear) {

u=queue[front]; cout<<M.vexs[u]<<' '; visited[u]=1;

front=(front+1)%MAX_VERTEX_NUM;

// //

for(w=FirstAdjVex(M,u);w>=0;w=NextAdjVex(M,u,w)) {

if(!visited[w]) {

}

}

}

}

visited[w]=1;

printf("%2c",M.vexs[w]); queue[rear]=w;

rear=(rear+1)%MAX_VERTEX_NUM;

// }

cout<<endl;

void main() {

MGraph M,N; ALGraph G;

printf("建立有向图的邻接矩阵：\n"); CreateGraph(M); PrintGraph(M);

printf("\n由有向图M的邻接矩阵产生邻接表:\n ");

CreateMGtoDN(G,M);

PrintDN(G);

printf("\n由邻接表产生对应的邻接矩阵:\n");

CreateDNtoMG(N,G);

PrintGraph(N);

printf("深度优先搜索的结果:\n"); DFSTraverse(M,0); cout<<endl;

printf("广度优先搜索的结果:\n"); BFSTraverse(M,0); printf("\n");

结果截图

四，实验小结

1、邻接矩阵是表示顶点之间相互关系的矩阵，用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有关联。

2、图的遍历是按照某种搜索方法沿着图的边访问图的所有顶点，使每个顶点仅被访问一次。对于无向图，深度优先搜索和广度优先搜索需要队列进行访问。

3、深度优先搜索遍历和广度优先搜索用邻接矩阵表示图时，时间复杂度均为O（n^2）.