前言

這幾天復(fù)習(xí)圖論算法，覺(jué)得BFS和DFS挺重要的，而且應(yīng)用比較多，故記錄一下。

廣度優(yōu)先搜索

有一個(gè)有向圖如圖a

image

廣度優(yōu)先搜索的策略是：

從起始點(diǎn)開(kāi)始遍歷其鄰接的節(jié)點(diǎn)，由此向外不斷擴(kuò)散。

1.假設(shè)我們以頂點(diǎn)0為原點(diǎn)進(jìn)行搜索，首先確定鄰接0的頂點(diǎn)集合S0 = {1，2}。

2.然后確定頂點(diǎn)1的集合S1 = {3}，頂點(diǎn)2沒(méi)有鄰接點(diǎn)，所以集合為空。

3.然后確定3的鄰接點(diǎn)集合S3，因?yàn)?已經(jīng)被遍歷過(guò)，所以不考慮，所以由頂點(diǎn)3知道的鄰接點(diǎn)集合S3 = {4}。

4.然后再確定頂點(diǎn)4的鄰接點(diǎn)集合,頂點(diǎn)4沒(méi)有更多的鄰接點(diǎn)了，此時(shí)也沒(méi)有還未遍歷的鄰接點(diǎn)集合，搜索終止。

遍歷的路徑可以參考如下圖紅色標(biāo)記的路徑：

image

動(dòng)態(tài)過(guò)程

image

代碼的實(shí)現(xiàn)思路：

BFS()
{
  輸入起始點(diǎn)；
  初始化所有頂點(diǎn)標(biāo)記為未遍歷；
  初始化一個(gè)隊(duì)列queue并將起始點(diǎn)放入隊(duì)列；

  while（queue不為空）
  {

    從隊(duì)列中刪除一個(gè)頂點(diǎn)s并標(biāo)記為已遍歷； 
    將s鄰接的所有還沒(méi)遍歷的點(diǎn)加入隊(duì)列；
  }
}

深度優(yōu)先遍歷

繼續(xù)以圖a為例

image

深度優(yōu)先遍歷的策略是：

從一個(gè)頂點(diǎn)v出發(fā)，首先將v標(biāo)記為已遍歷的頂點(diǎn)，然后選擇一個(gè)鄰接于v的尚未遍歷的頂點(diǎn)u，如果u不存在，本次搜素終止。如果u存在，那么從u又開(kāi)始一次DFS。如此循環(huán)直到不存在這樣的頂點(diǎn)。

比如圖a中

1.從頂點(diǎn)0開(kāi)始，將0標(biāo)記為已遍歷，然后選擇未被遍歷的鄰接0的頂點(diǎn)1。

2.標(biāo)記頂點(diǎn)1，然后選擇3并標(biāo)記，然后選擇頂點(diǎn)3鄰接的頂點(diǎn)2。

3.頂點(diǎn)2標(biāo)記后沒(méi)有與它鄰接的未標(biāo)記的點(diǎn)，所以返回3選擇另一個(gè)鄰接3并且未被標(biāo)記的頂點(diǎn)4。

4.頂點(diǎn)4沒(méi)有更多的符合條件的點(diǎn)，因此搜索終止，返回到3，3沒(méi)有更多的點(diǎn)，搜索終止返回到1，最后返回到0，搜索終止。

遍歷的路徑可以參考如下圖紅色標(biāo)記的路徑：

image

動(dòng)態(tài)過(guò)程

image

代碼的實(shí)現(xiàn)思路：

DFS（頂點(diǎn)v）
{
  標(biāo)記v為已遍歷；
  for（對(duì)于每一個(gè)鄰接v且未標(biāo)記遍歷的點(diǎn)u）
      DFS（u）;
}

一個(gè)簡(jiǎn)單的應(yīng)用

問(wèn)題不贅述，具體可參考 LeetCode朋友圈問(wèn)題 。

實(shí)現(xiàn)的代碼如下（C#）：

public class Solution {
    public void dfs(int [,]M,int []visit,int i)
    {
        for(int j = 0;j < M.GetLength(0);j++)
        {
            if(M[i,j] == 1 && visit[j] == 0)
            {
                visit[j] = 1;
                dfs(M,visit,j);
            }
        }
    }

    public void bfs(int [,]M,int []visit,int i)
    {
        Queue<int> q = new Queue<int>();
        q.Enqueue(i);
        while(q.Count > 0)
        {
            int temp = q.Dequeue();
            for(int j = 0;j < M.GetLength(0);j++)
            {
                if(M[temp,j] == 1 && visit[j] == 0)
                {
                    visit[j] = 1;
                    q.Enqueue(j);
                }
            }
        }
    }

    public int FindCircleNum(int[,] M) {
        int N = M.GetLength(0);
        int circle = 0; //朋友圈數(shù)
        int[] visit = new int[N];
        for(int i = 0;i < N;i++)
        {
            if(visit[i] == 0) //還沒(méi)被遍歷過(guò)
            {
                //dfs(M,visit,i); //使用dfs搜索并標(biāo)記與其相關(guān)的學(xué)生
                bfs(M,visit,i);   //使用bfs搜索并標(biāo)記與其相關(guān)的學(xué)生
                circle++;
            }
        }
        return circle;
    }
}