本文共 2827 字，大约阅读时间需要 9 分钟。

深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search

一，应用

（1）拓扑排序（比如，在大学里必须满足一些先决条件才能选的课程）

（2）走迷宫和八皇后问题（结合回溯算法） （3）部分和，给出的n个数字中找到m和数字加起来等于sum （4）检验连通性的问题（求联通分量） （5）求无权最短路

二，算法思想

（注：遍历结果不唯一，要看输入的顺序）

DFS的操作步骤如下（非递归方式）：

1、把起始点放入stack；

2、重复下述3步骤，直到stack为空为止： （1）从stack中访问栈顶的点； （2）找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入stack中； （3）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出。

DFS的操作步骤如下（递归方式）：

1，初始化每个节点，令其访问标志为0

2，对初识节点调用DFS访问， 只要p不空即（即边表不空)，如该节点没被访问过就递归调用DFS来访问，访问过以后标志记为1，否则p=p->next找下一个相邻节点 3 ，循环遍历，对每个节点执行相同的操作，直到全部访问完

算法实现

#include
   
    #include
    
     #define MAXVEX 1000typedef char VertexType;int Visited[MAXVEX];//时间复杂度O(E+V) //边表结点 typedef struct EdgeNode{    int adjvex;    int value;//权值     struct EdgeNode *next;}EdgeNode;//顶点表结点typedef struct VertexNode{    VertexType data;     //顶点信息     EdgeNode *firstedge; //头指针 }VertexNode,AdjList[MAXVEX];typedef struct{    AdjList adjlist;     int numVertexes,numEdges;}GraphAdjList,*Mgraph;//创建邻接表void Create(GraphAdjList *G){    int i,j,k;    EdgeNode *p;    printf("输入顶点数和边数:\n");    scanf("%d%d",&G->numVertexes,&G->numEdges);    //输入顶点信息    printf("输入顶点信息:\n");    for(i=0;i
     
      numVertexes;i++){       getchar();       scanf("%c",&G->adjlist[i].data);        G->adjlist[i].firstedge=NULL;           //将指向边表的指针初始化     }     //建立边表    printf("输入边(Vi,Vj)中的下标i,j和权值:\n");     for(k=0;k
      
       numEdges;k++){    	int v = 0;         p=(EdgeNode *)malloc(sizeof(EdgeNode));        scanf("%d%d%d",&i,&j,&v);        p->value = v;        p->adjvex=j;                                //存储弧头         p->next=G->adjlist[i].firstedge;            //头插法插入边结点         G->adjlist[i].firstedge=p;        //下面代码有向图无,无向图有         p=(EdgeNode *)malloc(sizeof(EdgeNode));        p->value = v;        p->adjvex=i;                                //存储弧头         p->next=G->adjlist[j].firstedge;            //头插法插入边结点         G->adjlist[j].firstedge=p;    }       //打印邻接表   printf("边:权值\n");    for(i=0;i
       
        numVertexes;i++){        p=G->adjlist[i].firstedge;        while(p){            printf("(%c,%c)",G->adjlist[i].data,G->adjlist[p->adjvex].data);            printf(" %d",p->value);            p=p->next;        }        printf("\n");    } 	} void DFS(Mgraph G,int v){	 EdgeNode  *p ;    if(Visited[v]==0) { printf("%c ",G->adjlist[v].data);}      /*  置访问标志，访问顶点v  */      Visited[v]=1;    p=G->adjlist[v].firstedge;   /*  链表的第一个结点  */    while (p!=NULL){ 	 if (!Visited[p->adjvex]) {DFS(G, p->adjvex) ;} /*  从v的未访问过的邻接顶点出发深度优先搜索   */          p=p->next;    }} void DFS_traverse_Grapg(GraphAdjList *G,int t)//t是初始点的下标 {       	    for (int v=0 ; v
        
         numVertexes ; v++){ /* 访问标志初始化 */ Visited[v]=0 ; } DFS(G, t); //访问初始点 for (int v=0 ; v
         
          numVertexes; v++){ if (Visited[v]==0) DFS(G ,v);//未访问过，那么就用DFS访问 }}int main(){ GraphAdjList g; Create(&g); DFS_traverse_Grapg(&g,0); return 0;}
         
        
       
      
     
    
   

转载地址：http://kgqen.baihongyu.com/