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)
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}
แสดงจุดยอดของกราฟ
ในการแสดงจุดยอดของกราฟเราหาคีย์ของพจนานุกรมกราฟ เราใช้วิธีการคีย์ ()
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())
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
['d', 'b', 'e', 'c', 'a']
แสดงขอบกราฟ
การหาขอบกราฟนั้นยากกว่าจุดยอดเล็กน้อยเนื่องจากเราต้องหาจุดยอดแต่ละคู่ที่มีขอบคั่นอยู่ ดังนั้นเราจึงสร้างรายการขอบที่ว่างเปล่าแล้ววนซ้ำค่าขอบที่เกี่ยวข้องกับจุดยอดแต่ละจุด รายการถูกสร้างขึ้นโดยมีกลุ่มขอบที่แตกต่างกันซึ่งพบจากจุดยอด
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())
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[{'b', 'a'}, {'b', 'd'}, {'e', 'd'}, {'a', 'c'}, {'c', 'd'}]
การเพิ่มจุดยอด
การเพิ่มจุดยอดเป็นไปอย่างตรงไปตรงมาซึ่งเราจะเพิ่มคีย์เพิ่มเติมอื่นในพจนานุกรมกราฟ
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())
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
['f', 'e', 'b', 'a', 'c','d']
การเพิ่มขอบ
การเพิ่มขอบให้กับกราฟที่มีอยู่เกี่ยวข้องกับการปฏิบัติต่อจุดยอดใหม่เป็นทูเพิลและการตรวจสอบความถูกต้องหากขอบมีอยู่แล้ว ถ้าไม่เช่นนั้นขอบจะถูกเพิ่ม
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())
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[{'e', 'd'}, {'b', 'a'}, {'b', 'd'}, {'a', 'c'}, {'a', 'e'}, {'c', 'd'}]