遍历 Class 个对象列表属性

Question

希望有人对此有所了解。 Kosaraju 算法实现的前半部分，带有图和节点 class。我正在遍历节点列表，每个节点都有一个头部列表和一个尾部列表，以允许向前或向后移动。当您在图表中移动时，新探索的顶点是 explored 然后您访问 head_list:

    for j in i.head_list:
        DFS(my_graph, j, T, S)

有趣的是 i.head_list 有时是一个空列表，尽管在图中 测试数据 每个节点至少有一个头和一个尾。

示例（来自下面的 测试数据 ）：第一次调用应该是“9”，head_list 为 [6]，但返回 [] 并且 tail_list 是 [3, 7]。在作为 tail_list 的一部分调试钻入变量 3 时，head_list 填充为 [9]，但 tail_list 为 []。在填充头列表和尾列表之间进行某种翻转。

我以为有一些全局变量混淆了，但我没有找到。我想也许 copy.deepcopy 可能已经修复了它，但事实并非如此。这似乎是非常不寻常的行为。更有趣的是，当一个节点已经包含在 head_list 中时，它似乎只产生一个空列表。例如：节点 4 是第一个失败并且

我希望能够无限期地通过节点和 head_list 或 tail_list 进行连续钻取，但是迭代中列表的存在会来回变化。任何见解将不胜感激。

测试数据

Node	Tail
1	4
2	8
3	6
4	7
5	2
6	9
7	1
8	5
8	6
9	3
9	7

class Graph():

    def __init__(self, graph):
        self.graph = graph
        self.node_list = []
    def add_node(self, node):
        self.node_list.append(node)


    def __repr__(self):
        return (f'_{self.graph} + {[node for node in self.node_list]} + {[node.head_list for node in self.node_list]}')

class Node():

    def __init__(self, head):
        self.head = head
        self.explored = False
        self.head_list = []
        self.tail_list = []
        self.leader = None
        self.finish_time = 0
    def __repr__(self):
        return f'{self.head}'
    def add_node_edge(self, Node, lst):
        if lst == 'head':
            self.head_list.extend([Node])
        else: 
            self.tail_list.extend([Node])

def DFS_loop(my_graph):
    global T
    global S
    T = 0 # number of nodes processed so far
    S = None # current source vertex

    for node in my_graph.node_list[::-1]:
        if node.explored == False:
            S = node
            DFS(my_graph, node, T, S)

def DFS(my_graph, i, T, S):

    i.explored = True
    i.leader = S.head

    for j in i.head_list:
        DFS(my_graph, j, T, S)
    T += 1
    i.finish_time = T

file1 = open('C:/Downloads/test_Data.txt', 'r')
Lines = file1.readlines()

my_graph = Graph('A')

default_node = Node(0)
my_graph.node_list = [default_node]*9
unexplored_queue = []

for line in Lines:
    h, t = line.strip().split()
    h = int(h)
    t = int(t)
    new_node = Node(h)
    new_head_node = Node(h)
    new_tail_node = Node(t)

    new_node.add_node_edge(new_tail_node, 'tail')
    new_tail_node.add_node_edge(new_node, 'head')

    if my_graph.node_list[h-1].head == 0:
        my_graph.node_list[h-1] = new_node
    else:
        my_graph.node_list[h-1].add_node_edge(new_tail_node, 'tail')

    if my_graph.node_list[t-1].head == 0:
        my_graph.node_list[t-1] = new_tail_node
    else:
        my_graph.node_list[t-1].add_node_edge(new_node, 'head')

DFS_loop(my_graph)
for node in my_graph.node_list:
    print(node, node.finish_time)```

Answer 1

在此代码中：

new_node = Node(h)
new_head_node = Node(h)
new_tail_node = Node(t)

您假设图中不存在尾节点。这不是一个安全的假设。如果尾节点已经存在，则需要调整它的链接，而不是分配一个新的链接。

Answer 2

感谢蒂姆让我更清楚地思考这个问题。在我的原始代码中，头部和尾部列表是节点对象的列表。但是，如果您不使用图中已有的节点，那么您就不会正确地包含所有尾节点和头节点，并且更新节点的头列表和尾列表是一场噩梦。

我更新了代码以索引图中头部或尾部现在所指的位置。 node.head_list 和 node.tail_list 成为您用 my_graph.node_list[node.head_list[0]]

调用的整数列表

    new_node = Node(h)
    new_tail_node = Node(t)

    if my_graph.node_list[h-1].head == 0:
        my_graph.node_list[h-1] = new_node
        my_graph.node_list[h-1].tail_list.append(t)
    else:
        my_graph.node_list[h-1].tail_list.append(t)

    if my_graph.node_list[t-1].head == 0:
        my_graph.node_list[t-1] = new_tail_node
        my_graph.node_list[t-1].head_list.append(h)
    else:
        my_graph.node_list[t-1].head_list.append(h)

遍历 Class 个对象列表属性

Iterating through Class object list attribute

python

oop

kosaraju-algorithm