圖的遍歷-有解無憂

從圖中某一頂點出發訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這一程序就叫做圖的遍歷，

(1)深度優先遍歷

深度優先遍歷類似于數的先序遍歷，是樹的先序遍歷的推廣，

從圖中某個頂點v出發，訪問v，

找到剛訪問過得頂點的第一個未被訪問的鄰接點，訪問該頂點，以該頂點為新頂點，重復此步驟，直至剛訪問的頂點沒有未被訪問的鄰接點為止，

回傳前一個訪問過得且扔有未被訪問的鄰接點的頂點，找到該頂點的下一個未被訪問的鄰接點，訪問該頂點，

重復步驟2，3，直至圖中所有頂點都被訪問過，

深度優先遍歷演算法的實作

為了在遍歷程序中便于區分頂點是否已經被訪問，需附設訪問標志組visited,其初值為false，一旦某個頂點被訪問，則其相應的分量置為true，

# python代碼實作鄰接矩陣的深度優先遍歷
class MGraph():
    def __init__(self):
        self.vertex = []
        self.matrix = []
        self.numNodes = 0
        self.numEdges = 0
        self.visited = []

    def createMGraph(self):
        """創建無向圖的鄰接矩陣表示"""
        self.numNodes = int(input("請輸入頂點數："))
        self.numEdges = int(input("請輸入邊數："))
        for i in range(self.numNodes):
            self.vertex.append(input("請輸入一個頂點："))

        for i in range(self.numNodes):
            self.matrix.append([])
            for j in range(self.numNodes):
                self.matrix[i].append(0)  # 初始化鄰接矩陣

        for k in range(self.numEdges):  # 讀入numEdges條邊，建立鄰接矩陣
            i = int(input("請輸入邊(vi,vj)上的下標i:"))
            j = int(input("請輸入邊(vi,vj)上的下標j:"))
            self.matrix[i][j] = 1
            self.matrix[j][i] = self.matrix[i][j]  # 因為是無向網圖，矩陣對稱

    def viewMGraphStruct(self):
        print(self.matrix)

    def DFS(self, i):
        """零階矩陣的深度優先遞回演算法"""
        self.visited[i] = True
        print(self.vertex[i])
        for j in range(self.numNodes):
            if self.matrix[i][j] == 1 and not self.visited[j]:
                self.DFS(j)

    def DFSTraverse(self):
        """鄰接矩陣的深度優先遍歷操作"""
        self.visited = [False for i in range(self.numNodes)]
        for i in range(self.numNodes):
            if not self.visited[i]:  # 對未訪問過的頂點呼叫DFS，若為連通圖僅執行一次
                self.DFS(i)


if __name__ == '__main__':
    G = MGraph()
    G.createMGraph()
    G.viewMGraphStruct()
    print("深度優先遍歷結果如下：")
    G.DFSTraverse()

此代碼包含了無向圖的鄰接矩陣存盤方式的創建，以及深度優先遍歷演算法,既能遍歷連通圖也能遍歷非聯通圖，

以上面的圖為例，代碼運行后，我們輸入圖的資訊創建圖，生成的鄰接矩陣以及深度優先遍歷結果如下：

鄰接矩陣：
[[0, 1, 0, 0, 0, 1, 0, 0, 0], 
[1, 0, 1, 0, 0, 0, 1, 0, 1], 
[0, 1, 0, 1, 0, 0, 0, 0, 1], 
[0, 0, 1, 0, 1, 0, 1, 1, 1], 
[0, 0, 0, 1, 0, 1, 0, 1, 0], 
[1, 0, 0, 0, 1, 0, 1, 0, 0], 
[0, 1, 0, 1, 0, 1, 0, 1, 0], 
[0, 0, 0, 1, 1, 0, 1, 0, 0], 
[0, 1, 1, 1, 0, 0, 0, 0, 0]]

深度優先遍歷結果如下：
A
B
C
D
E
F
G
H
I

python代碼實作鄰接表的深度優先遍歷：

