Manchester


私信TA

用户名:wenyajie

访问量:103723

签 名:

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

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

  自我简介:

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

解题思路:
(1)总思路:在图中任意选取一个顶点开始(题目要求编号为0开始),访问该顶点,并把该顶点设置为已访问

如visit[i]=1表示编号为i的顶点已经访问过。然后选取与该顶点邻接的一个未被访问过 的顶点访问,并把该顶点设置为已访问,当某个顶点的所有邻接顶点都已访问,则依次返回到最近访问过的节点,再选取与该顶点邻接的一个未被访问过 的顶点访问。当图中所有顶点都已经访问过时,遍历结束。


(2)以上过程为思想描述过程,但在实际代码描述中,许些地方不同

①:假设图的存储结构为邻接表,从顶点v开始访问,其代码遍历过程为

②:访问该顶点v,把该顶点置为已访问visit[v]=1

③:让p指向v的第一个边表节点

④:当p不等于NULL时,循环以下过程

1):如果该边表节点未被访问过,以该节点为顶点继续深度优先遍历

2):1)结束后 p=p->nextarc p等于p的下一个边表节点


以下为邻接表图结构定义模板,以及其在邻接表结构下的DFS

typedef struct ArcNode_{
    
    int adjvex;/*边表节点编号,其实也就是顶点编号*/
    struct ArcNode_ * nextarc;/*指向下一个边表节点*/
}*arcnode,ArcNode;

typedef struct VNode_{
    char data;/*顶点数据*/
    ArcNode * firstarc;/*指向他的第一个边表节点*/

}*vnode,VNode;

typedef struct Agraph_{
  
  VNode adjlist[maxsize];/*邻接表*/ /*maxsize为图顶点数*/
  int n,e;/*图的定点数和边数*/

}*agraph,Agraph;
int visit[maxsize]={0};
void DFS(Agraph* G,int v)
{
    ArcNode * p;
    visit(v);/*访问v*/
    visit[v]=1;/*编号为v的顶点设置为已经访问*/

     p=G->adjlist[v].firstarc;
      while(p!=NULL)
      {
          if(visit[p->adjvex]==0)/*若顶点v的第一个边表节点未被访问过/这里第一个指刚进循环时*/
            DFS(G,p->adjvex);
          p=p->nextarc;/*下一个边表节点*/
      }
}

注意事项:

题目输入为邻接矩阵,因为输入的一定是无向图所以偷个懒把它直接当做邻接表,故可以第0列为顶点表,后面1到n-1列分别为边表节点。

一定要在熟练理解背诵上面所有代码的基础上,书写代码

不用先把它转化为邻接表存储,再用以上代码

参考代码:

#include<stdio.h>
#include<malloc.h>

void DFS_(int **edges,int visit[],int n,int v);
void input(int **edges,int n);
int main()
{
    int n;/*定点个数*/
    int **edges;/*邻接矩阵*/
    while(scanf("%d",&n)!=EOF)
    {   /*为邻接矩阵开辟空间*/
        edges=(int **)malloc(n*sizeof(int *));
         for(int i=0;i<n;i++)
            edges[i]=(int *)malloc(n*sizeof(int));
          int visit[n];
          for(int i=0;i<n;i++)
            visit[i]=0;/*访问数组起始为0*/
          input(edges,n);/*输入邻接矩阵*/
          DFS_(edges,visit,n,0);

    }
    return 0;
}
/*==========================================================*/
void DFS_(int **edges,int visit[],int n,int v)
{
    printf("%d ",v);/*输出访问顶点*/
    visit[v]=1;/*顶点v设置为已访问*/
      for(int i=1;i<n;i++)/*相当于while(p!=NULL)*/
      {
          if(edges[v][i]!=0&&visit[i]==0)/*如果顶点i是v的邻接顶点,且没有被访问,则进行以i为顶点的深度优先遍历*/
          {
              DFS_(edges,visit,n,i);
          }
      }
}
/*==========================================================*/
void input(int **edges,int n)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        scanf("%d",&edges[i][j]);
}

别忘点赞哦-.-

 

0.0分

0 人评分

C语言网提供「C语言、C++、算法竞赛」在线课程,全部由资深研发工程师或ACM金牌大佬亲授课,更科学、全面的课程体系,以在线视频+在线评测的学习模式学习,学练同步,拒绝理论派,真正学会编程!还有奖学金等增值福利等你!

  评论区

大佬
2019-04-16 01:38:43 | |
很好
2019-01-17 16:53:05 | |
  • «
  • 1
  • »