实验六 图基本操作的编程实现

实验六图基本操作的编程实现【实验目的】图基本操作的编程实现要求：图基本操作的编程实现（2学时，验证型），掌握图的建立、遍历、插入、删除等基本操作的编程实现，存储结构可以在顺序结构、链接结构、联合使用多种结构等中任选，也可以全部实现。

也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】验证性实验（学时数：2H）【实验内容】编程对图进行存储（邻接矩阵或邻接表都可以，由学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。

设计一个将图形转成邻接链表的程序。

设计一个深度优先搜索法来查找图形的程序。

设计一个广度优先搜索法来查找一个图形的程序。

鼓励开发出难度更高的程序。

【思考问题】1.图的定义和特性？2.图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？3.图的主要遍历思路是哪些？4.举出图的应用范例？【参考代码】（一）将一个将图转成邻接矩阵的程序．/*程序构思：*//*用户输入结点与各个边，再将边转成邻接矩阵。

*/#include<stdio.h>#define Max 6 /* 定义最大可输入的结点个数 */int Graph[Max][Max]; /*图形邻接数组 *//*===============================================*//*输出邻接矩阵数据===============================*//*===============================================*/void print_M_Graph(){int i,j;printf("Vertice");for (i=0;i<Max;i++)printf("%3d",i);printf("\n");for(i=0;i<Max;i++){printf("%4d ",i);for (j=0;j<Max;j++)printf("%3d" );}}/*===============================================*//*以邻接矩阵建立图形=============================*//*===============================================*/void Create_M_Graph(int Verticel,int Vertice2){Graph[Verticel][Vertice2]=1; /* 将矩阵内容设为1 */}/*===============================================*//*主程序=========================================*//*===============================================*/void main(){int Source; /*起始顶点*/int Destination; /*终止顶点*/int i,j;for (i=0;i<Max;i++)for (j=0;j<Max;j++)Graph[i][i]=0;while(1){printf("please input the Edge's source：");scanf("%d",&Source);if(Source ==-1)break;printf("Please input the Edge's Destination：");scanf("%d",&Destination);if(Source==Destination) /* 出错：自身循环*/printf("***Error***： Self Loop!! \n");else if (Source >= Max || Destination >= Max) /* 出错：超出范围*/ printf ("***Error***： out of range!! \n");else /*调用建立邻接数组 */Create_M_Graph(Source,Destination);}printf("##Graph##\n");; /*调用输出邻接数组数据*/}/*希望的结果 *//*please input the Edge's source：0 *//*Please input the Edge's Destination：4 *//*please input the Edge's source：1 *//*Please input the Edge's Destination：0 *//*please input the Edge's source：1 *//*Please input the Edge's Destination：4 *//*please input the Edge's source：2 *//*Please input the Edge's Destination：1 *//*please input the Edge's source：3 *//*Please input the Edge's Destination：2 *//*please input the Edge's source：4 *//*Please input the Edge's Destination：3 *//*please input the Edge's source：-1 *//*##Graph## *//*Vertice 0 1 2 3 4 5 *//* 0 0 0 0 0 1 0 *//* 1 1 0 0 0 1 0 *//* 2 0 1 0 0 0 0 *//* 3 0 0 1 0 0 0 *//* 4 0 0 0 1 0 0 *//* 5 0 0 0 0 0 0 */(二) 将一个将图转成邻接表的程序．/*程序构思：*//*用户输入结点与各个边，再将边转成邻接链表。

*/#include<stdio.h>#include <stdlib.h>#define vertexnum 6 /* 定义最大可输入的结点个数 */ typedef struct node /*定义图形的顶点结构 */ {int vertex;struct node *next;}Graph;Graph head[vertexnum];/*===============================================*//*以邻接链表建立图形=============================*//*===============================================*/ void Create_l_Graph(int Vertex1,int Vertex2){Graph *searchP; /* 结点声明 */Graph *New; /* 新结点声明 */New = (Graph *) malloc(sizeof(struct node));if (New!= NULL ){New ->vertex = ;searchP = &(head[Vertex1]);while ( searchP->next != NULL);searchP->next = New;}}/*===============================================*//*输出邻接链表的数据===============================*/ /*===============================================*/ void print_l_graph(struct node *head){Graph *searchP;searchP = head->next;while ( searchP != NULL ){printf("[%d]",searchP->vertex);searchP=searchP->next;}printf("\n");}/*===============================================*//*主程序=========================================*//*===============================================*/ void main(){int Source; /*起始顶点*/int Destination; /*终止顶点*/int i,j;for (i=0;i<vertexnum;i++){head[i].vertex = i;head[i].next = NULL;}while(1){printf("please input the Edge's source：");scanf("%d",&Source);if(Source ==-1)break;printf("Please input the Edge's Destination：");scanf("%d",&Destination);if(Source==Destination) /* 出错：自身循环*/printf("***Error***： Self Loop!! \n");else if (Source >= vertexnum || Destination >= vertexnum)/* 出错：超出范围*/printf ("***Error***： out of range!! \n");else /*调用建立邻接链表 */Create_l_Graph(Source,Destination);}printf("##Graph##\n");for (i=0;i<=vertexnum;i++){printf("vertex[%d]:",i);print_l_graph(&head[i]); /*调用输出邻接链表数据*/}}/*希望的结果 *//*please input the Edge's source：2 *//*Please input the Edge's Destination：1 *//*please input the Edge's source：2 *//*Please input the Edge's Destination：3 *//*please input the Edge's source：3 *//*Please input the Edge's Destination：4 *//*please input the Edge's source：4 *//*Please input the Edge's Destination：1 *//*please input the Edge's source：4 *//*Please input the Edge's Destination：2 *//*please input the Edge's source：4 *//*Please input the Edge's Destination：5 *//*please input the Edge's source：5 *//*Please input the Edge's Destination：1 *//*please input the Edge's source：-1 *//*##Graph## *//*Vertex[0]: *//*Vertex[1]: *//*Vertex[2]:[1][3] *//*Vertex[3]:[4] *//*Vertex[4]:[1][2][5] *//*Vertex[5]:[1] */（三）图的深度优先遍历（搜索）。