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

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

【实验目的】

图基本操作的编程实现 要求:

图基本操作的编程实现(2学时,验证型),掌握图的建立、遍历、插入、删除等基本操作的编程实现,存储结构可以在顺序结构、结构、联合使用多种结构等中任选,也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】

验证性实验(学时数:2H)

【实验容】

编程对图进行存储(邻接矩阵或邻接表都可以,由学生自由选择),之后可以询问任何两个结点之间是否有通路和路径数。

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

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

设计一个广度优先搜索法来查找一个图形的程序。 鼓励开发出难度更高的程序。

【思考问题】

1. 图的定义和特性?

2. 图的主要存储结构是什么?是独立的某种还是多种数据结构的综合? 3. 图的主要遍历思路是哪些? 4. 举出图的应用例?

【参考代码】

(一)将一个将图转成邻接矩阵的程序. /*程序构思:*/

/*用户输入结点与各个边,再将边转成邻接矩阵。*/ #include

#define Max 6 /* 定义最大可输入的结点个数 */ int Graph[Max][Max]; /*图形邻接数组 */

/*===============================================*/ /*输出邻接矩阵数据===============================*/ /*===============================================*/ void print_M_Graph() {

int i,j;

printf(\ for (i=0;i

for(i=0;i

printf(\ for (j=0;j

printf(\ printf(\ } }

/*===============================================*/ /*以邻接矩阵建立图形=============================*/

/*===============================================*/ 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

printf(\:\ scanf(\

if(Source ==-1) break;

printf(\:\ scanf(\

if(Source==Destination) /* 出错:自身循环*/ printf(\: Self Loop!! \\n\

else if (Source >= Max || Destination >= Max) /* 出错:超出围*/ printf (\: out of range!! \\n\ else /*调用建立邻接数组 */

Create_M_Graph(Source,Destination); }

printf(\

; /*调用输出邻接数组数据*/ }

/*希望的结果 */ /*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 #include

#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 = ; New ->next = NULL;

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(\ searchP=searchP->next; }

printf(\ }

/*===============================================*/ /*主程序=========================================*/ /*===============================================*/ void main() {

int Source; /*起始顶点*/ int Destination; /*终止顶点*/ int i,j;

for (i=0;i