[em2]

void DFS(MGraph G) //深搜索    
{
 int i, j;
    void DFS1( MGraph G, int i);//函数声明

 for (i = 0 ; i < G.vexnum; i++)
 {
  visit[i] = FALSE;
 }
 for (j = 0; j <G.vexnum; j++)
 {
  if (!visit[j])
   DFS1(G,j);//不要用&G 因为G已经是地址了
 }
    
// return 0; 
}

void DFS1(MGraph G, int i)
{
 int j;

 visit[i]=TRUE;
 printf("%c",G.vex[i]);
 
 for (j = 0; j < G.vexnum; j++)
 {
  if ((i != j) && (G.arcs[i][j].adj == 1) && !visit[j])
  {
   DFS1(G,j);
  }
 }
    
 // return 0;
}

两种图的遍历方法，第一种为DFS，也就是Depth-First Search，深度优先遍历；第二种为BFS，也就是Breadth-First Search，广度优先遍历。

深度优先遍历是访问到一个未访问的顶点之后，再对这个顶点使用深度优先遍历。如果不能找到未访问的顶点，则返回上一个顶点，并对该顶点相邻的另一个未访问的顶点使用深度优先遍历。直到所有顶点都被访问。深度优先遍历通常使用递归或者堆栈的方式就可以实现了。伪代码如下：

void DFS(Graph *G, int v)
{
    G->mark(v, VISITED);
    for (w = G->first(v); w < w->size(); w = G->next(v, w))
    {
        if (G->get_mark(w) != VISITED)
            DFS(G, w);
    }
}

广度优先遍历是访问到一个未访问的顶点之后，先访问这个顶点的所有相邻的顶点，再深入访问别的顶点。直到所有顶点都被访问到。广度优先遍历使用队列就可以实现了。伪码如下：

void BFS(Graph *G, int v, Queue<int> *Q)
{
    int m, n;
    Q->enqueue(v);
    G->mark(v, VISITED);
    while (Q->length() != 0)
    {
        Q->dequeue(&m);
        for (n = G->first(m); n < G->size(); n = G->next(m, n))
        {
             if (G->get_mark(n) != VISITED)
             {
                 G->mark(n, VISITED); 
                 Q->enqueue(n);
             }
        }
    }
}