算法是編碼面試中最常見(jiàn)的主題之一。為了在面試中獲得優(yōu)勢(shì)，非常熟悉頂級(jí)算法及其實(shí)現(xiàn)非常重要。

在次此篇文章中，我們將探索圖算法。我們將從圖論和圖算法的介紹開(kāi)始。接下來(lái)，我們將學(xué)習(xí)如何實(shí)現(xiàn)圖。

今天，我們將學(xué)習(xí)：

• 什么是圖算法？
• 圖的屬性
• 如何在代碼中表示圖形
• 如何實(shí)現(xiàn)廣度優(yōu)先遍歷
• 如何實(shí)現(xiàn)深度優(yōu)先遍歷
• 如何去除邊緣

什么是圖算法？

算法是使用明確定義或最佳步驟數(shù)解決問(wèn)題的數(shù)學(xué)過(guò)程。它只是用于完成特定工作的基本技術(shù)。

圖是一種抽象符號(hào)，用于表示所有對(duì)象對(duì)之間的連接。圖是廣泛使用的數(shù)學(xué)結(jié)構(gòu)，由兩個(gè)基本組成部分可視化：節(jié)點(diǎn)和邊。

圖算法用于解決將圖表示為網(wǎng)絡(luò)的問(wèn)題，例如航空公司航班、互聯(lián)網(wǎng)如何連接或微信、QQ、微博上的社交網(wǎng)絡(luò)連接。它們?cè)贜LP和機(jī)器學(xué)習(xí)中也很流行，用于形成網(wǎng)絡(luò)。

一些頂級(jí)的圖形算法包括：

• 實(shí)現(xiàn)廣度優(yōu)先遍歷
• 實(shí)現(xiàn)深度優(yōu)先遍歷
• 計(jì)算圖級(jí)別中的節(jié)點(diǎn)數(shù)
• 查找兩個(gè)節(jié)點(diǎn)之間的所有路徑
• 查找圖的所有連通分量
• Dijkstra 算法在圖數(shù)據(jù)中查找最短路徑
• 移除邊緣

雖然圖是離散數(shù)學(xué)不可或缺的一部分，但它們?cè)谟?jì)算機(jī)科學(xué)和編程中也有實(shí)際用途，包括以下內(nèi)容：

• 計(jì)算機(jī)程序中以圖形表示的調(diào)用者-被調(diào)用者關(guān)系
• 網(wǎng)站的鏈接結(jié)構(gòu)可以用有向圖來(lái)表示
• 神經(jīng)網(wǎng)絡(luò)

圖的屬性

由 G 表示的圖由一組頂點(diǎn) (V)或在邊 (E)處鏈接的節(jié)點(diǎn)表示。邊的數(shù)量取決于頂點(diǎn)。邊緣可以是有向的或無(wú)向的。

在有向圖中，節(jié)點(diǎn)沿一個(gè)方向鏈接。這里的邊顯示了一種單向關(guān)系。

在無(wú)向圖中，邊是雙向的，顯示出雙向關(guān)系。

示例：無(wú)向圖的一個(gè)很好的用例是微信好友建議算法。用戶（節(jié)點(diǎn)）有一個(gè)邊緣運(yùn)行到朋友 A（另一個(gè)節(jié)點(diǎn)），而朋友 A 又連接（或有一個(gè)邊緣運(yùn)行）到朋友 B。然后將朋友 B 推薦給用戶。

還有許多其他復(fù)雜類(lèi)型的圖屬于不同的子集。例如，當(dāng)每個(gè)頂點(diǎn)都可以從其他每個(gè)頂點(diǎn)到達(dá)時(shí)，有向圖就具有強(qiáng)連通分量。

頂點(diǎn)

頂點(diǎn)是多條線相交的點(diǎn)。它也稱(chēng)為節(jié)點(diǎn)。

邊緣

邊是一個(gè)數(shù)學(xué)術(shù)語(yǔ)，用于表示連接兩個(gè)頂點(diǎn)的線。許多邊可以由單個(gè)頂點(diǎn)形成。然而，沒(méi)有頂點(diǎn)，就無(wú)法形成邊。每條邊必須有一個(gè)起始和結(jié)束頂點(diǎn)。

路徑

