跑分安卓第一！Redmi K60至尊版8月發(fā)布！盧偉冰：目標(biāo)年度性能之王
8月5日消息，Redmi K60至尊版將于8月發(fā)布，在此前舉行的戰(zhàn)略發(fā)布會上，官方該機(jī)將搭載搭載天璣9200+處理器，安兔兔V10跑分超177萬分，是目前安卓陣營最高的分?jǐn)?shù)
算法是編碼面試中最常見的主題之一。為了在面試中獲得優(yōu)勢，非常熟悉頂級算法及其實現(xiàn)非常重要。
在次此篇文章中，我們將探索圖算法。我們將從圖論和圖算法的介紹開始。接下來，我們將學(xué)習(xí)如何實現(xiàn)圖。
今天，我們將學(xué)習(xí)：
算法是使用明確定義或最佳步驟數(shù)解決問題的數(shù)學(xué)過程。它只是用于完成特定工作的基本技術(shù)。
圖是一種抽象符號，用于表示所有對象對之間的連接。圖是廣泛使用的數(shù)學(xué)結(jié)構(gòu)，由兩個基本組成部分可視化：節(jié)點(diǎn)和邊。
圖算法用于解決將圖表示為網(wǎng)絡(luò)的問題，例如航空公司航班、互聯(lián)網(wǎng)如何連接或微信、QQ、微博上的社交網(wǎng)絡(luò)連接。它們在NLP和機(jī)器學(xué)習(xí)中也很流行，用于形成網(wǎng)絡(luò)。
一些頂級的圖形算法包括：
雖然圖是離散數(shù)學(xué)不可或缺的一部分，但它們在計算機(jī)科學(xué)和編程中也有實際用途，包括以下內(nèi)容：
由 G 表示的圖由一組頂點(diǎn) (V)或在邊 (E)處鏈接的節(jié)點(diǎn)表示。邊的數(shù)量取決于頂點(diǎn)。邊緣可以是有向的或無向的。
在有向圖中，節(jié)點(diǎn)沿一個方向鏈接。這里的邊顯示了一種單向關(guān)系。
在無向圖中，邊是雙向的，顯示出雙向關(guān)系。
示例：無向圖的一個很好的用例是微信好友建議算法。用戶（節(jié)點(diǎn)）有一個邊緣運(yùn)行到朋友 A（另一個節(jié)點(diǎn)），而朋友 A 又連接（或有一個邊緣運(yùn)行）到朋友 B。然后將朋友 B 推薦給用戶。
還有許多其他復(fù)雜類型的圖屬于不同的子集。例如，當(dāng)每個頂點(diǎn)都可以從其他每個頂點(diǎn)到達(dá)時，有向圖就具有強(qiáng)連通分量。
頂點(diǎn)是多條線相交的點(diǎn)。它也稱為節(jié)點(diǎn)。
邊是一個數(shù)學(xué)術(shù)語，用于表示連接兩個頂點(diǎn)的線。許多邊可以由單個頂點(diǎn)形成。然而，沒有頂點(diǎn)，就無法形成邊。每條邊必須有一個起始和結(jié)束頂點(diǎn)。
圖中的路徑G=( V ,E ）是頂點(diǎn) v1, v2, …, vk 的序列，其屬性是之間有邊 vi 和 vi +1。我們說路徑從v1到vk 。
序列 6,4,5,1,26,4,5,1,2 定義從節(jié)點(diǎn) 6 到節(jié)點(diǎn) 2 的路徑。
類似地，可以通過遍歷圖的邊來創(chuàng)建其他路徑。如果路徑的頂點(diǎn)全部不同，則路徑很簡單。
行走是路徑，但它們不需要一系列不同的頂點(diǎn)。
如果對于每對頂點(diǎn)，則圖是連通的v和v，有一條路徑從v到v。
循環(huán)是一條路徑 v1, v2, …, vk，滿足以下條件：
樹是不包含環(huán)的連通圖。
在圖中，如果從頂點(diǎn)到自身繪制一條邊，則稱為環(huán)。在圖中，V 是一個頂點(diǎn)，其邊 (V, V) 形成一個環(huán)。
在我們繼續(xù)使用圖算法解決問題之前，首先了解如何在代碼中表示圖非常重要。圖可以表示為鄰接矩陣或鄰接列表。
鄰接矩陣是由圖頂點(diǎn)標(biāo)記的方陣，用于表示有限圖。矩陣的條目指示頂點(diǎn)對在圖中是否相鄰。
在鄰接矩陣表示中，需要迭代所有節(jié)點(diǎn)來識別節(jié)點(diǎn)的鄰居。
a b c d ea 1 1 - - -b - - 1 - -c - - - 1 -d - 1 1 - -鄰接表用于表示有限圖。鄰接列表表示允許輕松地遍歷節(jié)點(diǎn)的鄰居。列表中的每個索引代表頂點(diǎn)，與該索引鏈接的每個節(jié)點(diǎn)代表其相鄰頂點(diǎn)。
1 a -> { a b }2 b -> { c }3 c -> { d }4 d -> { b c }對于下面的基圖類，我們將使用鄰接列表實現(xiàn)，因為它對于本文后面的算法解決方案執(zhí)行得更快。
我們的圖實現(xiàn)的要求相當(dāng)簡單。我們需要兩個數(shù)據(jù)成員：圖中頂點(diǎn)的總數(shù)和存儲相鄰頂點(diǎn)的列表。我們還需要一種添加邊或一組邊的方法。
class AdjNode: """ 表示節(jié)點(diǎn)鄰接表的 類 """ def __init__(self, data): """ 構(gòu)造函數(shù) :參數(shù)數(shù)據(jù) : 頂點(diǎn) """ self.vertex = data self.next = Noneclass Graph: """ 圖類 ADT """ def __init__(self, vertices): """ 構(gòu)造函數(shù) :param vertices : 圖中的總頂點(diǎn)數(shù) """ self.V = vertices self.graph = [None] * self.V # 在無向圖中添加邊的函數(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 # 如果無向圖，將源節(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)奠定了圖形類的基礎(chǔ)。變量 V 包含一個整數(shù)，指定頂點(diǎn)總數(shù)。下面示例的代碼都會用到這個類。
給定一個表示為鄰接列表和起始頂點(diǎn)的圖，代碼應(yīng)該輸出一個字符串，其中包含以正確的遍歷順序列出的圖的頂點(diǎn)。當(dāng)從起始頂點(diǎn)遍歷圖形時，將首先打印每個節(jié)點(diǎn)的右子節(jié)點(diǎn)，然后是左子節(jié)點(diǎn)。
為了解決這個問題，前面已經(jīng)實現(xiàn)了 Graph 類。
輸入：表示為鄰接列表和起始頂點(diǎn)的圖。
輸出：一個字符串，其中包含以正確的遍歷順序列出的圖的頂點(diǎn)。
示例輸出：
result = "02143" orresult = "01234"在開始實施之前，先看一下并設(shè)計一個分步算法。首先嘗試自己解決。如果遇到困難，可以隨時參考解決方案部分提供的解決方案。
bfs：
def bfs(graph, source): """ 打印圖的 BFS 的函數(shù) :param graph: 圖表 :param source: 起始頂點(diǎn) :return: """ # 寫你的代碼 passbfs：
def bfs(my_graph, source): """ 打印圖的 BFS 函數(shù) :param graph: 圖表 :param source: 起始頂點(diǎn) :return: """ # 將所有的頂點(diǎn)標(biāo)識為未訪問過 visited = [False] * (len(my_graph.graph)) # 創(chuàng)建 BFS 隊列 queue = [] # 結(jié)果字符串 result = "" # 將源節(jié)點(diǎn)表示為 訪問過并將其排入隊列 queue.append(source) visited[source] = True while queue: # 經(jīng)一個頂點(diǎn)重隊列中取出 # 排隊并打印 source = queue.pop(0) result += str(source) # 取出相鄰的頂點(diǎn) # 出對的頂點(diǎn)源， #如果一個相鄰的還沒有訪問過，那么標(biāo)記一下 # 訪問過并將其排入隊列 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# 主要測試上面的程序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)開始，逐層遍歷圖。探索所有鄰居節(jié)點(diǎn)。然后，我們進(jìn)入下一個級別。我們水平遍歷圖表，也就是每一層。
圖表可能包含循環(huán)。為了避免再次處理同一節(jié)點(diǎn)，我們可以使用布爾數(shù)組來標(biāo)記訪問過的數(shù)組。可以使用隊列來存儲節(jié)點(diǎn)并將其標(biāo)記為已訪問。隊列應(yīng)遵循先進(jìn)先出（FIFO）排隊方法。
在這個問題中，你必須實現(xiàn)深度優(yōu)先遍歷。為了解決這個問題，之前實現(xiàn)的圖類已經(jīng)提供了。
輸入：表示為鄰接列表和起始頂點(diǎn)的圖。
輸出：一個字符串，其中包含以正確的遍歷順序列出的圖的頂點(diǎn)。
示例輸出：
result = "01342" orresult = "02143"在開始實施之前，先看一下并設(shè)計一個分步算法。首先嘗試自己解決。如果遇到困難，可以隨時參考解決方案部分提供的解決方案。
dfs：
def dfs(graph, source): """ 打印圖的 DFS 的函數(shù) :param graph: 圖表 :param source: 起始頂點(diǎn) :return: """ # 在這里寫下你的代碼! passdfs：
def dfs(my_graph, source): """ 打印圖的DFS的函數(shù) :param graph: 圖表 :param source: 起始頂點(diǎn) :return: 以字符串形式返回遍歷結(jié)果 """ # 將所有頂點(diǎn)標(biāo)記為未訪問過 visited = [False] * (len(my_graph.graph)) # 創(chuàng)建 DFS 堆棧 stack = [] # 結(jié)果字符串 result = "" # 拼接字符 stack.append(source) while stack: # 從堆棧中彈出一個頂點(diǎn) source = stack.pop() if not visited[source]: result += str(source) visited[source] = True # 獲取彈出頂點(diǎn)源的所有相鄰頂點(diǎn) # 如果相鄰的未必訪問過，則將其壓入 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)前路徑上沒有更多的節(jié)點(diǎn)，就向前移動，然后在同一條路徑上向后移動，尋找要遍歷的節(jié)點(diǎn)。
在此問題中，必須實現(xiàn)remove_edge以源和目標(biāo)作為參數(shù)的函數(shù)。如果兩者之間存在邊，則應(yīng)將其刪除。
輸入：圖形、源（整數(shù)）和目標(biāo)（整數(shù)）。
輸出：對圖進(jìn)行 BFS 遍歷，并刪除源和目標(biāo)之間的邊。
首先，在開始實施之前仔細(xì)研究這個問題并設(shè)計一個分步算法。
remove_edge：
def remove_edge(graph, source, destination): """ 刪除邊緣函數(shù) :param graph: 圖表 :param source: 源頂點(diǎn) :param destination: 目標(biāo)頂點(diǎn) """ # 寫代碼 pass如果熟悉的話，這個解決方案與鏈表中的刪除非常相似。
我們的頂點(diǎn)存儲在一個鏈接列表中。首先，我們訪問source鏈表。如果源鏈表的頭節(jié)點(diǎn)持有要刪除的鍵，我們將頭向前移動一步并返回圖。
如果要刪除的鍵位于鏈表的中間，我們會跟蹤前一個節(jié)點(diǎn)，并在目的地遇到時將前一個節(jié)點(diǎn)與下一個節(jié)點(diǎn)連接起來。
圖算法是用于解決圖（Graph）數(shù)據(jù)結(jié)構(gòu)中的各種問題的算法，對廣度優(yōu)先和深度優(yōu)先做了一些示例，還有注釋，我們可以私下練習(xí)一下。
圖算法能夠幫助我們理解和處理復(fù)雜的關(guān)系型數(shù)據(jù)，并在實際應(yīng)用中提供解決方案。
本文鏈接：http://www.www897cc.com/showinfo-26-17169-0.html如何使用圖算法，幫助我們理解和處理復(fù)雜的關(guān)系型數(shù)據(jù)
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： RabbitMQ的四種交換機(jī)詳解
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號