图的深度优先遍历的非递归算法

实现图的深度优先遍历的非递归算法，图采用邻接表存储。

思想：将初始顶点入栈。然后出栈，如果出栈的这个顶点为被访问过，则将与该顶点相邻的所有顶点全部入栈，如果已经访问过，则略过。

代码：

typedef struct ArcNode{int adjvex;  //该边所指向的顶点的位置 struct ArcNode *next;//指向下一条边的指针 
}ArcNode;//顶点的结点结构 
typedef struct VNode{GElemType data;//顶点信息、ArcNode *first;//指向第一条依附该顶点的边的指针 
}VNode,AdjList[MVNum];//AdjList表示邻接表类型//图的结构定义 
typedef struct{VNode *vertices; //定义一个数组vertices,是vertex的复数形式int vexNum,arcNum; //图的当前顶点数和弧数
}ALGraph;//深度优先实现非递归遍历
void DFS(ALGraph &G,int v,bool *visited){int stack[MAXSIZE],top=-1;stack[++top]=v;//初始化入栈while(top != -1){//栈不为空 int w = stack[top--];//出栈//已经访问过则不在进行入栈if(visited[w]==true) continue;//没有被访问过visited[w] = true;printf("%d",w);//访问邻接结点ArcNode *p G.vertices[w].first;while(p != NULL){if(visited[p->adjvex]==false){//未访问过，则都入栈 stack[++top]=p->adjvex;}p=p->next;} } 
} 
void DFSTraverse(ALGraph &G){// 申请访问数组bool *visited = (bool*)malloc(sizeof(bool)*G.vexNum);//初始化访问数组for(int v=0;i<G.vexNum;++v) {visited[v]=false;}//对图进行遍历，因为图可能不是连通图for(int v=0;v<G.vexNum;++v){if(visited[v]==false){DFS(G,v,visited);}} free(visited);
}