实验报告:图的存储结构和遍历

admin管理员组

文章数量:1532656

2024年1月16日发(作者：)

.

武汉东湖学院

实 验 报 告

学院：

计算机科学学院 专业

计算机科学与技术

2016年

11月18日

姓 名

班 级

课程名称

实验名称

付磊

计科一班

学 号

指导老师

2

吴佳芬

数据结构

图的存储结构和遍历

成

绩

1．实验目的

（1）了解邻接矩阵存储法和邻接表存储法的实现过程。

（2）了解图的深度优先遍历和广度优先遍历的实现过程。

2．实验内容

1. 采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵.

2. 设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法

3. 实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列

4. 实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列

3．实验环境

Visual C++ 6.0

.

.

4．实验方法和步骤（含设计）

我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可知，其邻接矩阵示意图为如下：

V0

V0

0

v1 v2 v3 v4 v5

1 0 1 0 1

V1 1 0 1 1 1 0

V2 0 1 0 0 1 0

V3 1 1 0 0 1 1

V4 0 1 1 1 0 0

V5 1 0 0 1 0 0

此时的“1”表示这两个节点有关系，“0”表示这两个节点无关系。

我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：

.

.

5．程序及测试结果

# include

# include

int visited [6];

typedef struct

{ int a[6][6];

int n;

}mgraph;

typedef struct ANode

{

typedef struct Vnode

{

typedef VNode AdjList[6];

typedef struct

{ AdjList adjlist;

int n;

}ALGraph;

void mattolist (mgraph g,ALGraph *&G)

{ int i,j;

ArcNode *p;

G=(ALGraph*)malloc(sizeof(ALGraph));

for(i=0;i

}

void dispadj(ALGraph *G)

.

G->adjlist[i].firstarc=NULL;

for(j=g.n-1;j>=0;j--)

if(g.a[i][j]!=0)

{ p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

}

G->n=g.n;

p->nextarc=G->adjlist[i].firstarc;

G->adjlist[i].firstarc=p;

for(i=0;i

ArcNode *firstarc;

}VNode;

int adjvex;

struct ANode *nextarc;

}ArcNode;

.

{ int i;

ArcNode *p;

}

void dfs (ALGraph *G,int v)

{

}

void bfs (ALGraph *G ,int v)

{ ArcNode *p;

int queue[6],front=0,rear=0;

int visited[6];

int w,i;

for(i=0;in;i++)

visited[i]=0;

printf("%d ",v);

visited[v]=1;

rear=(rear+1)%6;

queue[rear]=v;

while (front!=rear)

{ front=(front+1)%6;

w=queue[front];

p=G->adjlist[w].firstarc;

while(p!=NULL)

{

if(visited[p->adjvex]==0)

{

printf("%d ",p->adjvex);

visited[p->adjvex]=1;

ArcNode *p;

visited [v]=1;

printf("%d ",v);

p=G->adjlist[v].firstarc;

while (p!=NULL)

{ if(visited[p->adjvex]==0)

dfs(G,p->adjvex);

p=p->nextarc;

}

for(i=0;in;i++)

{ p=G->adjlist[i].firstarc;

printf("%d:",i);

}

while (p!=NULL)

{ printf("%d ",p->adjvex);

p=p->nextarc;

}

printf("n");

.

.

}

printf("n");

}

int main ()

{

bfs(G,0);

.

printf("n");

return 0;

printf("-----------从0开始的广度优先遍历--------------n");

dfs(G,0);

printf("n");

for(i=0;i

{

}

G=(ALGraph*)malloc(sizeof(ALGraph));

mattolist(g,G);

dispadj(G);

for(j=0;j

printf("%d ",g.a[i][j]);

printf("n");

for(i=0;i

for(j=0;j

g.a[i][j]=a[i][j];

g.n=6;

int i,j;

int a[6][6]={{0,1,0,1,0,1},{1,0,1,1,1,0},{0,1,0,0,1,0},

{1,1,0,0,1,1},{0,1,1,1,0,0},{1,0,0,1,0,0}};

mgraph g;

ALGraph *G;

}

}

p=p->nextarc;

rear=(rear+1)%6;

queue[rear]=p->adjvex;

printf("----------邻接矩阵----------n");

printf("----------邻接表-------------n");

printf("-----------从0开始的深度优先遍历-------------n");

.

}

.

.

6．实验分析与体会

通过此次实验，使我更加深刻的明白了图在计算机中是如何存储的，图在计算机中的存储有两种，一种是邻接矩阵存储方式，这种方式我们主要是运用到了二维数组的特性，通过二维数组来明确表现出节点与节点的位置关系，第二种就是我们说的邻接表存储结构，这种结构主要是运用到了指针来实现。而当我们在进行图的遍历时，首先要选择一个起始点，上面我们选择的是0为起始点，当我们在进行深度优先遍历时，可以用递归的思想，而在广度优先遍历时，不能用递归，这个要注意。

在这次的实验中，通过对图的操作，使我对数组和指针都有了更加深刻地认识，我认为我们要多打代码，因为这样我们才能够更全面的理解每一个指令的意思，同时我们也应该要将代码分成一个更小的指令的看，这样我们对程序将有更好地提高，更大的认识。

实验日期 ： 2016 年 11 月 17 日

.

.

教师评语

签名： 年 月 日

.

本文标签： 遍历优先实验节点