数据结构图的基本操作及遍历
邻接表的存储结构遍历请看http://www.omegaxyz.com/2017/05/16/graphofds/
实验目的：
编写程序，建立该图的邻接矩阵存储。
基于上面所建立的存储结构，编程实现深度优先和广度优先搜索算法。
头文件
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ typedef char VertexType; /* 顶点类型应由用户定义 */ typedef int EdgeType; /* 边上的权值类型应由用户定义 */ #define MAXSIZE 9 /* 存储空间初始分配量 */ #define MAXEDGE 15 #define MAXVEX 9 #define INFINITY 65535 typedef struct { VertexType vexs[MAXVEX]; /* 顶点表 */ EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */ int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ }MGraph; |
文中使用到的队列请使用C++ <queue>头文件或自己写
函数
①图的构建
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
void CreateMGraph(MGraph *G) { int i, j; G->numEdges=12; G->numVertexes=9; G->vexs[0]='0'; G->vexs[1]='1'; G->vexs[2]='2'; G->vexs[3]='3'; G->vexs[4]='4'; G->vexs[5]='5'; G->vexs[6]='6'; G->vexs[7]='7'; G->vexs[8]='8'; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < G->numVertexes; j++) { G->arc[i][j]=0; } } G->arc[0][2]=1; G->arc[1][3]=1; G->arc[1][4]=1; G->arc[2][4]=1; G->arc[2][5]=1; G->arc[3][6]=1; G->arc[3][7]=1; G->arc[4][7]=1; G->arc[4][8]=1; G->arc[5][7]=1; G->arc[6][7]=1; G->arc[7][8]=1; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } Boolean visited[MAXVEX]; //访问标志的数组 |
②DFS遍历
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
void DFS(MGraph G, int i) { int j; visited[i] = TRUE; printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */ for(j = 0; j < G.numVertexes; j++) if(G.arc[i][j] == 1 && !visited[j]) DFS(G, j);/* 对为访问的邻接顶点递归调用 */ } /* 邻接矩阵的深度遍历操作 */ void DFSTraverse(MGraph G) { int i; for(i = 0; i < G.numVertexes; i++) visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */ for(i = 0; i < G.numVertexes; i++) if(!visited[i]) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */ DFS(G, i); } |
③BFS遍历
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
void BFSTraverse(ALGraph G,VertexType x) { struct { ArcNode *Q[Maxsize]; int front,rear; }Que; Que.front=Que.rear; int k,i; k=LocateX(G,x); visited[k]=1; printf("%d /",G.vertices[k].data); Que.rear=(Que.rear+1)%Maxsize; Que.Q[Que.rear]=G.vertices[k].firstarc; ArcNode *p; while(Que.rear!=Que.front) { Que.front=(Que.front+1)%Maxsize; p=Que.Q[Que.front]; while(p) { if(visited[p->adjvex]==0) { visited[p->adjvex]=1; printf("%d /",G.vertices[p->adjvex].data); Que.rear=(Que.rear+1)%Maxsize; Que.Q[Que.rear]=G.vertices[p->adjvex].firstarc; } p=p->nextarc; } } } |
MAIN函数
|
1 2 3 4 5 6 7 8 9 10 11 |
int main(void) { MGraph G; printf("--------------徐奕 软件工程 E21614061--------------------\n"); CreateMGraph(&G); printf("\n深度遍历序列为："); DFSTraverse(G); printf("\n广度遍历序列为："); BFSTraverse(G); return 0; } |
