Python 圖算法

圖在解決許多重要的數(shù)學(xué)難題中是非常有用的數(shù)據(jù)結(jié)構(gòu)。例如計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)浠蚍治龌瘜W(xué)化合物的分子結(jié)構(gòu)。它們還用于城市交通或路線規(guī)劃，甚至用于人類語(yǔ)言和語(yǔ)法。所有這些應(yīng)用程序都有使用它們的邊遍歷圖的共同挑戰(zhàn)，并確保圖的所有節(jié)點(diǎn)都被訪問(wèn)。有兩種常見(jiàn)的已建立的方法來(lái)進(jìn)行這種遍歷，下面將對(duì)其進(jìn)行描述。

深度優(yōu)先遍歷：

也稱為深度優(yōu)先搜索（DFS），該算法遍歷深度病房運(yùn)動(dòng)中的圖形，并使用堆棧記住在任何迭代中發(fā)生死角時(shí)開(kāi)始搜索的下一個(gè)頂點(diǎn)。我們使用設(shè)置的數(shù)據(jù)類型在python中實(shí)現(xiàn)DFS圖表，因?yàn)樗鼈兲峁┝烁櫾L問(wèn)和未訪問(wèn)節(jié)點(diǎn)所需的功能。

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(chǎn)生以下結(jié)果 -

a b d e c

廣度第一次遍歷

也稱為寬度優(yōu)先搜索（BFS），該算法遍歷圖的寬度運(yùn)動(dòng)，并使用隊(duì)列記住在任何迭代中發(fā)生死角時(shí)開(kāi)始搜索的下一個(gè)頂點(diǎn)。請(qǐng)?jiān)L問(wèn)我們網(wǎng)站的鏈接，了解BFS圖表步驟的詳細(xì)信息。

我們使用之前討論的隊(duì)列數(shù)據(jù)結(jié)構(gòu)在python中實(shí)現(xiàn)BFS。當(dāng)我們繼續(xù)訪問(wèn)相鄰的未訪問(wèn)節(jié)點(diǎn)并繼續(xù)將其添加到隊(duì)列中時(shí)。然后，我們開(kāi)始只出現(xiàn)沒(méi)有未訪問(wèn)節(jié)點(diǎn)的節(jié)點(diǎn)。當(dāng)沒(méi)有下一個(gè)相鄰節(jié)點(diǎn)被訪問(wèn)時(shí)，我們停止程序。

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(chǎn)生以下結(jié)果 -

a c b d e