圖中的路徑G=( V ,E ）是頂點(diǎn) v1, v2, …, vk 的序列，其屬性是之間有邊 vi 和 vi +1。我們說(shuō)路徑從v1到vk 。

序列 6,4,5,1,26,4,5,1,2 定義從節(jié)點(diǎn) 6 到節(jié)點(diǎn) 2 的路徑。

類(lèi)似地，可以通過(guò)遍歷圖的邊來(lái)創(chuàng)建其他路徑。如果路徑的頂點(diǎn)全部不同，則路徑很簡(jiǎn)單。

行走

行走是路徑，但它們不需要一系列不同的頂點(diǎn)。

連通圖

如果對(duì)于每對(duì)頂點(diǎn)，則圖是連通的v和v，有一條路徑從v到v。

循環(huán)

循環(huán)是一條路徑 v1, v2, …, vk，滿足以下條件：

• k>2k>2k>2k _>2
• 首先k-1頂點(diǎn)都不同
• v1=vk

樹(shù)

樹(shù)是不包含環(huán)的連通圖。

環(huán)形

在圖中，如果從頂點(diǎn)到自身繪制一條邊，則稱(chēng)為環(huán)。在圖中，V 是一個(gè)頂點(diǎn)，其邊 (V, V) 形成一個(gè)環(huán)。

如何在代碼中表示圖形

在我們繼續(xù)使用圖算法解決問(wèn)題之前，首先了解如何在代碼中表示圖非常重要。圖可以表示為鄰接矩陣或鄰接列表。

鄰接矩陣

鄰接矩陣是由圖頂點(diǎn)標(biāo)記的方陣，用于表示有限圖。矩陣的條目指示頂點(diǎn)對(duì)在圖中是否相鄰。

在鄰接矩陣表示中，需要迭代所有節(jié)點(diǎn)來(lái)識(shí)別節(jié)點(diǎn)的鄰居。

a  b  c  d  e
a   1  1  -  -  -
b   -  -  1  -  -
c   -  -  -  1  -
d   -  1  1  -  -

鄰接表

鄰接表用于表示有限圖。鄰接列表表示允許輕松地遍歷節(jié)點(diǎn)的鄰居。列表中的每個(gè)索引代表頂點(diǎn)，與該索引鏈接的每個(gè)節(jié)點(diǎn)代表其相鄰頂點(diǎn)。

1  a ->  { a b }
2  b ->  { c }
3  c ->  { d }
4  d ->  { b c }

對(duì)于下面的基圖類(lèi)，我們將使用鄰接列表實(shí)現(xiàn)，因?yàn)樗鼘?duì)于本文后面的算法解決方案執(zhí)行得更快。

圖類(lèi)（Graph Class）

我們的圖實(shí)現(xiàn)的要求相當(dāng)簡(jiǎn)單。我們需要兩個(gè)數(shù)據(jù)成員：圖中頂點(diǎn)的總數(shù)和存儲(chǔ)相鄰頂點(diǎn)的列表。我們還需要一種添加邊或一組邊的方法。

class AdjNode:
    """
    表示節(jié)點(diǎn)鄰接表的 類(lèi)
    """
    def __init__(self, data):
        """
        構(gòu)造函數(shù)
        :參數(shù)數(shù)據(jù) : 頂點(diǎn)
        """
        self.vertex = data
        self.next = None

class Graph:
    """
    圖類(lèi) ADT
    """

    def __init__(self, vertices):
        """
        構(gòu)造函數(shù)
        :param vertices : 圖中的總頂點(diǎn)數(shù)
        """
        self.V = vertices
        self.graph = [None] * self.V

        # 在無(wú)向圖中添加邊的函數(shù)

    def add_edge(self, source, destination):
        """
        添加邊緣
        :param source: 源頂點(diǎn)
        :param destination: 目標(biāo)頂點(diǎn)
        """

        # 將節(jié)點(diǎn)添加到源節(jié)點(diǎn)
        node = AdjNode(destination)
        node.next = self.graph[source]
        self.graph[source] = node

        # 如果無(wú)向圖，將源節(jié)點(diǎn)添加到目標(biāo)節(jié)點(diǎn)
        
        # 故意注釋這一行，方便理解
        #node = AdjNode(source)
        #node.next = self.graph[destination]
        #self.graph[destination] = node

    def print_graph(self):
        """
        打印圖標(biāo)的函數(shù)
        """
        for i in range(self.V):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")


