上一节:
下一节:

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

  • 显示图形顶点

    为了显示图的顶点，我们简单地找到图字典的键。我们使用 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())

    输出

    执行上述代码时，会产生以下结果 - 
    
['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'}]
上一节:
下一节: