【学生版】实验六图基本操作的编程实现

1、实验六 图基本操作的编程实现【实验目的】图基本操作的编程实现要求：图基本操作的编程实现（2学时，验证型），掌握图的建立、遍历、插入、删除等基本操作的编程实现，存储结构可以在顺序结构、链接结构、联合使用多种结构等中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】验证性实验（学时数：2H）【实验内容】编程对图进行存储（邻接矩阵或邻接表都可以，由学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。设计一个将图形转成邻接链表的程序。设计一个深度优先搜索法来查找图形的程序。设计一个广度优先搜索法来查找一个图形的程序。鼓励开发出难度更高的程序。【思考问题】1.

2、图的定义和特性？2. 图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？3. 图的主要遍历思路是哪些？4. 举出图的应用范例？【参考代码】（一）基础篇/将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历/程序构思：/用户键盘输入结点与各条边，再将边转成邻接链表。/然后对采用邻接表表示的图进行深度优先遍历。#include<stdio.h>#include <stdlib.h>#define vertexnum 100 /定义最大可输入的结点个数typedef struct node /定义图形的顶点结构 int vertex; /图中的顶点信息为数字 s

3、truct node *next;Graph;Graph headvertexnum; /邻接表的表头结点int Visitedvertexnum; /遍历记录void Create_l_Graph(int Vertex1,int Vertex2,int no) /以邻接链表建立图形 Graph *searchP; /结点声明 Graph *New; /新结点声明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New->vertex=Vertex2; New->next=NULL; searchP=&(h

4、eadVertex1); while(searchP->next!=NULL) searchP=searchP->next; searchP->next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New->vertex=Vertex1; New->next=NULL; searchP=&(headVertex2); while(searchP->next!=NULL) searchP=searchP->next; searchP->next =New; void showme

5、nu() /显示菜单printf(" 欢迎使用图的操作演示软件n");printf("t1、创建图的邻接表n");printf("t2、图的输出n");printf("t3、图的深度优先遍历n");printf("t4、退出程序n");void print_l_graph(Graph *head) /输出邻接链表的数据 Graph *searchP; searchP=head->next; while(searchP!=NULL) printf("n");void DF

6、S(int vertex) /深度优先遍历 Graph *SearchP; /结点声明 /标记某个结点已遍历过 printf("%d=>",vertex); SearchP=headvertex.next; while(SearchP!=NULL) if( ) /判断结点未被遍历过 /递归调用深度优先遍历函数 SearchP=SearchP->next; /下一个邻接点 void main() int source; /图中一条边的起始顶点 int destination; /图中一条边的终止顶点 int i,j; int vermax; /定义图中最大的顶点数

7、 int edgemax; /定义图中最大的边数 int choice; int no; while(1)showmenu();printf(" 请输入你的选择：");scanf("%d",&choice);fflush(stdin);/清除键盘缓冲区switch(choice) case 1:printf("请输入图的类别（有向图-1，无向图-0）:"); scanf("%d",&no); printf("请输入图中的总顶点数和边数:"); scanf("%d%d&q

8、uot;,&vermax,&edgemax); for(i=1;i<vermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i<=edgemax;i+)printf("请输入第%d条边的起点：",i);scanf("%d",&source);printf("请输入第%d条边的终点：",i);scanf("%d",&destination);if(source=destination) printf("输入有误！

9、n");/出错：自身循环 else /调用建立邻接链表 Create_l_Graph(source,destination,no); printf("图创建成功，按任意键继续n"); getch(); system("cls"); break; case 2:printf("图的邻接表如下：n"); for(i=1;i<=vermax;i+)printf("顶点%d:",i); print_l_graph(&headi);/调用输出邻接链表数据 printf("n");

10、system("pause"); system("cls"); break; case 3:for(i=1;i<=vermax;i+) Visitedi=0; printf("请输入遍历的起点:"); scanf("%d",&source); printf("图的深度优先遍历结果为：n"); DFS(source); printf("ENDn"); system("pause"); system("cls"); break

11、; case 4:return; default: printf("你的输入有误，请从新输入！n"); system("pause"); system("cls"); (二)提高篇/将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历/程序构思：/用户键盘输入结点与各个边，再将边转成邻接链表。/然后对采用邻接表表示的图进行广度优先遍历。#include<stdio.h>#include <stdlib.h>#define vertexnum 100 /定义最大可输入的结点个数#define QueueMax

12、 100typedef struct node /定义图形的顶点结构 int vertex; /图中的顶点信息为数字 struct node *next;Graph;Graph headvertexnum; /邻接表的表头结点int Visitedvertexnum; /遍历记录int Front=-1;int Rear=-1;int QueueQueueMax;int Enqueue(int Vertex) /元素入队 if (Rear>=QueueMax) /队列已满 return -1; else Rear+; /队列尾端指针后移 QueueRear=Vertex; /将值存入队列

13、中 return 1; int Dequeue() /元素出队 if (Front>=Rear) /队列已空 return -1; else Front+; /队头指针后移 return QueueFront; void BFS(int Vertex)/广度优先搜索 void Create_l_Graph(int Vertex1,int Vertex2,int no) /以邻接链表建立图形 Graph *searchP; /结点声明 Graph *New; /新结点声明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) N

14、ew->vertex=Vertex2; New->next=NULL; searchP=&(headVertex1); while(searchP->next!=NULL) searchP=searchP->next; searchP->next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New->vertex=Vertex1; New->next=NULL; searchP=&(headVertex2); while(searchP->next!=NULL) sea

15、rchP=searchP->next; searchP->next =New; void showmenu() /显示菜单printf(" 欢迎使用图的操作演示软件n");printf("t1、创建图的邻接表n");printf("t2、图的输出n");printf("t3、图的广度优先遍历n");printf("t4、退出程序n");void print_l_graph(Graph *head) /输出邻接链表的数据 Graph *searchP; searchP=head->

16、;next; while(searchP!=NULL) printf("%d",searchP->vertex); searchP=searchP->next; printf("n");void main() int source; /图中一条边的起始顶点 int destination; /图中一条边的终止顶点 int i,j; int vermax; /定义图中最大的顶点数 int edgemax; /定义图中最大的边数 int choice; int no; while(1)showmenu();printf(" 请输入你的选

17、择：");scanf("%d",&choice);fflush(stdin);/清除键盘缓冲区switch(choice) case 1:printf("请输入图的类别（有向图-1，无向图-0）:"); scanf("%d",&no); printf("请输入图中的总顶点数和边数:"); scanf("%d%d",&vermax,&edgemax); for(i=1;i<vermax;i+)headi.vertex = i;headi.next =

18、 NULL; for(i=1;i<=edgemax;i+)printf("请输入第%d条边的起点：",i);scanf("%d",&source);printf("请输入第%d条边的终点：",i);scanf("%d",&destination);if(source=destination) printf("输入有误！n");/出错：自身循环 else /调用建立邻接链表 Create_l_Graph(source,destination,no); printf("图创建成功，按任意键继续n"); getch(); system("cls"); break; case 2:printf("图的邻接表如下：n"); for(i=1;i