Python圖

圖是一組對象通過鏈接連接的一組對象的圖形表示。 互連對象由稱爲頂點的點表示,連接頂點的鏈接稱爲邊。 在這裏詳細描述了與圖相關的各種術語和功能。 在本章中,我們將演示如何使用python程序創建圖並向其添加各種數據元素。 以下是在圖表上執行的基本操作。

  • 顯示圖形頂點
  • 顯示圖形邊緣
  • 添加一個頂點
  • 添加邊緣
  • 創建一個圖

可以使用python字典數據類型輕鬆呈現圖。 我們將頂點表示爲字典的關鍵字,頂點之間的連接也稱爲邊界,作爲字典中的值。

看看下面的圖 -

Python圖

在上面的圖中 -

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

可以在下面的python程序中展示這個圖 -

# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
          "b" : ["a", "d"],
          "c" : ["a", "d"],
          "d" : ["e"],
          "e" : ["d"]
         }

# Print the graph
print(graph)

當上面的代碼被執行時,它會產生以下結果 -

{'a': ['b', 'c'], 'b': ['a', 'd'], 'c': ['a', 'd'], 'd': ['e'], 'e': ['d']}

顯示圖的頂點

要顯示圖頂點,簡單地找到圖字典的關鍵字,使用keys()方法。

class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = []
        self.gdict = gdict

# Get the keys of the dictionary
    def getVertices(self):
        return list(self.gdict.keys())

# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
                "b" : ["a", "d"],
                "c" : ["a", "d"],
                "d" : ["e"],
                "e" : ["d"]
                }

g = graph(graph_elements)

print(g.getVertices())

執行上面示例代碼,得到以下結果 -

['a', 'b', 'c', 'd', 'e']

顯示圖的邊緣

尋找圖邊緣比頂點少一些,因爲必須找到每對頂點之間有一個邊緣的頂點。 因此,創建一個空邊列表,然後迭代與每個頂點關聯的邊值。 一個列表形成了包含從頂點找到的不同組的邊。

[{'a', 'b'}, {'c', 'a'}, {'d', 'b'}, {'c', 'd'}, {'d', 'e'}]

添加一個頂點

添加一個頂點很簡單,直接添加另一個鍵到圖字典。

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

    def getVertices(self):
        return list(self.gdict.keys())

# Add the vertex as a key
    def addVertex(self, vrtx):
       if vrtx not in self.gdict:
            self.gdict[vrtx] = []

# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
                "b" : ["a", "d"],
                "c" : ["a", "d"],
                "d" : ["e"],
                "e" : ["d"]
                }

g = graph(graph_elements)

g.addVertex("f")

print(g.getVertices())

執行上面示例代碼,得到以下結果 -

['a', 'b', 'c', 'd', 'e', 'f']

添加邊

將邊添加到現有圖, 涉及將新頂點視爲元組並驗證邊是否已經存在。 如果不存在,則添加邊緣。

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

    def edges(self):
        return self.findedges()
# Add the new edge

    def AddEdge(self, edge):
        edge = set(edge)
        (vrtx1, vrtx2) = tuple(edge)
        if vrtx1 in self.gdict:
            self.gdict[vrtx1].append(vrtx2)
        else:
            self.gdict[vrtx1] = [vrtx2]

# List the edge names
    def findedges(self):
        edgename = []
        for vrtx in self.gdict:
            for nxtvrtx in self.gdict[vrtx]:
                if {nxtvrtx, vrtx} not in edgename:
                    edgename.append({vrtx, nxtvrtx})
        return edgename

# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
                "b" : ["a", "d"],
                "c" : ["a", "d"],
                "d" : ["e"],
                "e" : ["d"]
                }

g = graph(graph_elements)
g.AddEdge({'a','e'})
g.AddEdge({'a','c'})
print(g.edges())

執行上面示例代碼,得到以下結果 -

[{'b', 'a'}, {'c', 'a'}, {'b', 'd'}, {'c', 'd'}, {'e', 'd'}, {'e', 'a'}]