有向图深度和广度优先遍历问题（基本概念，别笑我）
举个最简单的有向图
b -> a -> c
设a是第一个顶点，这样的有向图从a只能走到c，不可能走到b，那么从a进行遍历，b是否应该遍历到？
我开始一直不太明白严蔚敏书上深度广度优先遍历最外层的那个循环是干吗的，现在明白加上外层的循环就可以处理这种从第一顶点无法到达的顶点，但这样就很奇怪，路径是断的，b相当于凭空冒出来
以下是根据严蔚敏书上逻辑写的代码
#include <stdio.h>#include <stdint.h>#include <stack>#include <queue>using namespace std;#define MAX_NODE 26typedef int InfoType;typedef int ElemType;typedef int VRType;typedef char VertexType;typedef enum{ DG = 0, DN, UDG, UDN}GraphKind;typedef struct ArcCell{ VRType adj; InfoType *info;}ArcCell, AdjMatrix[MAX_NODE][MAX_NODE];typedef struct{ VertexType vexs[MAX_NODE]; AdjMatrix arcs; int vexnum; int arcnum; GraphKind kind;}MGraph;void BuildUDG(MGraph *G){ int i = 0, j = 0, k = 0; char c = 'a'; int n1[] = {0, 0, 1, 1, 2, 2, 3, 4, 5}; int n2[] = {1, 2, 3 ,4, 5, 6, 7, 7, 6}; if (!G) return; G->vexnum = 8; G->arcnum = 9; G->kind = UDG; for (i=0; i<G->vexnum; ++i) G->vexs[i] = c++; for (i=0; i<G->vexnum; ++i) { for (j=0; j<G->vexnum; ++j) { G->arcs[i][j].adj = 0; G->arcs[i][j].info = NULL; } } for (k=0; k<G->arcnum; ++k) { G->arcs[n1[k]][n2[k]].adj = 1; G->arcs[n2[k]][n1[k]].adj = G->arcs[n1[k]][n2[k]].adj; }}static unsigned char visited[MAX_NODE] = {0};int NextAdjVex(MGraph *G, int v, int w){ int i = 0; if (!G || v < 0) return -1; for (i=++w; i<G->vexnum; ++i) if (G->arcs[v][i].adj != 0 && G->arcs[v][i].adj != INT32_MAX) return i; return -1;}void DFS(MGraph *G, int v){ int i = 0; if (!G) return; visited[v] = 1; printf("%c ", G->vexs[v]); for (i=NextAdjVex(G, v, -1); i>=0; i=NextAdjVex(G, v, i)) { if (!visited[i]) DFS(G, i); }}void DFSRecursion(MGraph *G){ int i = 0; if (!G) return; for (i=0; i<G->vexnum; ++i) visited[i] = 0; for (i=0; i<G->vexnum; ++i) { if (!visited[i]) DFS(G, i); } printf("\n");}void DFSStack(MGraph *G){ int i = 0, j = 0, k = 0; stack<int> s; if (!G) return; for (i=0; i<G->vexnum; ++i) visited[i] = 0; for (i=0; i<G->vexnum; ++i) { if (!visited[i]) { visited[i] = 1; printf("%c ", G->vexs[i]); s.push(i); while (!s.empty()) { j = s.top(); s.pop(); for (k=NextAdjVex(G, j, -1); k>=0; k=NextAdjVex(G, j, k)) { if (!visited[k]) { visited[k] = 1; printf("%c ", G->vexs[k]); s.push(k); j = k; } } } } } printf("\n");}void BFSQueue(MGraph *G){ int i = 0, j = 0, k = 0; queue<int> s; if (!G) return; for (i=0; i<G->vexnum; ++i) visited[i] = 0; for (i=0; i<G->vexnum; ++i) { if (!visited[i]) { visited[i] = 1; printf("%c ", G->vexs[i]); s.push(i); while (!s.empty()) { j = s.front(); s.pop(); for (k=NextAdjVex(G, j, -1); k>=0; k=NextAdjVex(G, j, k)) { if (!visited[k]) { visited[k] = 1; printf("%c ", G->vexs[k]); s.push(k); } } } } } printf("\n");}int main(){ MGraph G = {0}; BuildUDG(&G); DFSRecursion(&G); DFSStack(&G); BFSQueue(&G); getchar();}