如果你把它想象成一种疾病传播，所有感染者都可以将疾病传播到另一个目标，那么这个问题就更容易理解了。将零号病人视为起始节点。它在第一步中仅传播到一个其他节点，而在第二回合中，两个“受感染”节点都可以传播到两个或更少的其他节点，具体取决于整个图的连接。
我一直在努力自己编写算法，但在网上找不到任何有用的东西，因为很难用一般性的术语来写这个问题。
我当前的代码根据节点的连接数（功率）进行移动。当前被感染的节点将其传播到已连接且连接数最多的节点。传播顺序也被修改，使得所有连接数较少的节点都可以首先被使用，以增加更多节点被“感染”的机会。 还尝试计算每个子图的邻居，但该方法在测试 1 中失败。 任何我应该检查的算法链接将不胜感激。
我当前的Python代码：
import networkx as nx
import matplotlib.pyplot as plt
class Node:
def __init__(self, value, neighbors):
self.value = value #the number of the node
self.neighbors = neighbors #connections to other nodes
self.power = len(neighbors) #number of connections
self.visited = None #array of visited nodes
class Graph:
def __init__(self, nodes):
self.nodes = nodes
for i in range(len(self.nodes)):
#Creating the array of nodes that can be visited (marked by 0)
#And those whose can't be visited (marked by -1)
nodes[i].visited = [-1 for j in range(len(self.nodes))]
for m in range(len(self.nodes[i].neighbors)):
self.nodes[i].visited[nodes[i].neighbors[m]-1] = 0
#Array used to check if every node is visited. Should be all 1's if all are visited
self.globalVisits = [0 for i in range(len(nodes))]
#Returns node if indexed by the value
def getNode(self,index):
return self.nodes[index-1]
def allVisited(self):
return not 0 in self.globalVisits
#Helper function to paint the spreading process and initiate the main algorithm
def findValue(graph, start,drawing, pos):
graph.globalVisits[start-1]=1 #Marking the staring position
visited = [start] #Initializing array of visited nodes
order = [[start]] #Initializing array of order of visits
result = spreadRumour(graph, visited, order) #Finding the steps to spread through all of the graph
#Painting the graph
for cell in order:
for number in cell:
drawing.nodes[number]['color'] = 'green'
plt.clf()
node_colors = [drawing.nodes[node].get('color', 'red') for node in drawing.nodes]
nx.draw(drawing,pos, with_labels=True, font_weight='bold', node_color=node_colors)
plt.pause(0.5)
plt.ioff()
plt.show()
print(f"Spread order: {order}") #Printing order
return result
def spreadRumour(graph, visited,order):
travels = 0
while not graph.allVisited():
change = False
travels += 1
lastOrder = order[len(order) - 1].copy()
for i in range(len(visited)):
maxP = -1 #Max power
nextNode = None #node.Value of the next node
current = graph.getNode(visited[i]) #Current node that is spreading
for j in range(len(current.visited)):
#Checking if the node can spread locally and globally
if current.visited[j] ==0 and graph.globalVisits[j] == 0:
#Checking if the power is greatest of all neighbors
if graph.getNode(j+1).power>maxP:
#Marking power and the spreading target
maxP = graph.getNode(j+1).power
nextNode = j+1
if nextNode != None:
#Mark that the spread is still happening
change = True
#Mark visited nodes in graph context
graph.globalVisits[nextNode-1]=1
graph.globalVisits[current.value-1]=1
#Decrease the power and mark visits in the next node
graph.getNode(nextNode).visited[visited[i]-1]=1
graph.getNode(nextNode).power -= 1
#Decrease the power and mark visits in the current node
current.visited[nextNode-1]=1
current.power -=1
#Update visited nodes list and update the spread order
visited.append(nextNode)
lastOrder.append(nextNode)
#Marking the order
if(order[len(order) - 1] != lastOrder):
order.append(lastOrder)
#Checking if the algorithm still makes progress
if change == False:
print("Failed to spread to all")
break
#Sorting nodes by the number of connections
visited.sort(key=lambda x: graph.getNode(x).power)
# print(visited)
return travels
# test 1
#vertices = [[1, [2,3]], [2, [1,3]], [3, [1,4,5]], [4, [3]], [5, [3]]]
# test 2
# vertices = [
# [1, [2, 3, 4, 5, 6]],
# [2, [1]],
# [3, [1]],
# [4, [1]],
# [5, [1, 7, 8, 9, 10, 15, 17]],
# [6, [1, 11, 12, 13, 14, 16, 18]],
# [7, [5, 8, 9, 10]],
# [8, [5, 7, 9, 10]],
# [9, [5, 7, 8, 10]],
# [10, [5, 7, 8, 9]],
# [11, [6, 12, 13, 14]],
# [12, [6, 11, 13, 14]],
# [13, [6, 11, 12, 14]],
# [14, [6, 11, 12, 13]],
# [15, [5]],
# [16, [6]],
# [17, [5]],
# [18, [6]]
# ]
# test 3
vertices = [
[1, [2, 3, 5, 8, 12]],
[2, [1, 3, 4]],
[3, [1, 2, 4]],
[4, [2, 3]],
[5, [1, 6, 7]],
[6, [5, 7]],
[7, [5, 6]],
[8, [1, 9, 10]],
[9, [8, 10, 11]],
[10, [8, 9]],
[11, [9]],
[12, [1, 13]],
[13, [12, 14, 15]],
[14, [13, 15]],
[15, [13, 14]]
]
#creating nodes and the graph objects
nodes = [Node(x[0], x[1]) for x in vertices]
graph = Graph(nodes)
#drawing the initial graph
G = nx.Graph()
for i in range(len(graph.nodes)):
for j in range(len(graph.getNode(i+1).neighbors)):
G.add_edge(graph.getNode(i+1).value, graph.getNode(i+1).neighbors[j])
pos = nx.spring_layout(G)
nx.draw(G,pos, with_labels=True, font_weight="bold", node_color="red")
plt.show()
#printing result
print(f"Was spread through the graph in {findValue(graph,1,G, pos)} turns")
未注释的测试可以在5回合内清除，但我的程序在7回合内清除。
要找到访问所有节点的最少步骤，您需要找到以起始节点为根的树的最大深度。 这可以使用深度优先搜索（DFS）来完成。 您可以找到很多实现 DFS 的代码。