1.广度优先搜索
1.1.广度优先搜索的概念
广度优先搜索(Breadth-First-Search, BFS)，类似二叉树层次遍历。以v为起点，依次访问和v有路径相同且路径长度为1，2，……的顶点
#define MaxVertexNum 100 bool visited[MaxVertexNum]; //标记是否访问过 void BTS(Graph G, int v){ //从顶点v出发 Queue Q; initQueue(Q); visit(v); //访问v visited[v] = true; //visited数组中下标v的元素改为true EnQueue(Q, v); //v入队 while(!IsEmpty(Q)){ DeQueue(Q, v); //取出队头元素 int w; for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){ //检测所有v的邻接点 if (!visit[w]){ //w当前未访问过 visit(w); //访问w visit[w] = true; //visited数组中下标w的元素改为true EnQueue(Q, w); //将w入队 }//if }//for }//while }
非连通图或非强连通图，在执行完BTS后，可能还会有剩余的顶点没有访问到，因此，要重新调用BTS函数继续进行遍历
bool visited[MaxVertexNum]; void BTS(Graph G, int v){ visit(v); visited[v] = true; Queue Q; InitQueue(Q); EnQueue(Q, v); while(!IsEmpty(Q)){ DeQueue(Q, v); int w; for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){ if (!visited[w]){ visit(w); visited[w] = true; EnQueue(Q, W); }//if }//for }//while } void BTS_G(Graph G){ for (int i = 0; i < G.verNum; i++) visited[i] = false; //初始化visited数组 //当前visited数组下标i的元素为false，调用BTS函数 for (int i = 0; i < G.verNum; i++) if (!visited[i]) BTS(G, i); }
1.2.广度优先搜索的可变性
邻接矩阵唯一→广度优先遍历序列唯一
邻接表不唯一→广度优先遍历序列不唯一
1.3.广度优先搜索性能
空间复杂度：图中每个顶点都需要入队一次，最坏情况下是O(|V|)
时间复杂度：分为访问各顶点的时间和探索各条边的时间
- 邻接矩阵，访问V个结点，需要O(|V|)，查找需遍历V行（顶点数），每行V个顶点，需要O(|
|)，故时间复杂度为O(|
|) - 邻接表，访问V个结点，需要O(|V|)，查找E个边，需要O(|E|)，故时间复杂度为O(|V|+|E|)
2.深度优先搜索
2.1.深度优先搜索的概念
首先访问起点v，然后访问与之邻接且未被访问的顶点w，再访问与w邻接且未被访问的顶点u，直到不能再继续向下访问时，依次退回到最近被访问的顶点，如果还有邻接且未被访问的顶点，则访问那个顶点，循环这个过程，直至图中所有顶点都被访问过
bool visited[MaxVertexNum]; void DFS(Graph G, int v){ visit(v); visited[v] = true; int w; for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) DFS(G, w); } void DFS_G(Graph G){ for (int i = 0; i < G.verNum; i++) visit[i] = false; for (int i = 0; i < G.verNum; i++) if (!visit[i]) DFS(G, i); }
2.2.深度优先搜索的性能
空间复杂度：最好O(1)：中间一点连着其他顶点，栈仅需一个空间；最坏O(|V|)：一条线，需要全部依次压入栈中
时间复杂度：
- 邻接矩阵 O(|
|) - 邻接表O(|V|+|E|)
3.图的遍历和图的连通性
无向图：DFS/BFS函数调用次数 = 连通分量数
有向图：起始顶点到其他顶点都有路径，则仅需一次；强连通图从任意一个顶点出发，都仅需一次
4.王道课后题
无向图是树→连通图且没有回路 || 有 n - 1 条边的连通图
//广度搜索，对应连通图且没有回路 bool visited[MaxVertexNum]; bool IsTree(ALGraph G) { //初始化visited数组 for (int i = 0; i < MaxVertexNum; i++) visited[i] = false; Queue Q; InitQueue(Q); //寻找图中的第一个数据 int p; for (p = 0; p < MaxVertexNum; p++) if (G.vertices[p].data) break; int temp = p; int count = 0; //标记访问了多少个顶点 //将p入队 EnQueue(Q, p); while (!IsEmpty(Q)) { //出队队头元素 DeQueue(Q, p); //当前顶点p未扫描过，则进入标记扫描，并且找到所有与它邻接的顶点，并依次入队 if (!visited[p]) { visited[p] = true; count++; for (int q = FirstNeighbor(G, p); q >= 0; q = NextNeighbor(G, p, q)){ EnQueue(Q, q); } } //扫描过p，存在回路 else return false; } //访问顶点个数不等于顶点总数，非连通图 if (count != G.verNum) return false; else return true; }
//DFS，对应有 n - 1 条边的连通图 bool visited[MaxVertexNum]; bool IsTree(ALGraph G) { //初始化visited数组为false for (int i = 0; i < G.verNum; i++) visited[i] = false; //vCount记录遍历顶点数，eCount记录遍历边数 int vCount = 0, eCount = 0; //遍历G中的每个顶点 for (int i = 0; i < G.verNum; i++) { if (!visited[i]) DFS(G, vCount, eCount, i); } //满足条件顶点数=已遍历顶点数，并且边数为n - 1 //无向图的存储中每条边存储两次 if (vCount == G.verNum && 2 * eCount + 2 == G.arcNum) return true; else return false; } void DFS(ALGraph G, int& vCount, int& eCount, int v) { if (!visited[v]) { visited[v] = true; //访问顶点数+1 vCount++; } for (int w = FistNeighbor; w >= ; w = NextNeighbor) { //访问边数+1 eCount++; DFS(G, vCount, eCount, w); } }
#define MaxVertexNum 100 typedef struct ArcNode{ struct ArcNode *next; int adjVertex; }ArcNode; typedef struct VNode{ ArcNode *next; elemtype data; }VNode, adjList[MaxVertexNum]; typedef struct{ adjList vertices; int verNum, arcNum; }ALGraph; typedef struct Stack{ int top; elemtype data[MaxVertexNum]; }Stack; bool visited[MaxVertexNum]; void DFS(ALGraph G, int v){ //初始化visited数组 for (int i = 0; i < MaxVertexNum; i++) visited[i] = false; Stack S; InitStack(S); int i, j; //访问v，并将v压入栈中 visited[v] = true; push(S, v); //循环直到栈空 while(!IsEmpty(S)){ //弹出栈顶元素 pop(S, i); //访问i所有的邻接结点 for (j = FirstNeighbor(G, i); j >= 0; j = NextNeighbor(G, i, j)){ //将j压入栈中 if (!visited[j]) { visited[j] = true; push(S, j); } }//for }//while }
//广度搜索 #define MaxVertexNum 100 typedef struct ArcNode{ struct ArcNode *next; int adjVertex; }ArcNode; typedef struct VNode{ ArcNode *first; elemtype data; }VNode, AdjList[MaxVertexNum]; typedef struct ALGraph{ AdjList vertices; int verNum, arcNum; }ALGraph; typedef struct Queue{ elemtype data[MaxVertexNum]; int rear, front; }Queue; bool visited[MaxVertexNum]; bool BFS_iToj(Graph G, int i, int j){ for (int i = 0; i < G.verNum; i++) visited[i] = false; Queue Q; InitQueue; EnQueue(Q, i); int w, v; while (!IsEmpty(Q)){ DeQueue(Q, v); if (!visited[v]) { //v == j， ij存在路径，返回true if (j == v) return true; visited[v] = true; for (w = FistNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){ if (!visited[w]) EnQueue(Q, w); } }//if }//while //ij没有路径，返回false return false; }
//深度搜索 #define MaxVertexNum 100 typedef struct ArcNode{ struct ArcNode *next; int adjVertex; }ArcNode; typedef struct VNode{ ArcNode *first; elemtype data; }VNode, AdjList[MaxVertexNum]; typedef struct ALGraph{ int verNum, arcNum; AdjList vertices; }ALGraph; typedef struct Stack{ elmetpye data[MaxVertexNum]; int top; }Stack; bool visited[MaxVertexNum]; bool DFS_iToj(ALGraph G, int i, int j){ Stack S; InitStack(S); for (int temp = 0; temp < G.verNum; temp++) visited[temp] = false; push(S, i); visited[i] = 0; int v, w; while (!IsEmpty(S)){ pop(S, v); for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){ //w == j, ij存在路径，返回true if (w == j) return true; if (!visited[w]) { visited[w] = true; push(S, w); } }//for }//while return false; }
