Python Data Structure 简明教程
Python - Graphs
图是对一组对象的图形化表示，其中某些对象对通过链接连接。互连的对象由称为顶点的点表示，连接顶点的链接称为边。与图相关的各种术语和功能在本教程中有详细说明。
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges. The various terms and functionalities associated with a graph is described in great detail in our tutorial here.
在本章中，我们将看到如何使用 Python 程序创建图，并向其中添加各种数据元素。以下是我们在图上进行的基本操作。
In this chapter we are going to see how to create a graph and add various data elements to it using a python program. Following are the basic operations we perform on graphs.
-
Display graph vertices
-
Display graph edges
-
Add a vertex
-
Add an edge
-
Creating a graph
可以使用 Python 字典数据类型轻松呈现图。我们将顶点表示为字典的键，并将称为边的顶点之间的连接表示为字典中的值。
A graph can be easily presented using the python dictionary data types. We represent the vertices as the keys of the dictionary and the connection between the vertices also called edges as the values in the dictionary.
请看下面的图表 −
Take a look at the following graph −
在上图中，
In the above graph,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}Example
我们可以将此图表示为以下 Python 程序 −
We can present this graph in a python program as below −
# 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
执行上述代码后，将生成以下结果 −
When the above code is executed, it produces the following result −
{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}Display graph vertices
要显示图顶点，我们只需找到图字典的键。我们使用 keys() 方法。
To display the graph vertices we simple find the keys of the graph dictionary. We use the keys() method.
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
找到图边比找到顶点要困难一些，因为我们必须找到每对之间有边的顶点的各个对。因此，我们创建一个空的边列表，然后遍历与每个顶点关联的边值。我们将形成一个包含从顶点找到的不同组边的列表。
Finding the graph edges is little tricker than the vertices as we have to find each of the pairs of vertices which have an edge in between them. So we create an empty list of edges then iterate through the edge values associated with each of the vertices. A list is formed containing the distinct group of edges found from the vertices.
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
添加顶点非常直接，我们在图字典中添加另一个额外的键即可。
Adding a vertex is straight forward where we add another additional key to the graph dictionary.
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())Output
执行上述代码后，将生成以下结果 −
When the above code is executed, it produces the following result −
['a', 'b', 'c', 'd', 'e','f']Adding an edge
向现有图添加边涉及将新顶点视为元组，并验证该边是否已经存在。如果不存在，则添加该边。
Adding an edge to an existing graph involves treating the new vertex as a tuple and validating if the edge is already present. If not then the edge is added.
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())