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

【实验目的】

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

图基本操作的编程实现（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