課程目標

• 了解樹/圖的深度遍歷，寬度遍歷基本原理；
• 會使用python語言編寫深度遍歷，廣度遍歷代碼；
• 掌握拓撲排序算法

搜索算法的意義和作用

搜索引擎

提到搜索兩個子，大家都應(yīng)該會想到搜索引擎，搜索引擎的基本工作步驟；
網(wǎng)頁爬取 — 數(shù)據(jù)預(yù)處理 — 排序 — 查詢
第一步，網(wǎng)頁爬取，非常重要，簡單來說，就是給爬蟲（蜘蛛程序或者爬蟲機器人）分配一組起始的網(wǎng)頁，爬取一個網(wǎng)頁后，解析提取出這個網(wǎng)頁里的所有超鏈接，再依次爬取出這些超鏈接，再提取網(wǎng)頁超鏈接，如此不斷重復，從而提取網(wǎng)頁內(nèi)容。

海量的網(wǎng)頁鏈接之間最終構(gòu)成了一張圖，于是問題就變成了如何遍歷這張圖。
現(xiàn)在的網(wǎng)絡(luò)，網(wǎng)站機構(gòu)復雜，信息太多，所以蜘蛛爬行也是有一定策略的?；A(chǔ)就是廣度優(yōu)先和深度優(yōu)先兩種?，F(xiàn)實確實時間和帶寬優(yōu)先，再大的搜索引擎也僅僅只能是收入小部分網(wǎng)頁。提升網(wǎng)絡(luò)爬蟲的主要方法有：提升網(wǎng)站權(quán)重/頻繁更新/導入鏈接/減短與首頁的距離等等。

深度優(yōu)先搜索DFS

定義與基本內(nèi)容

深度優(yōu)先搜索屬于圖算法的一種（Depth First Search）。其過程簡要來說就是對每一個可能的分支路徑深入到不能深入為止，而且每一個節(jié)點只能訪問一次。

深度優(yōu)先搜索是每一次按照一個方向進行窮盡式的搜索，當該方向上的搜索無法繼續(xù)往前的時候，這時候就退回到上一步，換一個方向繼續(xù)搜索。

算法演示如下：

樹的深度優(yōu)先搜索

從跟節(jié)點開始，一直搜索左子樹，直到某個節(jié)點沒有左子樹為止，接著換個方向搜索右子樹。如圖，

DFS的序列為（先序遍歷）：0 —> 1 —> 3 —> 4 —> 2 —> 5 —> 6

無向圖的深度優(yōu)先搜索

假設(shè)初始狀態(tài)是圖中所有頂點均未被訪問，則從某個頂點v出發(fā)，首先訪問該頂點，然后依次從它的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到。
若此時尚有其他頂點未被訪問到，則另選一個未被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。

從頂點A開始深度優(yōu)先搜索；

1. 訪問A；
2. 訪問A的相鄰節(jié)點C
3. 訪問C的相鄰節(jié)點B
4. 在步驟3中訪問了C的鄰節(jié)點B之后，B周圍沒有鄰節(jié)點未被訪問；因此返回C節(jié)點，訪問C的另一個鄰節(jié)點D；
5. 在步驟4中訪問了D后，D周圍沒有未被訪問的鄰接點，因此返回C，再返回A，訪問F；
6. 訪問F的鄰接點G
7. 訪問G的鄰接點E

訪問的順序：A—C—B—D—F—G—E

有向圖的深度優(yōu)先搜索

1. 步驟1，訪問A
2. 步驟2，訪問A的出邊的頂點B
3. 步驟3，訪問B的出邊的頂點C
4. 步驟4，訪問C的出邊的頂點E
5. 步驟5，訪問E的出邊的頂點D和B（B在步驟2中已經(jīng)訪問過了）所以訪問D
6. 步驟6，返回之前的節(jié)點，直到碰到還有未訪問的出邊頂點，所以訪問到B的出邊頂點F
7. 步驟7，訪問G

訪問順序：A—B—C—E—D—F—G

典型題目（200. 島嶼數(shù)量）

