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

实验六 图基本操作的编程实现 【实验目的】 图基本操作的编程实现 要求： 图基本操作的编程实现（2学时，验证型），掌握图的建立、遍历、插入、删除等基本操作的编程实现，存储结构可以在顺序结构、链接结构、联合使用多种结构等中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 编程对图进行存储（邻接矩阵或邻接表都可以，由学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。 设计一个将图形转成邻接链表的程序。 设计一个深度优先有哪些信誉好的足球投注网站法来查找图形的程序。 设计一个广度优先有哪些信誉好的足球投注网站法来查找一个图形的程序。 鼓励开发出难度更高的程序。 【思考问题】 图的定义和特性？ 图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？ 图的主要遍历思路是哪些？ 举出图的应用范例？ 【参考代码】 （一）基础篇 //将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历． //程序构思： //用户键盘输入结点与各条边，再将边转成邻接链表。 //然后对采用邻接表表示的图进行深度优先遍历。 #includestdio.h #include stdlib.h #define vertexnum 100 //定义最大可输入的结点个数 typedef struct node //定义图形的顶点结构 { int vertex; //图中的顶点信息为数字 struct node *next; }Graph; Graph head[vertexnum]; //邻接表的表头结点 int Visited[vertexnum]; //遍历记录 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=(head[Vertex1]); 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=(head[Vertex2]); while(searchP-next!=NULL) searchP=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-next; while(searchP!=NULL) { } printf(\n); } void DFS(int vertex) { //深度优先遍历 Graph *SearchP; //结点声明 //标记某个结点已遍历过 printf([%d]==,vertex); SearchP=head[vertex].next;