Python Data Structure 简明教程
Python - Graphs
图是对一组对象的图形化表示，其中某些对象对通过链接连接。互连的对象由称为顶点的点表示，连接顶点的链接称为边。与图相关的各种术语和功能在本教程中有详细说明。
在本章中，我们将看到如何使用 Python 程序创建图，并向其中添加各种数据元素。以下是我们在图上进行的基本操作。
-
Display graph vertices
-
Display graph edges
-
Add a vertex
-
Add an edge
-
Creating a graph
可以使用 Python 字典数据类型轻松呈现图。我们将顶点表示为字典的键，并将称为边的顶点之间的连接表示为字典中的值。
请看下面的图表 −
在上图中，
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}Example
我们可以将此图表示为以下 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)Output
执行上述代码后，将生成以下结果 −
{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}Display graph vertices
要显示图顶点，我们只需找到图字典的键。我们使用 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())Display graph edges
找到图边比找到顶点要困难一些，因为我们必须找到每对之间有边的顶点的各个对。因此，我们创建一个空的边列表，然后遍历与每个顶点关联的边值。我们将形成一个包含从顶点找到的不同组边的列表。
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())Adding a vertex
添加顶点非常直接，我们在图字典中添加另一个额外的键即可。
Example
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())Adding an edge
向现有图添加边涉及将新顶点视为元组，并验证该边是否已经存在。如果不存在，则添加该边。
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())