【学生版】实验六 图基本操作的编程实现.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;
显示全部