数据结构实验四

1、数据结构实验报告实验题目： 实验四、图 姓名： 张鑫 学号： 142054301 班级： 1420543 系名： 计算机工程系 专业： 计算机科学与技术 指导老师： 刘海静 实验时间： 2016年5月30日 实验地点： 专业软件实验室 【实验概述】1.实验目的及要求目的：1熟练掌握图的两种存储结构，邻接矩阵和邻接表的表示方法。2熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤。3能按Prim算法构造最小生成树。4了解并掌握拓扑排序、关键路径、最短路径的算法思想。要求：预习并掌握图的逻辑结构特点、无向图和有向图的两种存储结构表示、图的深度优先和广度优先算法思想，最小生成

2、树的概念以及普利姆算法和克鲁斯卡尔构造最小生成树的过程。2.实验原理1、图的逻辑结构特点：图是一种较线性表和树更为复杂的数据结构。在图结构中，结点之间的关系可以是任意的，任意两个数据元素之间都可能相关。2、图没有顺序存储结构。3、图的邻接矩阵表示法：设图 A = (V, E)是一个有 n 个顶点的图, 则图的邻接矩阵是一个n行n列的二维数组Aij 。对有向图和无向图而言，数组元素或为1或为0。无向图的邻接矩阵是对称矩阵，有向图的不一定。对网来说，邻接矩阵中元素或者为两个顶点之间的边的权值，或者为无穷大。4、图的邻接表表示法：是一种顺序分配与链式分配相结合的存储方法，它包括两部分：一部分是单链表

3、，用来存放边/弧的信息；另一部分是数组，主要用来存放顶点本身的数据信息。对无向图而言，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点）。对有向图而言，通常要分为邻接表和逆邻接表。5、图的遍历是从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历 ，分为深度优先和广度优先搜索。6、最小生成树：生成树中每条边上权值之和达到最小。最小生成树是实际应用很广泛的。构造最小生成树的经典算法有普里姆算法和克鲁斯卡尔算法。、3.实验环境（使用的软件）VC+6.0【实验内容】1. 实验算法设计假设有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连

4、通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。要求：1、 创建带有n（顶点个数由用户输入）个顶点的带权无向图。可以是邻接矩阵或者邻接表存储。2、 使用深度或广度优先搜索对图中顶点进行遍历输出。2.实验过程（源代码及描述、调试过程及分析）#include <stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define Status int #define

5、 MAX_VERTEX_NUM 8 /*顶点最大个数*/ #define VertexType char /*顶点元素类型*/ enum BOOlean False,True; BOOlean visitedMAX_VERTEX_NUM; /全局变量-访问标志数组typedef struct ArcNode int adjvex; /顶点编号struct ArcNode *nextarc; int weight; /*边的权*/ ArcNode; /*表结点*/ typedef struct VNode VertexType data; ArcNode *firstarc; VNode/*头结

6、点*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum;/*顶点的实际数，边的实际数*/ ALGraph;#define MAXQSIZE 100 /最大队列长度-1typedef struct int *base; / 动态分配存储空间 int front; / 若队列不空，指向队列头元素 int rear; / 若队列不空，指向队列尾元素的下 /一个位置 Queue;void InitQueue (Queue &Q) Q.base =new intMAXQSIZE; / 存储分配失败

7、 Q.front = Q.rear = 0; void DeQueue (Queue &Q, int &e) e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; void EnQueue (Queue &Q, int e) Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; /建立图的邻接表void creat_link(ALGraph *G) int i,j; ArcNode *s; printf("请依次输入顶点数、边数："); scanf(&q

8、uot;%d%d",&G->vexnum,&G->arcnum); for (i=0;i<G->vexnum;i+) G->verticesi.data='A'+i;G->verticesi.firstarc=NULL; for (i=0;i<G->vexnum;) printf("请输入顶点的数组坐标(若退出，请输入-1)："); scanf("%d",&i); if(i=-1) break; printf("请输入顶点所指向下一个顶点的数组坐标

9、："); scanf("%d",&j); s=(ArcNode *)malloc(sizeof(ArcNode); s->adjvex=j; s->nextarc=G->verticesi.firstarc; G->verticesi.firstarc=s; / 输出邻接表void visit(ALGraph G) int i; ArcNode *p; printf("%4s%6s%18sn","NO","data","adjvexs of arcs")

10、; for (i=0;i<G.vexnum;i+) printf("%4d%5c",i,G.verticesi.data); for(p=G.verticesi.firstarc;p;p=p->nextarc) printf("%3d",p->adjvex); printf("n"); /在图G中寻找第v个顶点的第一个邻接顶点int FirstAdjVex(ALGraph G,int v) if(!G.verticesv.firstarc) return 0; else return(G.verticesv.firs

11、tarc->adjvex); /在图G中寻找第v个顶点的相对于u的下一个邻接顶点int NextAdjVex(ALGraph G,int v,int u) ArcNode *p; p=G.verticesv.firstarc; while(p->adjvex!=u) p=p->nextarc; /在顶点v的弧链中找到顶点u if(p->nextarc=NULL) return 0; /若已是最后一个顶点，返回0 else return(p->nextarc->adjvex); /返回下一个邻接顶点的序号 /采用邻接表存储实现无向图的深度优先递归遍历void

12、DFS(ALGraph G,int i) int w; visitedi=True; /访问第i个顶点printf("%d->",i); for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w) if(!visitedw) DFS(G,w); /对尚未访问的邻接顶点w调用DFS void DFSTraverse(ALGraph G) int i; printf("DFSTraverse:"); for(i=0;i<G.vexnum;i+) visitedi=False; /访问标志数组初始化for(i=0;i&

13、lt;G.vexnum;i+) if(!visitedi) DFS(G,i); /对尚未访问的顶点调用DFS /按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited void BFSTraverse(ALGraph G) int i,u,w; Queue q; printf("BFSTreverse:"); for(i=0;i<G.vexnum;i+) visitedi=False; /访问标志数组初始化InitQueue(q); /初始化队列for(i=0;i<G.vexnum;i+) if(!visitedi) visitedi=True; /访问顶点i printf("%d->",i); EnQueue(q,i); /将序号i入队列while(!(q.front =q.rear) /若队列不空，继续DeQueue(q,u); /将队头元素出队列并置为u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if(!visitedw) /对u的尚未访问的邻接顶点w进行访问并入队列visitedw=True; printf("%d->",w); EnQueue(q,