Manchester


私信TA

用户名:wenyajie

访问量:136567

签 名:

最近有点忙,大家的评论等这阵子忙完一定会一个一个回复

等  级
排  名 1
经  验 32842
参赛次数 1
文章发表 167
年  龄 0
在职情况 学生
学  校 Qing Dao University
专  业 计算机科学

  自我简介:

最近有点忙,大家的评论等这阵子忙完一定会一个一个回复

解题思路:

:深度优先遍历的非递归算法可以参照广度优先非递归算法实现;

:总思路

图中任意选取一个顶点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;
          }
      }
     /*栈为空遍历结束*/
}

别忘点赞哦-.-

 

0.0分

3 人评分

  评论区