Manchester- 图的遍历——深度优先搜索（非递归+邻接矩阵转邻接表）

解题思路:

①：深度优先遍历的非递归算法可以参照广度优先非递归算法实现；

②：总思路

图中任意选取一个顶点v（题目要求编号为0）开始遍历

访问该节点v，之后再访问该节点v的一个未被访问过的邻接顶点v1，然后再访问v1的一个未被访问过的邻接顶点，依次类推，直到访问到某个顶点vi，且vi的所有邻接顶点都被访问过，则原路返回到上一个未被访问的节点vi-1，再访问vi-1的一个为被访问的邻接顶点，再依次类推，直到图中所有顶点被访问完为止。

以上原路返回的过程，需要用一个栈来保存已经访问过的顶点

得到以下算法：

1）：从顶点v开始访问

2）：访问v并入栈

3）：当栈不为空循环下面过程

  1：获取栈顶元素j

  2：找到j的一个未被访问的邻接点

  3：若找到这样一个顶点，则访问后入栈

  4：没找到这样一个顶点，栈顶元素出栈

4）：栈为空结束

注意事项:

题目输入的是邻接矩阵，这里把它转化为邻接表，因为邻接表的遍历时间复杂度为

o(n+e),但是邻接矩阵为o(n*n);无论是DFS,还是BFS都是如此；

参考代码:

#include<stdio.h>
#include<malloc.h>
/*边表节点*/
typedef struct ArcNode_{

   int adjvex;/*节点编号*/
   struct ArcNode_ * nextarc;/*下一个边表节点指针*/

}*arcnode,ArcNode;
/*顶点表节点*/
typedef struct VNode_{

  char data;/*顶点表节点信息（可有可无）*/
  ArcNode *firstarc;/*第一个边表节点指针*/

}*vnode,VNode;
/*图的定义*/
typedef struct Agraph_{

  int n,e;/*顶点数与边数*/
  VNode *adjlist;/*顶点表指针*/

}*agraph,Agraph;

void creat_adjlist(agraph G,int n);
void DFS_(agraph G,int v);

int main()
{
    int n;/*顶点数*/
    while(scanf("%d",&n)!=EOF)
    {
        Agraph G;/*建立图*/
        /*根据输入的邻接矩阵建立邻接表*/
        creat_adjlist(&G,n);
        /*深度优先遍历（非递归）*/
        DFS_(&G,0);
        printf("\n");/*末尾换行*/
    }
    return 0;
}

/*-----------------------------------------------------*/
void creat_adjlist(agraph G,int n)
{
    /*首先配置G*/
    G->n=n;/*保存顶点数*/
    /*为G的顶点表开辟空间*/
    G->adjlist=(vnode)malloc(G->n*sizeof(VNode));

    int data;/*邻接表的每一个元素存放再这里面*/
    ArcNode Head;
    Head.nextarc=NULL;
     ArcNode *p,*q;/*建立边表使用*/

       for(int i=0;i<n;i++)
       {
           /*每次建立一个边表，初始化一次*/
           Head.nextarc=NULL;
           p=&Head;
           /*为顶点表中编号为i的节点建立边表*/
           for(int j=0;j<n;j++)
           {
               scanf("%d",&data);
               if(data!=0)
               {
                   q=(arcnode)malloc(sizeof(ArcNode));/*建立一个边表节点*/
                   q->adjvex=j;/*保存节点编号*/
                   /*把该边表节点插入边表，注意采用后插法*/
                   p->nextarc=q;
                   q->nextarc=NULL;
                   p=p->nextarc;
               }
           }
           /*建立完i的边表，让i的firstarc指向边表的首节点，注意不是头节点*/
           G->adjlist[i].firstarc=Head.nextarc;
       }
       /*邻接表建立完毕*/
}

/*------------------------------------------------------------------------------*/
void DFS_(agraph G,int v)
{
    /*定义一个简单的栈*/
    int Stack[G->n];
    int top=-1;/*也可以为0，具体见栈的实现题解*/

    /*定义访问数组并置0*/
    int visit[G->n];
      for(int i=0;i<G->n;i++)
        visit[i]=0;

     /*访问起始顶点*/
     printf("%d ",v);
     visit[v]=1;/*标记为已经访问*/
     Stack[++top]=v;/*该顶点入栈*//*只能为++top，见栈实现题解*/

      int j;/*保存栈顶节点编号*/
      ArcNode *p;/*遍历边表节点使用*/
      while(top!=-1)/*当栈不等于空，循环以下内容*/
      {
          /*得到栈顶元素*/
          j=Stack[top];
          /*找到该顶点的一个未被访问的邻接点*/
          p=G->adjlist[j].firstarc;

          while(p!=NULL&&visit[p->adjvex]==1)
            p=p->nextarc;

          /*如果其邻接点都被访问过，栈顶元素出栈*/
          if(p==NULL)
          {
              top--;
          }
          else/*否则访问该邻接顶点，并且入栈*/
          {
              printf("%d ",p->adjvex);
              visit[p->adjvex]=1;
              Stack[++top]=p->adjvex;
          }
      }
     /*栈为空遍历结束*/
}

别忘点赞哦-.-