class Vertex(object):
    """創建Vertex類，用來存放頂點資訊（包括data和firstEdge）"""

    def __init__(self, data=https://www.cnblogs.com/minqiliang/archive/2022/10/28/None):
        self.data = data
        self.firstEdge = None


class EdgeNode(object):""" 創建Edge類，用來存放邊資訊（包括adjVex和next）；"""

    def __init__(self, adjVex):
        self.adjVex = adjVex
        self.next = None


class ALGraph():
    """無向圖類"""

    def __init__(self):
        self.numNodes = 0
        self.numEdges = 0
        self.adjList = []
        self.visited = []

    def createALGraph(self):
        self.numNodes = int(input("輸入頂點數："))
        self.numEdges = int(input("輸入邊數："))
        for i in range(self.numNodes):  # 讀入頂點資訊，建立頂點表
            v = Vertex()
            self.adjList.append(v)
            self.adjList[i].data = https://www.cnblogs.com/minqiliang/archive/2022/10/28/input("請輸入頂點資料：")

        for k in range(self.numEdges):  # 建立邊表
            i = int(input("請輸入邊(vi,vj)上的下標i:"))
            j = int(input("請輸入邊(vi,vj)上的下標j:"))
            e = EdgeNode(j)  # 實體化邊節點
            e.next = self.adjList[i].firstEdge  # 將e的指標指向當前頂點指向的節點
            self.adjList[i].firstEdge = e  # 將當前頂點的指標指向e
            e = EdgeNode(i)  # 實體化邊節點
            e.next = self.adjList[j].firstEdge  # 將e的指標指向當前頂點指向的節點
            self.adjList[j].firstEdge = e  # 將當前頂點的指標指向e

    def DFS(self, i):
        """鄰階表的深度優先遞回演算法"""
        self.visited[i] = True
        print(self.adjList[i].data)
        p = self.adjList[i].firstEdge
        while p:
            if not self.visited[p.adjVex]:
                self.DFS(p.adjVex)
            p = p.next

    def DFSTraverse(self):
        """鄰接表的深度優先遍歷操作"""
        self.visited = [False for i in range(self.numNodes)]
        for i in range(self.numNodes):
            if not self.visited[i]:  # 對未訪問過的頂點呼叫DFS，若為聯通圖僅執行一次
                self.DFS(i)


if __name__ == '__main__':
    G = ALGraph()
    G.createALGraph()
    G.DFSTraverse()

遍歷結果如下：

A
F
G
H
E
D
I
C
B

(2)廣度優先遍歷

圖的廣度優先遍歷就類似于樹的層序遍歷，

從圖中某個頂點v出發，訪問v，

依次訪問v的各個未被訪問過得鄰接點，

分別從這些鄰接點出發依次訪問他們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，重復步驟3，直至圖中所有已被訪問的頂點的鄰接點都被訪問到，

廣度優先遍歷連通圖

從圖中某個頂點v出發，訪問v，并置visited[v]的值為true，然后將v進隊，

只要佇列不為空，則重復下述操作：

隊頭頂點u出隊，

依次檢查u的所有鄰接點w，如果visited[w]的值為false，則訪問w,并置visited[w]的值為true，然后將w進隊，

python實作鄰接矩陣的廣度優先遍歷：

class Queue():
    """佇列類"""
    def __init__(self):
        self.queue = []

    def Enqueue(self, data):
        """入隊操作"""
        self.queue.append(data)

    def Dequeue(self):
        """出隊操作"""
        return self.queue.pop(0)

    def isEmpty(self):
        """判斷佇列是否為空"""
        if len(self.queue) == 0:
            return True
        else:
            return False


class MGraph():
    def __init__(self):
        self.vertex = []
        self.matrix = []
        self.numNodes = 0
        self.numEdges = 0
        self.visited = []

    def createMGraph(self):
        """創建無向圖的鄰接矩陣表示"""
        self.numNodes = int(input("請輸入頂點數："))
        self.numEdges = int(input("請輸入邊數："))
        for i in range(self.numNodes):
            self.vertex.append(input("請輸入一個頂點："))

        for i in range(self.numNodes):
            self.matrix.append([])
            for j in range(self.numNodes):
                self.matrix[i].append(0)  # 初始化鄰接矩陣

        for k in range(self.numEdges):  # 讀入numEdges條邊，建立鄰接矩陣
            i = int(input("請輸入邊(vi,vj)上的下標i:"))
            j = int(input("請輸入邊(vi,vj)上的下標j:"))
            self.matrix[i][j] = 1
            self.matrix[j][i] = self.matrix[i][j]  # 因為是無向網圖，矩陣對稱

    def viewMGraphStruct(self):
        print(self.matrix)

    def BFSTraverse(self):
        """鄰接矩陣的廣度優先遍歷操作"""
        self.visited = [False for i in range(self.numNodes)]  # 初始化所有頂點狀態為未訪問狀態
        Q = Queue()  # 實體化佇列Q
        for i in range(self.numNodes):
            if not self.visited[i]:  # 對未訪問過的頂點進行處理
                self.visited[i] = True  # 將當前頂點標記為已訪問
                print(self.vertex[i])  # 列印此頂點
                Q.Enqueue(i)  # 將此頂點入佇列
                while not Q.isEmpty():  # 若佇列不為空
                    i = Q.Dequeue()  # 將隊首元素出佇列，賦值給i
                    for j in range(self.numNodes):
                        if self.matrix[i][j] == 1 and not self.visited[j]:  # 判斷其他頂點，若與當前頂點存在邊且未訪問過
                            self.visited[j] = True  # 將找到的此頂點標記為已訪問
                            print(self.vertex[j])  # 列印此頂點
                            Q.Enqueue(j)  # 將此頂點入佇列


if __name__ == '__main__':
    G = MGraph()
    G.createMGraph()
    G.viewMGraphStruct()
    print("廣度優先遍歷結果如下：")
    G.BFSTraverse()

鄰接矩陣如下：

[[0, 1, 0, 0, 0, 1, 0, 0, 0], 
[1, 0, 1, 0, 0, 0, 1, 0, 1], 
[0, 1, 0, 1, 0, 0, 0, 0, 1], 
[0, 0, 1, 0, 1, 0, 1, 1, 1], 
[0, 0, 0, 1, 0, 1, 0, 1, 0], 
[1, 0, 0, 0, 1, 0, 1, 0, 0], 
[0, 1, 0, 1, 0, 1, 0, 1, 0], 
[0, 0, 0, 1, 1, 0, 1, 0, 0], 
[0, 1, 1, 1, 0, 0, 0, 0, 0]]

遍歷結果如下：

A
B
F
C
G
I
E
D
H

python實作鄰接表的廣度優先遍歷：

class Queue():
    """佇列類"""

    def __init__(self):
        self.queue = []

    def Enqueue(self, data):
        """入隊操作"""
        self.queue.append(data)

    def Dequeue(self):
        """出隊操作"""
        return self.queue.pop(0)

    def isEmpty(self):
        """判斷佇列是否為空"""
        if len(self.queue) == 0:
            return True
        else:
            return False


class Vertex(object):
    """創建Vertex類，用來存放頂點資訊（包括data和firstEdge）"""

    def __init__(self, data=https://www.cnblogs.com/minqiliang/archive/2022/10/28/None):
        self.data = data
        self.firstEdge = None


class EdgeNode(object):""" 創建Edge類，用來存放邊資訊（包括adjVex和next）；"""

    def __init__(self, adjVex):
        self.adjVex = adjVex
        self.next = None


class ALGraph():
    """無向圖類"""

    def __init__(self):
        self.numNodes = 0
        self.numEdges = 0
        self.adjList = []
        self.visited = []

    def createALGraph(self):
        self.numNodes = int(input("輸入頂點數："))
        self.numEdges = int(input("輸入邊數："))
        for i in range(self.numNodes):  # 讀入頂點資訊，建立頂點表
            v = Vertex()
            self.adjList.append(v)
            self.adjList[i].data = https://www.cnblogs.com/minqiliang/archive/2022/10/28/input("請輸入頂點資料：")

        for k in range(self.numEdges):  # 建立邊表
            i = int(input("請輸入邊(vi,vj)上的下標i:"))
            j = int(input("請輸入邊(vi,vj)上的下標j:"))
            e = EdgeNode(j)  # 實體化邊節點
            e.next = self.adjList[i].firstEdge  # 將e的指標指向當前頂點指向的節點
            self.adjList[i].firstEdge = e  # 將當前頂點的指標指向e
            e = EdgeNode(i)  # 實體化邊節點
            e.next = self.adjList[j].firstEdge  # 將e的指標指向當前頂點指向的節點
            self.adjList[j].firstEdge = e  # 將當前頂點的指標指向e

    def BFSTraverse(self):
        """鄰接表的深度優先遍歷操作"""
        self.visited = [False for i in range(self.numNodes)]
        Q = Queue()
        for i in range(self.numNodes):
            if not self.visited[i]:  # 對未訪問過的頂點進行處理
                self.visited[i] = True  # 將當前頂點標記為已訪問
                print(self.adjList[i].data)  # 列印此頂點
                Q.Enqueue(i)  # 將此頂點入佇列
                while not Q.isEmpty():  # 若佇列不為空
                    i = Q.Dequeue()  # 將隊首元素出佇列，賦值給i
                    p = self.adjList[i].firstEdge  # 找到當前頂點的邊表鏈的表頭指標
                    while p:
                        if not self.visited[p.adjVex]:  # 若此頂點未被訪問
                            self.visited[p.adjVex] = True
                            print(self.adjList[p.adjVex].data)
                            Q.Enqueue(p.adjVex)  # 將此頂點入佇列
                        p = p.next  # 指標指向下一鄰接點


if __name__ == '__main__':
    G = ALGraph()
    G.createALGraph()
    G.BFSTraverse()

遍歷結果：

A
F
B
G
E
I
C
H
D

本文部分概念內容來自：https://www.jianshu.com/p/d9ca383e2bd8，其余均為自創，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/522933.html

標籤：其他

上一篇：Hugging Face發布diffuser模型AI繪畫庫初嘗鮮！

下一篇：軟體要想做的好，測驗必定少不了