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

Question

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

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]