内容发布更新时间 : 2024/11/19 8:35:42星期一 下面是文章的全部内容请认真阅读。
实验六 图基本操作的编程实现
【实验目的】
图基本操作的编程实现 要求：
图基本操作的编程实现（2学时，验证型），掌握图的建立、遍历、插入、删除等基本操作的编程实现，存储结构可以在顺序结构、链接结构、联合使用多种结构等中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。
【实验性质】
验证性实验（学时数：2H）
【实验内容】
编程对图进行存储（邻接矩阵或邻接表都可以，由学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。
设计一个将图形转成邻接链表的程序。
设计一个深度优先搜索法来查找图形的程序。
设计一个广度优先搜索法来查找一个图形的程序。 鼓励开发出难度更高的程序。
【思考问题】
1. 图的定义和特性？
2. 图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？ 3. 图的主要遍历思路是哪些？ 4. 举出图的应用范例？
【参考代码】
（一）基础篇
//将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历． //程序构思：
//用户键盘输入结点与各条边，再将边转成邻接链表。 //然后对采用邻接表表示的图进行深度优先遍历。 #include
#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(\、创建图的邻接表\\n\ printf(\、图的输出\\n\
printf(\、图的深度优先遍历\\n\ printf(\、退出程序\\n\ }
void print_l_graph(Graph *head)
{ //输出邻接链表的数据 Graph *searchP; searchP=head->next; while(searchP!=NULL) {
}
printf(\ }
void DFS(int vertex)
{ //深度优先遍历
Graph *SearchP; //结点声明
//标记某个结点已遍历过 printf(\ SearchP=head[vertex].next; while(SearchP!=NULL) {
if( ) //判断结点未被遍历过
//递归调用深度优先遍历函数 SearchP=SearchP->next; //下一个邻接点 } }
void main() {
int source; //图中一条边的起始顶点 int destination; //图中一条边的终止顶点 int i,j;
int vermax; //定义图中最大的顶点数 int edgemax; //定义图中最大的边数 int choice; int no;
while(1) {
showmenu();
printf(\请输入你的选择：\ scanf(\
fflush(stdin);//清除键盘缓冲区 switch(choice) {
case 1:printf(\请输入图的类别（有向图-1，无向图-0）:\ scanf(\
printf(\请输入图中的总顶点数和边数:\ scanf(\ for(i=1;i head[i].vertex = i; head[i].next = NULL; } for(i=1;i<=edgemax;i++) { printf(\请输入第%d条边的起点：\ scanf(\ printf(\请输入第%d条边的终点：\ scanf(\ if(source==destination)