从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

• 深度优先遍历（Depth_First_Search）
  从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这是连通图的情况，如果是非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
  如果我们用的是邻接矩阵的方式，则代码如下：
  

   1 typedef bool Boolean; // Boolean是布尔类型，其值是TRUE或FALSE
   2 Boolean visited[MAX]; // 访问标志的数组
   3 // 邻接矩阵的深度优先递归算法
   4 void DFS(MGraph G, int i) {
   5     visited[i] = TRUE;
   6     printf("%c ", G.vexs[i]); // 打印顶点，也可以其他操作
   7     for (int j = 1; j < G.numVertexes; j++)
   8         if (G.arc[i][j] == 1 && !visited[j])
   9             DFS(G, j); // 对未访问的邻接顶点递归调用
  10 }
  11 // 邻接矩阵的深度遍历操作
  12 void DFSTraverse(MGraph G) {
  13     for (int i = 0; i < G.numVertexes; i++)
  14         visited[i] = FALSE; // 初始所有顶点状态都是未访问过状态
  15     for (int i = 0; i < G.numVertexes; i++)
  16         if (!visited[i]) // 对未访问过的顶点调用DFS，若是连通图，只会执行一次
  17             DFS(G, i);
  18 }

   如果图结构是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有所不同。代码如下：

   1 // 邻接表的深度优先递归算法
   2 void DFS(GraphAdjList GL, int i) {
   3     EdgeNode *p;
   4     visited[i] = TRUE;
   5     printf("%c ", GL->adjList[i].data); // 打印顶点，也可以其他操作
   6     p = GL->adjList[i].firstedge;
   7     while (p) {
   8         if (!visited[p->adjvex])
   9             DFS(GL, p->adjvex);
  10         p = p->next;
  11     }
  12 }
  13 // 邻接表的深度遍历操作
  14 void DFSTraverse(GraphAdjList GL) {
  15     for (int i = 1; i < GL->numVertexes; i++)
  16         visited[i] = FALSE; // 初始所有顶点状态都是未访问过状态
  17     for (int i = 1; i < GL->numVertexes; i++)
  18         if (!visited[i]) // 对未访问过的顶点调用DFS
  19             DFS(GL, i);
  20 }

• 广度优先遍历（Breadth_First_Search）
  邻接矩阵结构的广度优先遍历算法代码如下：
  

   1 void BFSTraverse(MGraph G) {
   2     Queue Q;
   3     for (int i = 0; i < G.numVertexes; i++)
   4         visited[i] = FALSE;
   5     InitQueue(&Q); // 初始化一辅助用的队列
   6     for (int i = 0; i < G.numVertexes; i++) { // 对每一个顶点loop
   7         if (!visited[i]) { // 若是未访问过就处理
   8             visited[i] = TRUE; // 设置当前顶点访问过
   9             printf("%c ", G.vexs[i]); // 打印顶点，也可以其他操作
  10             EnQueue(&Q, i); // 将此顶点入队
  11             while (!QueueEmpty(Q)) { // 若当前队列不为空
  12                 DeQueue(&Q, &i); // 将队中元素出队，赋值给i
  13                 for (int j = 0; j < G.numVertexes; j++) {
  14                     // 判断其他顶点若与当前顶点存在边且未访问过
  15                     if (G.arc[i][j] == 1 && !visited[j]) {
  16                         visited[j] = TRUE; // 将找到的此顶点标记为已访问
  17                         printf("%c ", G.vexs[j]); // 打印顶点
  18                         EnQueue(&Q, j); // 将找到的此顶点入队
  19                     }
  20                 }
  21             }
  22         }
  23     }
  24 }

  邻接表的广度优先遍历的代码的邻接矩阵差距不大。代码如下：

   1 void BFSTraverse(GraphAdjList GL) {
   2     EdgeNode *p;
   3     Queue Q;
   4     for (int i = 0; i < GL->numVertexes; i++)
   5         visited[i] = FALSE;
   6     InitQueue(&Q);
   7     for (int i = 0; i < GL->numVertexes; i++) {
   8         if (!visited[i]) {
   9             visited[i] = TRUE;
  10             printf("%c ", GL->adjList[i].data); // 打印顶点，也可以其他操作
  11             EnQueue(&Q, i);
  12             while (!QueueEmpty(Q)) {
  13                 DeQueue(&Q, &i);
  14                 p = GL->adjList[i].firstedge; // 找到当前顶点边表链表头指针
  15                 while (p) {
  16                     if (!visited[p->adjvex]) { // 若此顶点未被访问
  17                         visited[p->adjvex] = TRUE;
  18                         printf("%c ", GL->adjList[p->adjvex].data);
  19                         Enqueue(&Q, p->adjvex); // 将此顶点入队
  20                     }
  21                     p = p->next; // 指针指向下一个邻接点
  22                 }
  23             }
  24         }
  25     }
  26 }