如何找到有向无环图中每个节点的所有父节点？

Question

对于下面python代码给出的有向无环图，我想找出DAG的每个节点的所有父节点。请帮忙！例如，节点 6,7 和 8 是节点 9 的父节点。我必须创建一个函数，我必须访问每个节点的所有父节点并根据我的问题采取行动。注：代码取自geeksforgeeks

class Graph:
    # Constructor to construct a graph
    def __init__(self, edges, n):
 
        # A list of lists to represent an adjacency list
        self.adjList = [None] * n
 
        # allocate memory for the adjacency list
        for i in range(n):
            self.adjList[i] = []
 
        # add edges to the directed graph
        for (src, dest, weight) in edges:
            # allocate node in adjacency list from src to dest
            self.adjList[src].append((dest, weight))


# Function to print adjacency list representation of a graph
def printGraph(graph):
    for src in range(len(graph.adjList)):
        # print current vertex and all its neighboring vertices
        for (dest, weight) in graph.adjList[src]:
            new_graph[src].append(dest)
            print(f'({src} —> {dest}, {weight}) ', end='')
        print()
 

# Input: Edges in a weighted digraph (as per the above diagram)
# Edge (x, y, w) represents an edge from `x` to `y` having weight `w`
edges = [(0, 1, 18), (0, 2, 12), (0, 3, 9), (0, 4, 11), (0, 5, 14), 
          (1, 7, 19), (1, 8, 16), (2, 6, 23), (3, 7, 27), (3, 8, 23),
        (4, 8, 13), (5, 7, 15), (6, 9, 17), (7, 9, 11), (8, 9, 13)]

# No. of vertices (labelled from 1 to 10)
n = 10

# construct a graph from a given list of edges
graph = Graph(edges, n)
new_graph = [[] for i in range(n)]
# print adjacency list representation of the graph
printGraph(graph)

Answer 1

您可以使用与遍历所有边的 printGraph 函数类似的结构。然后我们可以检查每条边是否通向我们的子节点。如果是这样，我们找到了一个父节点。这些父节点被存储和返回。这是该函数的示例实现：

# Function to find all parents of a node
def getParent(graph, node):
    # collect parents as a set in order to avoid duplicate entries
    parents = set()
    for src in range(len(graph.adjList)):
        # Iterate over all edges from src node
        for (dest, weight) in graph.adjList[src]:
            # if destiontion is our needed child add source as parent
            if dest == node:
                parents.add(src)
                
    # Return all parents as a list
    return list(parents)

这样调用它来查找节点 9 的父节点：

# Input: Edges in a weighted digraph (as per the above diagram)
# Edge (x, y, w) represents an edge from `x` to `y` having weight `w`
edges = [(0, 1, 18), (0, 2, 12), (0, 3, 9), (0, 4, 11), (0, 5, 14), 
          (1, 7, 19), (1, 8, 16), (2, 6, 23), (3, 7, 27), (3, 8, 23),
        (4, 8, 13), (5, 7, 15), (6, 9, 17), (7, 9, 11), (8, 9, 13)]

# No. of vertices (labelled from 1 to 10)
n = 10

# construct a graph from a given list of edges
graph = Graph(edges, n)
print(getParent(graph, 9))

输出是节点 9 的双亲列表：

[8, 6, 7]

如何找到有向无环图中每个节点的所有父节点？

How to find all the parent nodes of each node in a directed acyclic graph?

python

python-3.x

parent

directed-acyclic-graphs