# 主程序
if __name__ == "__main__":

    V = 5  # 頂點(diǎn)總數(shù)
    g = Graph(V)
    g.add_edge(0, 1)
    g.add_edge(0, 4)
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(1, 4)
    g.add_edge(2, 3)
    g.add_edge(3, 4)

    g.print_graph()

在上面的示例中，我們看到了Python graph class。我們已經(jīng)奠定了圖形類(lèi)的基礎(chǔ)。變量 V 包含一個(gè)整數(shù)，指定頂點(diǎn)總數(shù)。下面示例的代碼都會(huì)用到這個(gè)類(lèi)。

如何實(shí)現(xiàn)廣度優(yōu)先遍歷

給定一個(gè)表示為鄰接列表和起始頂點(diǎn)的圖，代碼應(yīng)該輸出一個(gè)字符串，其中包含以正確的遍歷順序列出的圖的頂點(diǎn)。當(dāng)從起始頂點(diǎn)遍歷圖形時(shí)，將首先打印每個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)，然后是左子節(jié)點(diǎn)。

為了解決這個(gè)問(wèn)題，前面已經(jīng)實(shí)現(xiàn)了 Graph 類(lèi)。

輸入：表示為鄰接列表和起始頂點(diǎn)的圖。

輸出：一個(gè)字符串，其中包含以正確的遍歷順序列出的圖的頂點(diǎn)。

示例輸出：

result = "02143" 
or
result = "01234"

在開(kāi)始實(shí)施之前，先看一下并設(shè)計(jì)一個(gè)分步算法。首先嘗試自己解決。如果遇到困難，可以隨時(shí)參考解決方案部分提供的解決方案。

bfs：

def bfs(graph, source):
    """
    打印圖的 BFS 的函數(shù)
    :param graph: 圖表
    :param source: 起始頂點(diǎn)
    :return:
    """

    # 寫(xiě)你的代碼
    pass

解決方案

bfs：

def bfs(my_graph, source):
    """
    打印圖的 BFS 函數(shù)
    :param graph: 圖表
    :param source: 起始頂點(diǎn)
    :return:
    """
    
    # 將所有的頂點(diǎn)標(biāo)識(shí)為未訪問(wèn)過(guò)
    visited = [False] * (len(my_graph.graph))

    # 創(chuàng)建 BFS 隊(duì)列
    queue = []

    # 結(jié)果字符串
    result = ""

    # 將源節(jié)點(diǎn)表示為 訪問(wèn)過(guò)并將其排入隊(duì)列
    queue.append(source)
    visited[source] = True

    while queue:

        # 經(jīng)一個(gè)頂點(diǎn)重隊(duì)列中取出
        # 排隊(duì)并打印
        source = queue.pop(0)
        result += str(source)

        # 取出相鄰的頂點(diǎn)
        # 出對(duì)的頂點(diǎn)源，
        #如果一個(gè)相鄰的還沒(méi)有訪問(wèn)過(guò)，那么標(biāo)記一下
        # 訪問(wèn)過(guò)并將其排入隊(duì)列
        while my_graph.graph[source] is not None:
            data = my_graph.graph[source].vertex
            if not visited[data]:
                queue.append(data)
                visited[data] = True
            my_graph.graph[source] = my_graph.graph[source].next

    return result


# 主要測(cè)試上面的程序
if __name__ == "__main__":
    
    V = 5
    g = Graph(V)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 3)
    g.add_edge(1, 4)

    print(bfs(g, 0))

我們從選定的節(jié)點(diǎn)開(kāi)始，逐層遍歷圖。探索所有鄰居節(jié)點(diǎn)。然后，我們進(jìn)入下一個(gè)級(jí)別。我們水平遍歷圖表，也就是每一層。

圖表可能包含循環(huán)。為了避免再次處理同一節(jié)點(diǎn)，我們可以使用布爾數(shù)組來(lái)標(biāo)記訪問(wèn)過(guò)的數(shù)組?？梢允褂藐?duì)列來(lái)存儲(chǔ)節(jié)點(diǎn)并將其標(biāo)記為已訪問(wèn)。隊(duì)列應(yīng)遵循先進(jìn)先出（FIFO）排隊(duì)方法。

如何實(shí)現(xiàn)深度優(yōu)先遍歷

在這個(gè)問(wèn)題中，你必須實(shí)現(xiàn)深度優(yōu)先遍歷。為了解決這個(gè)問(wèn)題，之前實(shí)現(xiàn)的圖類(lèi)已經(jīng)提供了。

