遍历线图是一种用于描述节点之间关系的图形结构。在遍历线图中,每个节点表示一个元素,并且节点之间的连接表示元素之间的关系。下面是一个使用邻接表表示的遍历线图的代码示例:
class Node:
def __init__(self, value):
self.value = value
self.neighbors = []
def traverse_graph(node):
visited = set()
stack = [node]
while stack:
current_node = stack.pop()
if current_node not in visited:
visited.add(current_node)
print(current_node.value)
for neighbor in current_node.neighbors:
stack.append(neighbor)
# 创建节点
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
# 构建节点之间的关系
node1.neighbors = [node2, node3]
node2.neighbors = [node4]
node3.neighbors = [node4, node5]
node4.neighbors = [node5]
# 遍历线图
traverse_graph(node1)
在上述代码中,我们首先定义了一个Node
类,该类表示遍历线图中的节点。每个节点包含一个value
属性表示节点的值,并且还包含一个neighbors
属性表示与该节点相邻的节点列表。
然后,我们定义了一个traverse_graph
函数,该函数用于遍历遍历线图。我们使用一个visited
集合来记录已经访问过的节点,使用一个stack
列表来存储待访问的节点。首先,我们将起始节点加入到stack
中。然后,我们进入一个循环,从stack
中取出一个节点,并检查是否已经访问过。如果没有访问过,则将其加入到visited
集合中,并输出该节点的值。接下来,我们遍历当前节点的所有相邻节点,并将其加入到stack
中。重复这个过程,直到stack
为空。
最后,我们创建了几个节点,并构建了节点之间的关系。然后,我们调用traverse_graph
函数来遍历线图,并输出节点的值。在上述代码中,遍历线图的顺序为1、3、5、4、2,即按照深度优先的顺序进行遍历。