Python - Đồ thị

Đồ thị là một biểu diễn bằng hình ảnh của một tập hợp các đối tượng trong đó một số cặp đối tượng được nối với nhau bằng các liên kết. Các đối tượng liên kết được biểu diễn bằng các điểm được gọi là đỉnh và các liên kết nối các đỉnh được gọi là cạnh. Các thuật ngữ và chức năng khác nhau liên quan đến biểu đồ được mô tả rất chi tiết trong hướng dẫn của chúng tôi tại đây. Trong chương này, chúng ta sẽ xem cách tạo một biểu đồ và thêm các phần tử dữ liệu khác nhau vào nó bằng chương trình python. Sau đây là các hoạt động cơ bản chúng tôi thực hiện trên đồ thị.

  • Hiển thị các đỉnh đồ thị
  • Hiển thị các cạnh biểu đồ
  • Thêm một đỉnh
  • Thêm một cạnh
  • Tạo đồ thị

Có thể dễ dàng trình bày một biểu đồ bằng cách sử dụng các kiểu dữ liệu từ điển python. Chúng tôi biểu diễn các đỉnh là các khóa của từ điển và kết nối giữa các đỉnh còn được gọi là các cạnh là các giá trị trong từ điển.

Hãy xem biểu đồ sau:

Trong đồ thị trên

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

Chúng ta có thể trình bày biểu đồ này trong một chương trình python như bên dưới.

# 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)

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

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

Hiển thị các đỉnh đồ thị

Để hiển thị các đỉnh của đồ thị, chúng ta chỉ cần tìm các khóa của từ điển đồ thị. Chúng tôi sử dụng phương thức key ().

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())

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

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

Hiển thị các cạnh biểu đồ

Việc tìm các cạnh của đồ thị khó hơn một chút so với các đỉnh vì chúng ta phải tìm từng cặp đỉnh có một cạnh ở giữa chúng. Vì vậy, chúng tôi tạo một danh sách trống các cạnh sau đó lặp qua các giá trị cạnh được liên kết với mỗi đỉnh. Một danh sách được hình thành có chứa nhóm cạnh khác biệt được tìm thấy từ các đỉnh.

class graph:

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

    def edges(self):
        return self.findedges()
# Find the distinct list of edges

    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)

print(g.edges())

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

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

Thêm một đỉnh

Việc thêm một đỉnh thẳng về phía trước nơi chúng tôi thêm một khóa bổ sung khác vào từ điển đồ thị.

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())

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

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

Thêm một cạnh

Việc thêm một cạnh vào đồ thị hiện có bao gồm việc coi đỉnh mới như một bộ giá trị và xác nhận xem cạnh đó đã có mặt chưa. Nếu không thì cạnh được thêm vào.

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())

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

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