輸入：表示為鄰接列表和起始頂點(diǎn)的圖。

輸出：一個(gè)字符串，其中包含以正確的遍歷順序列出的圖的頂點(diǎn)。

示例輸出：

result = "01342" 
or
result = "02143"

在開(kāi)始實(shí)施之前，先看一下并設(shè)計(jì)一個(gè)分步算法。首先嘗試自己解決。如果遇到困難，可以隨時(shí)參考解決方案部分提供的解決方案。

dfs：

def dfs(graph, source):
    """
    打印圖的 DFS 的函數(shù)
    :param graph: 圖表
    :param source: 起始頂點(diǎn)
    :return:
    """
    
    # 在這里寫(xiě)下你的代碼!
    pass

解決方案

dfs：

def dfs(my_graph, source):
    """
    打印圖的DFS的函數(shù)
    :param graph: 圖表
    :param source: 起始頂點(diǎn)
    :return: 以字符串形式返回遍歷結(jié)果
    """
    
    # 將所有頂點(diǎn)標(biāo)記為未訪問(wèn)過(guò)
    visited = [False] * (len(my_graph.graph))

    # 創(chuàng)建 DFS 堆棧
    stack = []

    # 結(jié)果字符串
    result = ""

    # 拼接字符
    stack.append(source)

    while stack:

        # 從堆棧中彈出一個(gè)頂點(diǎn)
        source = stack.pop()
        
        if not visited[source]:
            result += str(source)
            visited[source] = True

        # 獲取彈出頂點(diǎn)源的所有相鄰頂點(diǎn)
        # 如果相鄰的未必訪問(wèn)過(guò)，則將其壓入
        while my_graph.graph[source] is not None:
            data = my_graph.graph[source].vertex
            if not visited[data]:
                stack.append(data)
            my_graph.graph[source] = my_graph.graph[source].next

    return result


# 主程序運(yùn)行
if __name__ == "__main__":
    
    V = 5
    g = Graph(V)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 3)
    g.add_edge(1, 4)

    print(dfs(g, 0))

深度優(yōu)先圖算法利用了回溯的思想。這里的“回溯”是指只要當(dāng)前路徑上沒(méi)有更多的節(jié)點(diǎn)，就向前移動(dòng)，然后在同一條路徑上向后移動(dòng)，尋找要遍歷的節(jié)點(diǎn)。

如何去除邊緣

在此問(wèn)題中，必須實(shí)現(xiàn)remove_edge以源和目標(biāo)作為參數(shù)的函數(shù)。如果兩者之間存在邊，則應(yīng)將其刪除。

輸入：圖形、源（整數(shù)）和目標(biāo)（整數(shù)）。

輸出：對(duì)圖進(jìn)行 BFS 遍歷，并刪除源和目標(biāo)之間的邊。

首先，在開(kāi)始實(shí)施之前仔細(xì)研究這個(gè)問(wèn)題并設(shè)計(jì)一個(gè)分步算法。

remove_edge：

def remove_edge(graph, source, destination):
    """
    刪除邊緣函數(shù)
    :param graph: 圖表
    :param source: 源頂點(diǎn)
    :param destination: 目標(biāo)頂點(diǎn)
    """

    # 寫(xiě)代碼
    pass

解決方案

如果熟悉的話，這個(gè)解決方案與鏈表中的刪除非常相似。

我們的頂點(diǎn)存儲(chǔ)在一個(gè)鏈接列表中。首先，我們?cè)L問(wèn)source鏈表。如果源鏈表的頭節(jié)點(diǎn)持有要?jiǎng)h除的鍵，我們將頭向前移動(dòng)一步并返回圖。

如果要?jiǎng)h除的鍵位于鏈表的中間，我們會(huì)跟蹤前一個(gè)節(jié)點(diǎn)，并在目的地遇到時(shí)將前一個(gè)節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)連接起來(lái)。

總結(jié)

圖算法是用于解決圖（Graph）數(shù)據(jù)結(jié)構(gòu)中的各種問(wèn)題的算法，對(duì)廣度優(yōu)先和深度優(yōu)先做了一些示例，還有注釋?zhuān)覀兛梢运较戮毩?xí)一下。

圖算法能夠幫助我們理解和處理復(fù)雜的關(guān)系型數(shù)據(jù)，并在實(shí)際應(yīng)用中提供解決方案。