写在前面
**图的存储结构有两种：**一种是基于二维数组的邻接矩阵表示法。
另一种是基于链表的的邻接表表示法。
在邻接矩阵中，可以如下表示顶点和边连接关系：
说明：
将顶点对应为下标，根据横纵坐标将矩阵中的某一位置值设为1，表示两个顶点向联接。
图示表示的是无向图的邻接矩阵，从中我们可以发现它们的分布关于斜对角线对称。
我们在下面将要讨论的是下图的两种遍历方法（基于矩阵的）：
我们已经说明了我们要用到的是邻接矩阵表示法，那么我首先要来构造图：
1.深度优先遍历算法
分析深度优先遍历
从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。
深度优先搜索的思想：
①访问顶点v；
②依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
③若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
比如：
在这里为了区分已经访问过的节点和没有访问过的节点，我们引入一个一维数组bool visited[MaxVnum]用来表示与下标对应的顶点是否被访问过，
流程：
☐ 首先输出 V1，标记V1的flag=true;
☐ 获得V1的邻接边 [V2 V3],取出V2，标记V2的flag=true;
☐ 获得V2的邻接边[V1 V4 V5],过滤掉已经flag的，取出V4，标记V4的flag=true;
☐ 获得V4的邻接边[V2 V8],过滤掉已经flag的，取出V8，标记V8的flag=true;
☐ 获得V8的邻接边[V4 V5],过滤掉已经flag的，取出V5，标记V5的flag=true;
☐ 此时发现V5的所有邻接边都已经被flag了，所以需要回溯。（左边黑色虚线，回溯到V1，回溯就是下层递归结束往回返）
☐
☐ 回溯到V1，在前面取出的是V2，现在取出V3，标记V3的flag=true;
☐ 获得V3的邻接边[V1 V6 V7]，过滤掉已经flag的,取出V6，标记V6的flag=true;
☐ 获得V6的邻接边[V3 V7],过滤掉已经flag的,取出V7，标记V7的flag=true;
☐ 此时发现V7的所有邻接边都已经被flag了，所以需要回溯。（右边黑色虚线，回溯到V1，回溯就是下层递归结束往回返）
深度优先搜索的代码
2.广度优先搜索算法
分析广度优先遍历
所谓广度，就是一层一层的，向下遍历，层层堵截，还是这幅图，我们如果要是广度优先遍历的话，我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。
广度优先搜索的思想：
① 访问顶点vi ；
② 访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ；
③ 依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；
说明：
为实现③，需要保存在步骤②中访问的顶点，而且访问这些顶点的邻接点的顺序为：先保存的顶点，其邻接点先被访问。 这里我们就想到了用标准模板库中的queue队列来实现这种先进现出的服务。
老规矩我们还是走一边流程：
说明：
☐将V1加入队列，取出V1，并标记为true(即已经访问)，将其邻接点加进入队列，则 <—[V2 V3]
☐取出V2，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V3 V4 V5]
☐取出V3，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V4 V5 V6 V7]
☐取出V4，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V5 V6 V7 V8]
☐取出V5，并标记为true(即已经访问)，因为其邻接点已经加入队列，则 <—[V6 V7 V8]
☐取出V6，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V7 V8]
☐取出V7，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[V8]
☐取出V8，并标记为true(即已经访问)，将其未访问过的邻接点加进入队列，则 <—[]
两种表示法：
邻接矩阵完整代码：
1#include<stdio.h> 2#include<stdlib.h> 3#include<malloc.h> 4//邻接矩阵 5#define OK 1 6#define ERROR 0 7 8#define MAXNUM 10 9 10typedef int Status; 11typedef char ElemType; 12typedef struct 13{ 14 int vnum; //顶点数 15 int anum; //弧/边数 16 ElemType vex[MAXNUM]; //存储顶点 17 int arc[MAXNUM][MAXNUM]; //存储边关系 18}MGraph; 19 20int Location(MGraph G, ElemType e) 21{ 22 int v; 23 for (v = 0; v<G.vnum; v++) 24 if (G.vex[v] == e)return v; 25 return -1; 26 27} 28 29Status CreateGraph(MGraph &G, int vnum, int anum, ElemType v[], ElemType a[]) //数组生成图 30{ 31 int k; 32 G.vnum = vnum; //获取数组顶点数 33 G.anum = anum; //获取数组边数 34 for (k = 0; k<G.vnum; k++) 35 G.vex[k] = v[k]; 36 for (int i = 0; i<G.vnum; i++) 37 { 38 for (int j = 0; j<G.vnum; j++) 39 G.arc[i][j] = 0; 40 } 41 int t = 0; 42 int p, q; 43 for (k = 0; k<G.anum; k++) 44 { 45 ElemType m, n; 46 m = a[t++]; 47 n = a[t++]; 48 t++; 49 p = Location(G, m); 50 q = Location(G, n); 51 G.arc[p][q] = 1; 52 G.arc[q][p] = 1; 53 } 54 return OK; 55} 56 57void Print(MGraph G) 58{ 59 int v; 60 printf("顶点序列为:\n"); 61 for (v = 0; v<G.vnum; v++) 62 printf("%3c", G.vex[v]); 63 printf("\n"); 64 printf("边的二维数组关系:\n"); 65 for (int i = 0; i<G.vnum; i++) 66 { 67 for (int j = 0; j<G.vnum; j++) 68 printf("%3d", G.arc[i][j]); 69 printf("\n"); 70 } 71 printf("\n"); 72} 73 74int FirstAdjVex(MGraph G, int i) 75{ 76 int v; 77 if (i<0 || i >= G.vnum)return -1; 78 for (v = 0; v<G.vnum; v++) 79 if (G.arc[i][v] == 1)return v; 80 return -1; 81} 82 83int NextAdjVex(MGraph G, int i, int j) 84{ 85 if (i<0 || i >= G.vnum)return -1; 86 if (j<0 || j >= G.vnum)return -1; 87 for (int v = j + 1; v<G.vnum; v++) 88 if (G.arc[i][v] == 1)return v; 89 return -1; 90} 91 92//DFS遍历 93int visited[MAXNUM]; 94void DFS(MGraph G, int v); 95void DFSTraverse(MGraph G) 96{ 97 printf("深度优先遍历为:\n"); 98 int v; 99 for (v = 0; v<G.vnum; v++) 100 visited[v] = 0; 101 for (v = 0; v<G.vnum; v++) 102 { 103 if (visited[v] == 0)DFS(G, v); 104 } 105} 106void DFS(MGraph G, int v) 107{ 108 printf("%3c", G.vex[v]); 109 visited[v] = 1; 110 int w = FirstAdjVex(G, v); 111 while (w != -1) 112 { 113 if (visited[w] == 0)DFS(G, w); 114 w = NextAdjVex(G, v, w); 115 } 116} 117 118//BFS遍历 119typedef struct QNode 120{ 121 ElemType data; 122 struct QNode *next; 123}QNode, *QueuePtr; //定义队列的指针类型为QueuePtr,定义队列结点内存空间类型为QNode 124typedef struct 125{ 126 QueuePtr front; //front为头指针，指向头结点。Q.front->next指针存在头结点的指针域(即其存着首结点的地址)，是头结点的指针，指向首结点 127 QueuePtr rear; 128}LinkQueue; //定义队列结点类型为LinkQueue 129 130Status InitQueue(LinkQueue &Q) 131{ 132 Q.front = (QNode*)malloc(sizeof(QNode)); 133 if (!Q.front)return ERROR; 134 Q.front->next = NULL; 135 Q.rear = Q.front; 136 return OK; 137} 138 139Status EnQueue(LinkQueue &Q, ElemType e) //入队 140{ 141 QueuePtr p; 142 p = (QNode*)malloc(sizeof(QNode)); //生成新结点p 143 if (!p)return ERROR; 144 p->next = NULL; //新结点的指针p->next置空 145 p->data = e; //新结点暂存e 146 Q.rear->next = p; //队尾结点的指针Q.rear->next指向新结点p 147 Q.rear = p; //队尾指针Q.rear指向p 148 return OK; 149} 150 151Status DeQueue(LinkQueue &Q, ElemType &e) //出队 152{ 153 QueuePtr p; 154 if (Q.rear == Q.front) //确保队列有首结点 155 return ERROR; 156 p = Q.front->next; //指针p暂存被删结点(首结点)的地址 157 Q.front->next = p->next; //头结点的指针Q.front->next指向首结点的下一结点 158 e = p->data; 159 if (Q.front->next == Q.rear) //判断原队列是否只有首结点 160 Q.rear = Q.front; 161 free(p);//清空 162 return OK; 163} 164 165bool EmptyQueue(LinkQueue Q) //判空 166{ 167 if (Q.front == Q.rear)return true; 168 else return false; 169} 170 171void BFS(MGraph G) 172{ 173 printf("广度优先遍历为:\n"); 174 int v; 175 LinkQueue Q; 176 InitQueue(Q); 177 for (v = 0; v<G.vnum; v++) //初始化 178 visited[v] = 0; 179 for (v = 0; v<G.vnum; v++) 180 { 181 if (visited[v] == 1)continue; 182 printf("%3c", G.vex[v]); 183 visited[v] = 1; 184 EnQueue(Q, G.vex[v]); 185 while (EmptyQueue == 0) 186 { 187 int v; 188 ElemType e; 189 DeQueue(Q, e); 190 v = Location(G, e); 191 int w = FirstAdjVex(G, v); 192 while (w != -1) 193 { 194 w = NextAdjVex(G, v, w); 195 if (visited[w] = 1)continue; 196 printf("%3c", G.vex[w]); 197 EnQueue(Q, G.vex[w]); 198 visited[w] = 1; 199 } 200 } 201 } 202} 203 204 205int main() 206{ 207 MGraph G; 208 ElemType v[] = "abcdef"; //顶点数组 209 ElemType a[] = "ab,ac,ad,be,ce,df"; //边数组 210 CreateGraph(G, 6, 6, v, a); 211 Print(G); 212 DFSTraverse(G); 213 printf("\n"); 214 BFS(G); 215 printf("\n"); 216 system("pause"); 217 return 0; 218}//
View Code
邻接表完整代码：
1#include<stdio.h> 2#include<malloc.h> 3 4#define OK 1 5#define ERROR 0 6 7#define MAXNUM 10 8 9typedef int Status; 10typedef char ElemType; 11typedef struct ANode 12{ 13 int adjvex; //邻接点域 14 struct ANode *next; //邻接点指针域 15}ANode; //ANode为单链表的指针类型 16typedef struct 17{ 18 ElemType data; 19 ANode *firstarc; //定义单链表的头指针为firstarc 20}VNode; //VNode为顶点数组元素的类型 21typedef struct 22{ 23 int vnum,anum; //顶点数，边数 24 VNode vex[MAXNUM]; //顶点集 25}ALGraph; //ALGraph邻接表类型 26 27int Location(ALGraph G, ElemType e) 28{ 29 int v; 30 for (v = 0; v<G.vnum; v++) 31 if (G.vex[v].data == e)return v; 32 return -1; 33} 34 35Status CreatGraph(ALGraph &G, int vnum, int anum, ElemType v[], ElemType a[]) 36{ 37 int k, t = 0; 38 G.vnum = vnum; 39 G.anum = anum; 40 for (k = 0; k<G.vnum; k++) 41 { 42 G.vex[k].data = v[k]; 43 G.vex[k].firstarc = NULL;//易忘记 44 } 45 for (k = 0; k<G.anum; k++) 46 { 47 ElemType m, n; 48 ANode *p1, *p2, *p3; 49 int p, q; 50 m = a[t++]; 51 n = a[t++]; 52 t++; 53 p = Location(G, m); 54 q = Location(G, n); 55 p1 = (ANode*)malloc(sizeof(ANode)); 56 if (p1 == NULL)return ERROR; 57 p1->adjvex = q; 58 p1->next = NULL; 59 if (G.vex[p].firstarc == NULL) 60 G.vex[p].firstarc = p1; 61 else 62 { 63 p3 = G.vex[p].firstarc; 64 while (p3->next) 65 p3 = p3->next; 66 p3->next = p1; 67 } 68 p2 = (ANode*)malloc(sizeof(ANode)); 69 if (!p2)return ERROR; 70 p2->adjvex = p; 71 p2->next = NULL; 72 if (G.vex[q].firstarc == NULL) 73 G.vex[q].firstarc = p2; 74 else 75 { 76 p3 = G.vex[p].firstarc; 77 while (p3->next) 78 p3 = p3->next; 79 p3->next = p2; 80 } 81 82 } 83 return OK; 84} 85 86int FirstAdjVex(ALGraph G, int v) 87{ 88 if (v<0 || v >= G.vnum)return -1; 89 if (G.vex[v].firstarc != NULL) 90 return G.vex[v].firstarc->adjvex; 91 return -1; 92} 93 94int NextAdjVex(ALGraph G, int v, int w) 95{ 96 ANode *p; 97 p = G.vex[v].firstarc; 98 if (v<0 || v >= G.vnum)return -1; 99 if (w<0 || w >= G.vnum)return -1; 100 while (p&&p->adjvex != w) 101 p = p->next; 102 if (p ！= NULL || p->next ！= NULL) 103 return p->next->adjvex; 104 return -1; 105} 106 107//DFS 108int visited[MAXNUM]; 109void DFS(ALGraph G, int v); 110void DFSTraverse(ALGraph G) 111{ 112 printf("深度遍历为:\n"); 113 int v; 114 for (v = 0; v<G.vnum; v++) 115 visited[v] = 0; 116 for (v = 0; v<G.vnum; v++) 117 if (visited[v] == 0)DFS(G, v); 118 printf("\n"); 119} 120void DFS(ALGraph G, int v) 121{ 122 int w; 123 printf("%3c", G.vex[v].data); 124 visited[v] = 1; 125 w = FirstAdjVex(G, v); 126 while (w != -1) 127 { 128 if (visited[w] == 0)DFS(G, w); 129 w = NextAdjVex(G, v, w); 130 } 131 132} 133 134//BFS遍历-链队列 135typedef struct QNode 136{ 137 ElemType data; 138 struct QNode *next; 139}QNode, *QueuePtr; 140typedef struct 141{ 142 QueuePtr front; 143 QueuePtr rear; 144}LinkQueue; 145 146Status InitQueue(LinkQueue &Q) 147{ 148 Q.front = (QNode*)malloc(sizeof(QNode)); 149 if (!Q.front)return ERROR; 150 Q.front->next = NULL; 151 Q.rear = Q.front; 152 return OK; 153} 154//入队 155Status EnQueue(LinkQueue &Q, ElemType e) 156{ 157 QueuePtr p; 158 p = (QNode*)malloc(sizeof(QNode)); 159 if (!p)return ERROR; 160 p->next = NULL; 161 p->data = e; 162 Q.rear->next = p; 163 Q.rear = p; 164 return OK; 165} 166 167//出队 168Status DeQueue(LinkQueue &Q, ElemType &e) 169{ 170 QueuePtr p; 171 if (Q.rear == Q.front) 172 return ERROR; 173 p = Q.front->next; 174 Q.front->next = p->next; 175 if (Q.front->next == Q.rear) 176 Q.rear = Q.front; 177 e = p->data; 178 free(p);//清空 179 return OK; 180} 181 182//判空 183bool EmptyQueue(LinkQueue Q) 184{ 185 if (Q.front == Q.rear)return true; 186 else return false; 187} 188 189//BFS 190void BFS(ALGraph G) 191{ 192 printf("广度优先遍历为:\n"); 193 int v; 194 LinkQueue Q; 195 InitQueue(Q); 196 for (v = 0; v<G.vnum; v++)//初始化 197 visited[v] = 0; 198 for (v = 0; v<G.vnum; v++) 199 { 200 if (visited[v] == 1)continue; 201 printf("%3c", G.vex[v].data); 202 visited[v] = 1; 203 EnQueue(Q, G.vex[v].data); 204 while (EmptyQueue == 0) 205 { 206 int v; 207 ElemType e; 208 DeQueue(Q, e); 209 v = Location(G, e); 210 int w = FirstAdjVex(G, v); 211 while (w != -1) 212 { 213 w = NextAdjVex(G, v, w); 214 if (visited[w] = 1)continue; 215 printf("%3c", G.vex[w].data); 216 EnQueue(Q, G.vex[w].data); 217 visited[w] = 1; 218 } 219 } 220 } 221} 222 223int main() 224{ 225 ALGraph G; 226 ElemType v[] = "abcdef"; 227 ElemType a[] = "ab,ac,ad,be,ce,df"; 228 CreatGraph(G, 6, 6, v, a); 229 DFSTraverse(G); 230 BFS(G); 231 getchar(); 232 return 0; 233}
View Code