Manchester-图的遍历——深度优先搜索

解题思路:
(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]);
}

别忘点赞哦-.-