图形数据结构实验

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 图形数据结构实验

班 级： 学 号： 姓 名：

评语： 成绩： 指导教师： 批阅时间： 年 月 日

《 数据结构 》实验报告 - 1 -

图形数据结构实验报告要求

1目的与要求:

1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；

2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现； 3）掌握AOV-网普里姆构造最小生成树算法的数据结构和算法实现； 4）掌握AOE-网关路经的生成算法和实现；

5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；

6）认真书写实验报告,并按时提交（第12周周一提交）。

2 实验内容或题目

题目： 一、图形数据结构实验——图的建立与遍历。 内容：

1） 使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结

构。

2） 在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并

给出遍历结果（序列）。

V1 V2 V3 V4 V5 V6 V7 V8 图1 无向图

《 数据结构 》实验报告 - 2 -

V1 V2 V3 V4 V5 V6 V7 V8 例2 有向图

题目：二、连通网的最小生成树及其应用实验（选做）

内容：对下图所示通信连通网，按照普里姆算法实现其最小生成树。

V1

6 V2

5 1 v4

5 v3

5 4 6 2

v6

3 v5

6 通信连通网（权值单位：百万元）

3 实验步骤与源程序

#include #include

《 数据结构 》实验报告 - 3 -

#define MaxVertexNum 10 int visited[MaxVertexNum]; int visitde[MaxVertexNum]; typedef struct edgenode {

int adjvex;

struct edgenode *next; }edgenode;

typedef struct vexnode {

int data;

edgenode *link; }vexnode;

typedef struct {

vexnode vertex[MaxVertexNum]; int vexnum,arcnum; }AdjList;

void creat_wxdjlist(AdjList *G)//邻接表建立有向图 {

edgenode *s; int i,j,k;

printf(\请输入图的结点数和边数:\\n\

scanf(\printf(\请输入图的结点:\\n\ for(i=0;ivexnum;i++) {

getchar();

scanf(\ G->vertex[i].link=NULL; visited[i]=0; visitde[i]=0; }

printf(\请输入每条边对应的两个顶点的序号(输入格式为:i,j):\\n\for(k=0;karcnum;k++) {

getchar();

printf(\请输入第%d条边的顶点序号：\ scanf(\

s=(edgenode *)malloc(sizeof(edgenode)); s->adjvex=j-1;

s->next=G->vertex[i-1].link;//采用头插法 G->vertex[i-1].link=s; }

《 数据结构 》实验报告 - 4 -

}

void Dfsjb_visit(AdjList G,int i)//深度遍历有向图 {

edgenode *p;

if(visited[i]==0) {

printf(\}

visited[i]=1;

p=G.vertex[i].link; while(p!=NULL) {

if(visited[p->adjvex]==0) Dfsjb_visit(G,p->adjvex); p=p->next; } }

void Bfsljb_visit(AdjList G,int n)//广度遍历有向图 {

int i,front ,rear,q[MaxVertexNum]; edgenode *p; front=-1; rear=-1;

if(visitde[n]==0) {

printf(\}

visitde[n]=1; rear=rear+1; q[rear]=n;

while(rear!=front) {

front=front+1; i=q[front];

p=G.vertex[i].link; while(p!=NULL) {

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

printf(\ visitde[p->adjvex]=1; rear=rear+1;

q[rear]=p->adjvex;

《 数据结构 》实验报告 - 5 -

}

p=p->next; } } }

typedef struct {

int vexs[MaxVertexNum];

int edges[MaxVertexNum][MaxVertexNum]; int n,e;

}MGraph;

void CreateMGraph(MGraph *G) //邻接矩阵建立无向图 {

int i,j,k,m,n;

printf(\请输入顶点数和边数:\\n\ scanf(\

printf(\请输入顶点信息每个顶点以回车作为结束:\\n\ for(i=0;in;i++) {

getchar();

scanf(\ visited[i]=0; visitde[i]=0; }

for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0;

printf(\请输入每条边对应的两个顶点的序号(输入格式为:i,j):\\n\ for(k=0;ke;k++) {

getchar();

printf(\请输入第%d条边的顶点序号：\ scanf(\

G->edges[m-1][n-1]=G->edges[m-1][n-1]=1; } }

void DFSM(MGraph G,int i) //深度遍历无向图 {

int j;

if(visited[i]==0) {

printf(\

《 数据结构 》实验报告 - 6 -

visited[i]=1; }

for(j=0;j

if((G.edges[i][j]==1 )&&( visited[j]==0)) DFSM(G,j); }

void Bfsjz_visit(MGraph G,int k)//广度遍历无向图 {

int i,j,front,rear,q[MaxVertexNum]; front=-1;rear=-1; if(visitde[k]==0) {

printf(\ visitde[k]=1; }

rear=rear+1; q[rear]=k;

while(rear!=front) {

front=front+1; i=q[front];

for(j=0;j<=G.n;j++) {

if((G.edges[i][j]==1)&&(visitde[j]==0)) {

printf(\ visitde[j]=1; rear=rear+1; q[rear]=j; } } } }

void main() {

int j,m;

printf(\邻接表建立有向图*******************\\n\ AdjList q;

creat_wxdjlist(&q);

printf(\从结点Vi开始深度优化请输入i:\scanf(\--j;

printf(\深度优化搜索为:\\n\for(m=0;m

《 数据结构 》实验报告 - 7 -

Dfsjb_visit(q,j); j++; }

printf(\从结点Vi开始广度搜索请输入i:\scanf(\ --j;

printf(\广度搜索为:\\n\for(m=0;m

Bfsljb_visit(q,j); j++; }

printf(\邻接矩阵建立无向图**********************\\n\MGraph p;

CreateMGraph(&p);

printf(\从结点Vi开始深度优化请输入i:\scanf(\--j;

printf(\深度优化搜索为:\\n\DFSM(p,j) ;

printf(\从结点Vi开始广度搜索请输入i:\scanf(\ --j;

printf(\广度搜索为:\\n\ Bfsjz_visit(p,j); }

4 测试数据与实验结果（可以抓图粘贴）

《 数据结构 》实验报告 - 8 -

5 结果分析与实验体会

通过这次的实验我基本上 掌握了图的邻接矩阵及邻接表的建立与基本操作的实现,进一步地了解了图的邻接矩阵的物理储存结构,基于本次实验使我对邻接矩阵和邻接表的深度优先搜索遍历算法和图的广度优先搜索遍历算法有了很好的了解.

本文来源：https://www.bwwdw.com/article/cy3p.html