在Python中使用字典生成图形

先决条件—— 图 要使用内置库绘制图形—— Python中的图形绘制 在本文中，我们将看到如何使用 词典 python中的数据结构。 使用的字典键是图中的节点，对应的值是每个节点的列表，这些节点通过一条边连接。 这个简单的图有六个节点（a-f）和五条弧：

a -> cb -> cb -> ec -> ac -> bc -> dc -> ed -> ce -> ce -> b

它可以由以下Python数据结构表示。这是一个字典，其键是图的节点。对于每个关键点，对应的值都是一个列表，其中包含通过该节点的直弧连接的节点。

graph = { "a" : ["c"],          "b" : ["c", "e"],          "c" : ["a", "b", "d", "e"],          "d" : ["c"],          "e" : ["c", "b"],          "f" : []        } 

上述示例的图形表示：

defaultdict ：通常，如果您试图获取一个当前不在Python字典中的项，则Python字典会抛出一个KeyError。defaultdict允许，如果在字典中找不到密钥，则不会抛出密钥错误，而是创建一个新条目。这个新条目的类型由defaultdict的参数给出。 用于生成图形的Python函数：

# definition of functiondef generate_edges(graph):    edges = []    # for each node in graph    for node in graph:        # for each neighbour node of a single node        for neighbour in graph[node]:            # if edge exists then append            edges.append((node, neighbour))    return edges

输出：

[('a', 'c'), ('c', 'd'), ('c', 'e'), ('c', 'a'), ('c', 'b'), ('b', 'c'), ('b', 'e'), ('e', 'b'), ('e', 'c'), ('d', 'c')]

我们举了一个无向图的例子，所以我们把同一条边打印两次，比如（’a’，’c’）和（’c’，’a’）。我们可以通过使用有向图来克服这个问题。 下面是python中关于图形的更多程序： 生成从一个节点到另一个节点的路径 : 使用Python字典，我们可以在图中找到从一个节点到另一个节点的路径。这个想法类似于 DFS 在图表中。 在函数中，路径最初是一个空列表。在开始时，如果开始节点与结束节点匹配，函数将返回路径。否则，代码将前进并命中起始节点的所有值，并使用递归搜索路径。

输出：

['d', 'a', 'c']

程序生成从一个节点到另一个节点的所有可能路径。 : 在上面讨论的程序中，我们生成了第一条可能的路径。现在，让我们生成从开始节点到结束节点的所有可能路径。基本功能与上述代码的功能相同。不同之处不是立即返回第一条路径，而是将该路径保存在一个名为“路径”的列表中，在下面给出的示例中。最后，在迭代所有可能的方法之后，它返回路径列表。如果没有从起始节点到结束节点的路径，则返回None。

输出：

[['d', 'a', 'c'], ['d', 'a', 'c']]

程序生成最短路径。 : 为了从所有路径中获得最短路径，我们使用了一种稍微不同的方法，如下所示。在这种情况下，当我们得到从开始节点到结束节点的路径时，我们将路径的长度与名为shortest的变量进行比较，该变量被初始化为None值。如果生成的路径长度小于“最短路径”的长度，如果“最短路径”不是“无”，则将新生成的路径设置为“最短路径”的值。同样，如果没有路径，它将返回None

输出：

['d', 'a', 'c']

本文由 希瓦姆·普拉丹（anuj_charm） 和 里沙布·班萨尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。