非递归实现DFS的DFS函数体

• 非递归实现深度优先遍历的主要问题出在如何回退上
• 这里使用栈来代替递归实现类似的作用
• 返回值k是访问过的顶点数起到了类似深度的作用

1.栈初始化
2.起始点入栈
3.循环语句直到栈为空 {
1.取栈顶元素，不出栈（如果出栈，造成信息丢失，那么回退将无法进行）
2.找未被访问的邻接点，如果没有就出栈一个元素（回退），如果有就将 其进栈，并置访问标记为1。记录这条边进tree数组 }

int Graph_DepthFirst(Graph*g, int start, Edge* tree)
//从start号顶点出发深度优先遍历，（编号从开始）
//返回访问到的顶点数，
//tree[]输出遍历树
//返回的tree[0]是(-1, start), 
//真正的遍历树保存在tree[1..return-1], return是返回值
//顶点的访问次序依次为tree[0].to, tree[1].to, ..., tree[return-1].to
//输入时，tree[]的长度至少为顶点数
//返回值是从start出发访问到的顶点数
{
	/*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
    int stack[g->n]={0};
    int top=-1;
    int visited[g->n]={0};
    int k=0,i,j,w=start;
    visited[start]=1;
    tree[k].from=-1;
    tree[k++].to=start;
    stack[++top]=start; //start入栈
    while(top>=0)
    {
        w=stack[top];  //取栈顶元素
        for(i=w,j=0;;j++)
        {
            if(j>g->n-1)  //未找到没被访问过的邻接点
            {
                top--;  //出栈
                break;
            }
            if((g->adj[i*(g->n)+j]) && visited[j]==0)
            {
                visited[j]=1;  //已访问
                stack[++top]=j;  //j进栈
                tree[k].from=i;
                tree[k++].to=j;
                break;
            }
        }
    }
    return k;
    /*****END*******/
}