有向圖的介紹

引入

• 在實(shí)際生活中,很多應(yīng)用相關(guān)的圖都是有方向性的,最直觀的就是網(wǎng)絡(luò),可以從A頁面通過鏈接跳轉(zhuǎn)到B頁面,那么a和b連接的方向是a->b,但不能說是b->a,此時(shí)我們就需要使用有向圖來解決這一類問題,它和我們之前學(xué)習(xí)的無向圖,最大的區(qū)別就在于連接是具有方向的,在代碼的處理上也會(huì)有很大的不同。

定義

• 有向圖（Digraph或Directed graph）是一副由一系列頂點(diǎn)和連接頂點(diǎn)之間的具有方向性的邊組成的圖
  
  這是一幅簡(jiǎn)單的有向圖示意，其中雙向箭頭的邊實(shí)際上是由兩條不同的邊組成的

有向圖的術(shù)語

• 出度:由某個(gè)頂點(diǎn)指出的邊的個(gè)數(shù)稱為該頂點(diǎn)的出度。
• 入度:指向某個(gè)頂點(diǎn)的邊的個(gè)數(shù)稱為該頂點(diǎn)的入度。
• 有向路徑:由一系列頂點(diǎn)組成,對(duì)于其中的每個(gè)頂點(diǎn)都存在一條有向邊,從它指向序列中的下一個(gè)頂點(diǎn)。
• 有向環(huán):至少含有一條邊,且起點(diǎn)和終點(diǎn)相同的有向路徑。

一副有向圖中兩個(gè)頂點(diǎn)v和w可能存在以下四種關(guān)系:

沒有邊相連;

存在從v到w的邊v- ->W;

存在從w到v的邊w- ->v;

既存在w到v的邊,也存在v到w的邊,即雙向連接;

有向圖的實(shí)現(xiàn)

屬性方法設(shè)計(jì)

類名：Edge

構(gòu)造方法__init__()中的屬性
num_vertices和num_edges分別代表要構(gòu)造的圖的頂點(diǎn)和邊的數(shù)量；adj_list是一個(gè)列表，其索引代表頂點(diǎn)，儲(chǔ)存的值是與索引對(duì)應(yīng)頂點(diǎn)相鄰的全部頂點(diǎn)

point_edge(x, y) 對(duì)傳入的兩個(gè)頂點(diǎn)x，y構(gòu)造一條邊：x→y

point_to_vertices(x) 獲取傳入的頂點(diǎn)x所有指出的頂點(diǎn)

reverse_digraph() 將當(dāng)前圖中的所有邊的方向反轉(zhuǎn)獲得一張反轉(zhuǎn)圖并返回

Python代碼實(shí)現(xiàn)

class Digraph:def __init__(self, num):self.num_vertices = numself.num_edges = 0self.adj_list = [[] for _ in range(num)]def count_vertices(self):return self.num_verticesdef count_edges(self):return self.num_edgesdef point_edge(self, x, y):"""Add an edge of vertex x: x --> y"""self.adj_list[x].append(y)def point_to_vertices(self, x):return self.adj_list[x]def reverse_digraph(self):rvs_digraph = Digraph(self.num_vertices)for index, queue in enumerate(self.adj_list):for v in queue:rvs_digraph.point_edge(v, index)return rvs_digraphif __name__ == '__main__':graph = Digraph(5)graph.point_edge(3, 0)graph.point_edge(0, 2)graph.point_edge(2, 0)graph.point_edge(2, 1)graph.point_edge(1, 0)graph.point_edge(1, 4)print(graph.point_to_vertices(1))print(graph.adj_list)rvs_graph = graph.reverse_digraph()print(rvs_graph.adj_list)

運(yùn)行結(jié)果

[0, 4] [[2], [0, 4], [0, 1], [0], []] [[1, 2, 3], [2], [0], [], [1]]

總結(jié)

以上是生活随笔為你收集整理的数据结构之图：有向图的介绍与实现，Python代码实现——25的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。