<学习笔记>深度优先算法与广度优先算法

2017-10-03

本人这两种算法在课上没好好学过，只能通过读别人写的书和博客进行学习，如有个别雷同，希望见谅(那说明那个人写的一定很好a)。
在网上和书上看了不同的实现方法，我觉得有一种基于邻接矩阵的方法不错，那就做做笔记吧。
在我们讨论这两种图的基本搜索方法时，我们先来定义一下我们的图吧，确定一下图的存储结构。

struct Graph{
  int numofvert;
  int numofedge;
  int matrix[20][20];
};
//先把这个图初始化一下了；
void initgraph(Graph &G){
  G.numofedge=5;
  G.numofvert=5;
  G.matrix[0][2]=1;
  G.matrix[2][0]=1;
  G.matrix[0][3]=1;
  G.matrix[3][0]=1;
  G.matrix[1][2]=1;
  G.matrix[2][1]=1;
  G.matrix[1][4]=1;
  G.matrix[4][1]=1;
  G.matrix[2][4]=1;
  G.matrix[4][2]=1;    
}

深度优先遍历算法(DFS)
深度优先搜索的思想大致可以这么说：
这是一个不断的探查与回溯的过程。在探查的每一步，都会有一个当前顶点v，每一步探查，都会先访问当前顶点，然后将其设一个标志来标记已访问过。接着在它的邻接顶点中，找出未访问的一个，将其作为下一个当前顶点v’，如果所有的邻接顶点都被访问过了，那么我们返回上上步，将前一步所访问的顶点作为当前顶点，重复上述过程即可。
通俗点讲，就是我们每做的一步都要一探到底，到了底在掉头回去找其他路，优先纵向搜索。
那么我们一边看代码一边再做一次理解吧。

bool visited[20];
void DFS(Graph& g,int v){    //核心方法；
  visited[v]=true;                //将开始顶点设置为已经访问过；
  printf("%d ",v);                 //打印当前节顶；
  for(int i=0;i<g.numofvert;i++){           
    if(g.matrix[v][i]==1&&visited[i]==false){ //获取当前节点未访问过的邻接顶点;
      DFS(g,i);//递归调用，所有顶点都访问过后，进行回溯。
    }
  }
}
void DFST(Graph g){    //主方法，也就是看作遍历的入口方法；
  for(int i=0;i<g.numofvert;i++){
    visited[i]=false;     //将每个顶点初始化，都未访问过；
  }
  for(int i=0;i<g.numofvert;i++){
    if(visited[i]==false){
      DFS(g,i);      //挑选没有访问的第一个顶点，进行遍历；
    }
  }
}

广度优先遍历算法(BFS)
广度优先遍历是一个逐层遍历的过程。
在这个过程中，图中有多少个顶点就要重复多少步，在每一步中，规定一个当前顶点v，并设置它是被访问过的，接着依次访问v的各个未曾被访问过的邻接顶点，然后再顺序访问这些邻接顶点的未访问过的邻接节点。再从这些未访问过的顶点中，继续重复上述步骤。直到所有的顶点都被访问过为止。
通俗点讲，就是逐层递进，优先横向搜索。
贴代码；

#include<queue>
using namespace std;
void BFST(Graph g){
  for(int i=0;i<g.numofvert;i++){
    visited[i]=false;     //先将所有的顶点的初始状态都设置为未访问过；
  }
  queue<int> myq;
  for(int i=0;i<g.numofvert;i++){
    if(visited[i]==false){     //如果该顶点未访问过；
      myq.push(i);             //将其下标入队；
      visited[i]=true;
      while(!myq.empty()){      //队列未空，那么遍历就不结束；
        int t=myq.front();      //将队列头取出；
        myq.pop();
        printf("%d ", t);       //打印出当前访问的顶点；
        for(int j=0;j<g.numofvert;j++){     //将其未访问过的邻接节点加入队列；
          if(g.matrix[t][j]==1&&visited[j]==false){
            myq.push(j);
            visited[j]=true;//push()与设置为true成对达到标志访问的作用。
          }
        }
      }
    }
  }
}

设顶点数为n，那么这两种遍历方法的时间复杂度都是O(n^2);