https://leetcode.cn/problems/number-of-islands/description/


DFS（深度優(yōu)先搜索）問題通常在樹或者圖結(jié)構(gòu)上進行的，而這道提屬于網(wǎng)絡(luò)結(jié)構(gòu)，網(wǎng)絡(luò)結(jié)構(gòu)要比二叉樹結(jié)構(gòu)稍微復雜，它其實是一個簡化版的圖結(jié)構(gòu)。
分析：

1. 訪問相鄰節(jié)點：網(wǎng)絡(luò)結(jié)構(gòu)中，上下左右四個位置都是相鄰節(jié)點。坐標為（x, y）的格子，其四個相鄰的格子分別為（x-1，y） （x+1，y） （x，y-1） （x，y+1）
2. 判斷base case：如果走進超出網(wǎng)格返回的格子，那么直接返回；
3. 先往四個方向走一步再說，如果發(fā)現(xiàn)走出了網(wǎng)格范圍再趕緊返回；
4. 標記已經(jīng)遍歷過的格子。我們只關(guān)注值為1的格子做DFS遍歷，每走過一個陸地格子，那就把格子的值改成0.

思路：

• 采用DFS方式：從（i，j）向此點的上下左右（i+1， j），（i-1， j）， （i， j-1），（i， j+1）做深度搜索；
• 終止條件：①（i，j）越過矩陣邊界；②非陸地
• 搜索島嶼的同時，將遍歷過的地方改為0，以免重復搜索相同島嶼

主循環(huán)：
遍歷整個矩陣，當遇到grid[i][j]==1時，從此點開始做深度優(yōu)先搜索dfs，島嶼的數(shù)量+1且在深度優(yōu)先搜索中刪除此島嶼。
最終返回島嶼數(shù)量count。

class Solution:
   def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, i, j, rows, cols):
            # 退出條件
            if i < 0 or i >  rows - 1 or j < 0 or j > cols - 1 or grid[i][j] != "1":
                return
            grid[i][j] = '0'
            dfs(grid, i, j+1, rows, cols)
            dfs(grid, i, j-1, rows, cols)
            dfs(grid, i+1, j, rows, cols)
            dfs(grid, i-1, j, rows, cols)

        rows = len(grid)
        if rows == 0:
            return 0
        cols = len(grid[0])

        num_islands = 0
        for i in range(rows):
            for j in range(cols):
                # 只有確認時島嶼，才會遍歷
                if grid[i][j] == '1':
                    # 發(fā)現(xiàn)島嶼，島嶼個數(shù)加1
                    num_islands += 1
                    dfs(grid, i, j, rows, cols)
        
        return num_islands

附錄基礎(chǔ)

python基礎(chǔ)語法

python基礎(chǔ)精講

本專欄主要針對python基礎(chǔ)語法，幫助學習者快速接觸并掌握python大部分最重要的語法特征。
1、基本數(shù)據(jù)類型和變量
2、分支結(jié)構(gòu)與循環(huán)結(jié)構(gòu)
3、函數(shù)與異常處理
4、類與模塊
5、文件讀寫

通過本專欄可以快速掌握python的基礎(chǔ)語法。

python數(shù)據(jù)結(jié)構(gòu)與算法理論基礎(chǔ)（專欄）

數(shù)據(jù)結(jié)構(gòu)與算法（python）
程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法；而且在面試過程中這些是必考，必問的內(nèi)容。內(nèi)容大綱：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)（樹、鏈表、棧、隊列等）、常見算法（排序算法、遞歸算法等）。

專欄是基于python的基礎(chǔ)知識，是很好的入門學習資料。幫助大家快速理解這些數(shù)據(jù)結(jié)構(gòu)和常見算法的概念，同時結(jié)合力扣題目，也能更好的掌握這些知識，達到在面試中游刃有余的效果。文章來源地址http://www.zghlxwxcb.cn/news/detail-807674.html

到了這里，關(guān)于python算法與數(shù)據(jù)結(jié)構(gòu)（搜索算法和拓撲排序算法）---深度優(yōu)先搜索的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！