数据结构拓展习题：邻接表的深度优先非递归遍历

题目：一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

bool visited[MAX_VERTEX_NUM];

void DFS(ALGraph G, int v)

{

       Sqstack S;

       InitStack(S);

       visited[v] = true;

       Push(S, v);

       printf("%d ", G.vertices[v].data);

       ArcNode* p;

       while (!StackEmpty(S))

       {

              p = G.vertices[GetTop(S)].firstarc;//p指向栈顶元素的第一个邻接点

              while (p)

              {

                     if (visited[p->adjvex] == false)//如果p指向的结点没有被访问

                     {

                            visited[p->adjvex] = true;//访问该结点

                            printf("%d ", G.vertices[p->adjvex].data);

                            Push(S, p->adjvex);//将该结点入栈

                            p = G.vertices[p->adjvex].firstarc;//p指向该结点的第一个邻接点

                     }

else//如果p指向的结点被访问过，

                            p = p->nextarc; //则访问该结点没有被访问过的邻接点

              }

              if (p == NULL)

                     Pop(S);

       }

}

void DFS_Traverse(ALGraph G)

{

       for (int v = 0; v < G.vexnum; v++)

              visited[v] = FALSE;

       for (int v = 0; v < G.vexnum; v++)

       {

              if (!visited[v])

                     DFS(G, v);

       }

}