实验七图的建立及其应用

1、实验七 图的建立及其应用一、实验目的：（1）掌握图的存储思想及其存储实现。（2）掌握图的深度、广度优先遍历算法思想及其程序实现。（3）掌握图的常见应用算法的思想及其程序实现。（4）理解有向无环图、最短路径等算法二、实验要求1.将算法中的横线内容填写完整，使程序能正常运行2.在主函数中设计一个简单的菜单，具有如下功能。（1）建立有向图的邻接表； （2）输出邻接表； 3.实现图的深度优先遍历的算法（选做）4.完成实际应用（选做）三、实验原理1、图（GRAPH）是一种复杂的数据结构，结点之间的关系可以是任意的，由此图的应用极为广泛，已经渗透到如物理、化学、电讯工程、计算机科学等领域。2、图存储结构：

2、邻接矩阵表示法和邻接表表示法，本次实验图主要以邻接表进行存储。 用邻接矩阵表示法表示图如下图所示：V3V03 0 1 0 1 A = 1 0 1 1 V1V2 0 1 0 0 1 0 0 1 一个无向图的邻接矩阵表示无向图对应的邻接表表示如下图所示： 序号 vertex firstedge0V0 1 3 V11 0 2 3 112V2 V3 3 0 1 一个无向图的的邻接表表示四、实验程序说明图类型定义typedef struct Nodeint dest; /邻接边的弧头结点序号struct Node *next;Edge; /邻接边单链表的结点的结构体typedef structDataT

3、ype data; /图顶点Edge *adj; /邻接边的头指针AdjLHeight; /数组的数据元素类型结构体typedef structAdjLHeight aMaxVertices; /邻接表数组int numOfVerts; /结点个数int numOfEdges; /边个数AdjLGraph; /邻接表结构体五、参考程序#include<malloc.h> /* malloc()等 */#include<stdio.h> /* EOF(=Z或F6),NULL */#include<stdlib.h> /* atoi() */#include&l

4、t;process.h> /* exit() */typedef char DataType;#define MaxVertices 10void AdjInitiate(AdjLGraph *G) /初始化图int i;G->numOfEdges=0;G->numOfVerts=0;for(i=0;i<MaxVertices;i+)G->ai.adj = NULL ;/设置邻接边单链表头指针初值void InsertVertex(AdjLGraph *G,int i,DataType vertex)/在图中的第i个位置插入顶点数据元素vertexif(i>

5、=0&&i<MaxVertices)G->ai.data =vertex; /存储顶点数据元素vertex G->numOfVerts+ ; /个数加1else printf("结点越界");void InsertEdge(AdjLGraph *G,int v1,int v2)/在图中加入边<v1,v2>的信息Edge *p;if(v1<0|v1>=G->numOfVerts|v2<0|v2>=G->numOfVerts)printf("参数v1和v2越界出错!");exi

6、t(0);p=(Edge*)malloc(sizeof(Edge);/申请邻接边单链表结点空间p->dest=v2; /设置邻接边弧头序号 p->next = G->av1.adj ; /新结点插入邻接表的表头 G->av1.adj = p ; /头指针指向新的单链表表头G->numOfEdges+; /边个数加1int GetFirstVex(AdjLGraph G,int v)/取图G中结点v的第一个邻接结点Edge *p;if(v<0|v>=G.numOfVerts)printf("参数出错!");exit(0);p=G.av

7、.adj;if(p!=NULL)return p->dest;else return -1;int GetNextVex(AdjLGraph G,int v1,int v2)/取图G中结点v1的邻接结点v2的下一个邻接结点Edge *p;if(v1<0|v1>=G.numOfVerts|v2<0|v2>=G.numOfVerts)printf("参数v1和v2越界出错!");exit(0);p=G.av1.adj;while(p!=NULL)if(p->dest!=v2) p = p->next ;continue;else bre

8、ak;p=p->next;if(p!=NULL) return p->dest;else return -1;void main(void)int i,k,n,e,v1,v2;char c1;Edge *p;AdjLGraph G;AdjInitiate(&G);printf("输入图的顶点数n");scanf("%d",&n);getchar();printf("输入图顶点为（请输入字母）n");for(i=0;i<n;i+) scanf("%c",&c1); /通过键盘

9、，输入图的顶点 getchar(); InsertVertex(&G,i,c1) ; /插入顶点printf("输入图的边数n");scanf("%d",&e);printf("如果边v1->v2，则输入0，1n");for(k=0;k<e;k+)printf("输入边的顶点为（请输入数字）：");scanf("%d,%d",&v1,&v2); /通过键盘，输入图的邻接边的两个顶点 InsertEdge(&G,v1,v2) ; /插入边for(

10、i=0;i<n;i+)/输出邻接表printf("%ct",G.ai.data);p=G.ai.adj;if(p=NULL) printf("数据为空");else while(p!=NULL) printf("%d->",p->dest); p=p->next; printf(""); printf("n");调试参考结果：CBAA序号 vertex firstedge0 1 B1 2 C102 六、应用题（一）校园导游图实验内容：1、 设计学生所在学校的校园平面图，所含景点不少于10个。以图中顶点表示学校内各个景点，并存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。2、 为来访客人提供图中任意景点相关信息的查询。3、 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。测试数据：由学生根据学校的实际情况指定。（二）经济代价最低