和树的遍历类似，我们希望从图中某一顶点出发访遍图中所有的顶点，且每个顶点只被访问一次，这一过程就叫“图的遍历”。图的遍历算法是求解图的连通性问题，拓扑排序和求关键路径等算法的基础。
因为图的任一顶点都可能和其余的顶点连接，所以在访问了某个顶点之后，可能沿着某条路径搜索后又回到了该顶点。为了避免同一顶点被多次访问，可以设一个辅助数组visited[1…n]，初始值设为false，在遍历图的过程中，一旦访问了顶点vi，就置visited[i]为true。
通常有两条遍历图的路径：深度优先搜索和广度优先搜索。他们对无向图和有向图都适用。
一、 深度优先搜索（DFS—depth_first search）
深度优先搜索遍历类似于树的先根遍历，树树的先根遍历的推广。
它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。
如上图所示，从顶点v1出发进行搜索，在访问了顶点v1后，选择邻接点v2，因为v1没被访问过，所以从v2出发进行搜索，以此类推，接着从v4、v8、v5出发进行搜索，在访问了v5之后，由于v5的邻接点都以被访问，则搜索回到v8，由于同样的理由，搜索继续回到v4、v2直到v1，此时由于v1的另一个邻接点未被访问，则搜索又从v1到v3再继续进行下去，由此得到的顶点访问顺序为v1 → v2 → v4 → v8 → v5 → v3 → v6 → v7
这显然是一个递归过程，算法如下：
1、 使用邻接矩阵
图的结构定义：
typedef struct {
char vexs[n]; //存储顶点信息
int arc[n][n]; //邻接矩阵，可看作边
int numVertexes, numEdges; //图中当前的顶点数和边数
} Graph;
邻接矩阵的深度优先递归算法
void DFS(Graph g, int i) {
int j;
visited[i] = TRUE;
for(j = 0; j < g.numVertexes; j++) {
if(g.arc[i][j] == 1 && !visited[j]) {
//对未访问的邻接顶点递归调用
DFS(g, j);
}
}
}
2、 使用邻接表
图的结构定义：
typedef struct EdgeNode { //表结点结构
int adjvex; //邻接点域，存储该顶点对应的下标
int weigth; //用于存储权值，对于非网图可以不需要
struct EdgeNode *next; //链域，指向下一个邻接点
} EdgeNode;
typedef struct VertexNode { //头结点结构
char data; //数据域，存储头结点信息
EdgeNode *firstedge; //指向与该头结点相连的第一个结点的指针
} VertexNode, AdjList[n];
typedef struct {
AdjList adjList;
int numVertexes, numEdges; //图中当前顶点数和边数
} GraphList;
邻接表的深度递归算法
void DFS(GraphList g, int i) {
EdgeNode *p;
visited[i] = TRUE;
p = g->adjList[i].firstedge;
while(p) {
if(!visited[p->adjvex]) {
//对访问的邻接顶点递归调用
DFS(g, p->adjvex);
}
p = p->next;
}
}
对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
二、广度优先搜索（BFS—breadth_first search）
广度优先搜索遍历类似于树的按层次遍历的过程。
假设从图中某顶点广度优先搜v0出发，在访问了v0之后，依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发广度优先搜索遍历图，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点，重复上述过程，直至图中所有顶点都被访问到为止。也就是说，广度优先搜索遍历图的过程是以v0为起点，由近至远，依次访问和v0有路径相同且路径长度为1、2…的顶点。
如上图，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5已经v3的邻接点v6和v7，最后访问v4的邻接点v8。至此所有顶点均访问完成。得到的顶点访问顺序为v1 → v2 → v3 → v4 → v5 → v6 → v7 → v8
和深度优先搜索类似，在遍历过程中也要一个访问标志数组。并且，为了顺次访问路径长度为2、3…的顶点，需附设队列以存储已被访问的路径长度为1、2…的顶点。
算法如下：
1、 使用邻接矩阵
void BFSTraverse(Graph g) {
//从顶点v出发，广度优先遍历图g
//借助一个辅助队列q，用于存储已被访问的路径长度
Queue q;
for(i = 0; i < g.numVertexes; i++) {//对每个顶点做循环
if(!visited[i]) { //若是未访问过
visited[i] = TRUE;
EnQueue(q, i); //将此结点入队列
while(!QueueEmpty(q)) { //将队中元素出队列，赋值给m
DeQueue(q, m);
for(j = 0; j < g.numVertexes; j++) {
//判断其他顶点若与当前顶点存在边且未访问过
if(g.arc[m][j] == 1 && !visited[j]) {
visited[j] = TRUE;
EnQueue(&q, j);
}
}
}
}
}
}
2、 使用邻接表
void BFSTraverse(GraphList g) {
for(i = 0; i < g.numVertexes; i++) {
if(!visited[i]) {
visited[i] = TRUE;
EnQueue(q, i);
while(!QueueEmpty(q)) {
DeQueue(q, m);
//找到与当前顶点相连的第一个结点的指针
p = g.adjList[m].firstedge;
while(p) {
if(!visited[p->adjvex]) {
visited[p->adjvex] = TRUE;
EnQueue(q, p->adjvex);
}
p = p->next;
}
}
}
}
}
广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，不同之处仅仅在于对顶点的访问顺序不同。
