0

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

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

有趣的是，i.head_list有时它是一个空列表，尽管在 Graph Test Data中每个节点都至少有一个头和一个尾。

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

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

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

测试数据

节点 尾巴
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)```
4

2 回答 2

0

In this code:

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

you are assuming that the tail node does not already exist in the graph. That's not a safe assumption. If the tail node already exists, you need to adjust its links, not assign a new one.

于 2021-03-10T18:41:47.293 回答
0

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

我更新了代码以索引头部或尾部现在所指的图表中的位置。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)
于 2021-03-12T14:39:05.580 回答