|
#2
寒风中的细雨2010-05-31 19:18
#include <stdio.h>
#include <string.h> #include <stdlib.h> #define MAX_VERTEX_NUM 20 int visited[MAX_VERTEX_NUM]; typedef char Vertex_Type[5]; typedef enum { DG, DN, UDG, UDN }Graph_Kind; typedef struct Arc_Node { int adj_vertex;//邻接定点所在定点向量表中的位置 int weight;//权值 struct Arc_Node *next_arc;//指向下一个邻接点 }Arc_Node; typedef struct Vertex_Node { Vertex_Type data;//表示顶点的类型 struct Arc_Node *first_arc;//指向第一个邻接顶点 }Vertex_Node; typedef struct { Vertex_Node vertexs_vectors[MAX_VERTEX_NUM];//顶点向量 int vertex_num;//顶点数 int arc_num;//边数 Graph_Kind kind;//图的类型 }ALGraph; void Init_ALGraph( ALGraph &G ) { printf("输入图的边数:"); scanf("%d", &G.arc_num); printf("输入图的顶点数:"); scanf("%d", &G.vertex_num); printf("输入图的类型(0:DG 1:DN 2:UDG 3:UDN): "); scanf("%d", &G.kind); printf("初始化顶点向量(例如:v1 v2 v3):"); for( int i=0; i<G.vertex_num; ++i ) { scanf("%s", G.vertexs_vectors[i].data); G.vertexs_vectors[i].first_arc = NULL;//初始值指向空 } } int Get_Vertex_Location( ALGraph G, Vertex_Type V ) { for( int i=0; i<G.vertex_num; ++i ) if( strcmp( G.vertexs_vectors[i].data, V )==0 ) return i; exit(0);//表示操作错误就结束 } void Create_ALGraph( ALGraph &G ) { Init_ALGraph( G ); Vertex_Type v1, v2; int i, v1_site, v2_site; printf("输入与弧相关联的顶点和相关信息(v1 -- v2或v1 -> v2)\n"); for( i=0; i<G.arc_num; ++i ) { scanf("%s %*s %s", v1, v2); v1_site = Get_Vertex_Location( G, v1 ); v2_site = Get_Vertex_Location( G, v2 ); Arc_Node *p1, *p2; p1 = (Arc_Node*) malloc (sizeof(Arc_Node)); p1->next_arc = G.vertexs_vectors[v1_site].first_arc; G.vertexs_vectors[v1_site].first_arc = p1; p1->adj_vertex = v2_site; p1->weight = 0;//设置不带权的权值全为零 switch( G.kind ) { case DG://有向图 break; case DN://有向网 printf("输入权值:"); scanf("%d", &p1->weight); break; case UDN://无向网 printf("输入权值:"); scanf("%d", &p1->weight); case UDG://无向图 p2 = (Arc_Node*) malloc (sizeof(Arc_Node)); p2->next_arc = G.vertexs_vectors[v2_site].first_arc; G.vertexs_vectors[v2_site].first_arc = p2; p2->adj_vertex = v1_site; p2->weight = p1->weight; break; default://表示出错 exit(0); } } } void Print_ALGraph( ALGraph G ) { Arc_Node *p; for( int i=0; i<G.vertex_num; ++i ) { p = G.vertexs_vectors[i].first_arc; while( p ) { switch( G.kind ) { case DG: printf("< %s ->", G.vertexs_vectors[i].data); printf(" %s >\n", G.vertexs_vectors[p->adj_vertex].data); break; case DN: printf("< %s ->", G.vertexs_vectors[i].data); printf(" %s , %d >\n", G.vertexs_vectors[p->adj_vertex].data, p->weight); break; case UDG: printf("( %s --", G.vertexs_vectors[i].data); printf(" %s )\n", G.vertexs_vectors[p->adj_vertex].data); break; case UDN: printf("( %s --", G.vertexs_vectors[i].data); printf(" %s , %d )\n", G.vertexs_vectors[p->adj_vertex].data, p->weight); break; default: exit(0); } p = p->next_arc; } } } int First_Adj_Vertex( ALGraph G, int v ) { Arc_Node *p = G.vertexs_vectors[v].first_arc; if( !p ) return -1; else return Get_Vertex_Location( G, G.vertexs_vectors[p->adj_vertex].data); } int Next_Adj_Vertex( ALGraph G, int v, int w ) { Arc_Node *p = G.vertexs_vectors[v].first_arc; while( p ) { if( p->adj_vertex == w ) break; p = p->next_arc; } if( !p ) exit(0);//因为正常情况下w是一定可以找到的 p = p->next_arc; if( p ) return p->adj_vertex; else return -1; } void DFS( ALGraph G, int v ) { visited[v] = 1; printf("%s ", G.vertexs_vectors[v].data); for( int w=First_Adj_Vertex( G, v); w>=0; w=Next_Adj_Vertex( G, v, w ) ) if( !visited[w] ) DFS( G, w ); } void DFS_Traverse( ALGraph G ) { for( int v=0; v<G.vertex_num; ++v ) visited[v] = 0;// 表示没有被访问过 printf("DFS图的遍历序列:"); for( v=0; v<G.vertex_num; ++v ) if( !visited[v] ) DFS( G, v ); printf("\n"); } int main() { ALGraph G; Create_ALGraph( G ); Print_ALGraph( G ); DFS_Traverse( G ); return 0; } |
一、实验项目
名称：图的建立、基本操作以及遍历 课时：4学时
二、实验要求
1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围；
2、熟练掌握几种常见图的遍历方法及遍历算法；
三、实验环境
Widows操作系统、VC6.0
四、实验内容
选用任一种图的存储结构，建立如下图所示的带权有向图：
只有本站会员才能查看附件，请 登录
要求：1、建立边的条数为零的图；
2、依次将图的边以及相应的权值插入，建立如上图所示的图，并将结点集合和权值集合输出；
3、对所建立的图进行深度优先搜索或广度优先搜索，输出图的遍历序列；
算法思想：
首先，选定所使用的图的存储结构（邻接矩阵存储或邻接表存储），建立图的结构体定义。根据所选用的结构建立边条数为零的图，依次插入图的结点和图的各有向边以及权值weight；再次，将图的结点集合以及权值集合输出，以验证所建立图的正确性；最后，调用图的遍历函数，实现图的深度优先遍历或广度优先遍历，并输出遍历序列。