Python中的图算法

Question

我有这个示例图

graph = { "v1" : ["v3"],
          "v2" : ["v3", "v5"],
          "v3" : ["v1", "v2", "v4", "v5"],
          "v4" : ["v3"],
          "v5" : ["v3", "v2"],
          "v6" : []
        }

我有两个算法来生成边和寻找孤立的节点：

def edges(g):
    edges = []
    for node in g[node]:
        edges.append((node, g[node]))
    return edges

def isolated(g):
    result = []
    for node in g[node]:
        if not g[node]:
            result += node
    return result

我做错什么了？你知道吗

Answer 1

下面是一种以元组列表的形式列出边的方法，其中包含节点源和节点目标。你知道吗

以及列出没有输出边的节点的方法：

它假设邻接列表两次表示边：一次向外，一次向内，典型的无向图。你知道吗

def edges(g):
    """return a list of tuples representing an edge
    """
    edges = []
    for source in g:
        for destination in g[source]:
            edges.append((source, destination))
    return edges


def isolated_nodes(g):
    """returns a list of the nodes with no outgoing edges
    """
    disconnected_nodes = []
    for node in g:
        if len(g[node]) == 0:
            disconnected_nodes.append(node)
    return disconnected_nodes


graph = { "v1" : ["v3"],
          "v2" : ["v3", "v5"],
          "v3" : ["v1", "v2", "v4", "v5"],
          "v4" : ["v3"],
          "v5" : ["v3", "v2"],
          "v6" : []
        }


print(edges(graph))
print(isolated_nodes(graph))

输出：

[('v1', 'v3'), ('v2', 'v3'), ('v2', 'v5'), ('v3', 'v1'), ('v3', 'v2'), ('v3', 'v4'), ('v3', 'v5'), ('v4', 'v3'), ('v5', 'v3'), ('v5', 'v2')]
['v6']

Answer 2

你要做的是：

graph = { "v1" : ["v3"],
          "v2" : ["v3", "v5"],
          "v3" : ["v1", "v2", "v4", "v5"],
          "v4" : ["v3"],
          "v5" : ["v3", "v2"],
          "v6" : []
        }

res = [k for k, v in graph.items() if not v]

print(res)

您将得到['v6']，因为它是唯一没有节点关联的

Answer 3

如果图可以包含有向边，那么仅仅检查任何给定节点的邻接列表是不够的。相反，您可以为作为某个边缘的源或目标的所有节点获取set，并收集那些既不是源也不是目标的节点。你知道吗

>>> targets = {n for lst in graph.values() for n in lst}
>>> sources = {n for n in graph if graph[n] != []}
>>> isolated = {n for n in graph if n not in sources and n not in targets}
>>> isolated
{'v6'}

或者使用set方法：

>>> isolated = set(graph).difference(sources).difference(targets)