Python - 图(Graphs)

图(Graphs)是一组对象的图形表示，其中一些对象通过链接连接，互连的对象由称为顶点的点表示，而连接这些顶点的链接称为边。在本章中，无涯教程将了解如何使用python程序创建图形并向其中添加各种数据元素。

使用python字典数据类型可以很容易地显示图形，将顶点表示为字典的键，并将顶点之间的连接也称为边作为字典中的值。

在上图中

V={a, b, c, d, e}
E={ab, ac, bd, cd, de}

可以在python程序中显示此图，如下所示。

# 使用图形元素创建字典
graph={ "a" : ["b","c"],
          "b" : ["a", "d"],
          "c" : ["a", "d"],
          "d" : ["e"],
          "e" : ["d"]
         }

#打印图
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

# 获取字典的键
    def getVertices(self):
        return list(self.gdict.keys())

# 使用图形元素创建字典
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()
# 找到不同的边列表

    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

# 使用图形元素创建字典
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'}]

添加顶点

直接添加顶点是在图字典中添加另一个键的过程。

链接：https://www.learnfk.comhttps://www.learnfk.com/python-data-structure/python-graphs.html

来源：LearnFk无涯教程网

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict={}
        self.gdict=gdict

    def getVertices(self):
        return list(self.gdict.keys())

#添加顶点作为键
    def addVertex(self, vrtx):
       if vrtx not in self.gdict:
            self.gdict[vrtx]=[]

#使用图形元素创建字典
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()
# 添加新边

    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]

# 列出边缘名称
    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

# 使用图形元素创建字典
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'}]