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'}]