如果您想以优化的方式进行操作，请使用强连接组件（kosaraju 的算法）并找出最强连接的组件并添加您的弱连接节点以制作完全连接的图。
代码示例来演示：
#Function to findout the closely connected components:
class Graph:
def __init__(self,vertices):
self.V= vertices #No. of vertices
self.graph = defaultdict(list) # default dictionary to store graph
# function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
# A function used by DFS
def DFSUtil(self,v,visited):
# Mark the current node as visited and print it
visited[v]= True
print(v)
#Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i]==False:
self.DFSUtil(i,visited)
def fillOrder(self,v,visited, stack):
# Mark the current node as visited
visited[v]= True
#Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i]==False:
self.fillOrder(i, visited, stack)
stack = stack.append(v)
# Function that returns reverse (or transpose) of this graph
def getTranspose(self):
g = Graph(self.V)
# Recur for all the vertices adjacent to this vertex
for i in self.graph:
for j in self.graph[i]:
g.addEdge(j,i)
return g
def printSCCs(self):
stack = []
# Mark all the vertices as not visited (For first DFS)
visited =[False]*(self.V)
# Fill vertices in stack according to their finishing
# times
for i in range(self.V):
if visited[i]==False:
self.fillOrder(i, visited, stack)
# Create a reversed graph
gr = self.getTranspose()
# Mark all the vertices as not visited (For second DFS)
visited =[False]*(self.V)
# Now process all vertices in order defined by Stack
while stack:
i = stack.pop()
if visited[i]==False:
gr.DFSUtil(i, visited)
print("*****")
假设我总共有 18 个节点和一些初始连接：
g = Graph(18)
g.addEdge(0, 10)
g.addEdge(1, 15)
g.addEdge(1, 17)
g.addEdge(2, 1)
g.addEdge(2, 3)
g.addEdge(4, 12)
g.addEdge(5, 7)
g.addEdge(6, 11)
g.addEdge(7, 8)
g.addEdge(7, 9)
g.addEdge(8, 9)
g.addEdge(9, 10)
g.addEdge(11, 14)
g.addEdge(12, 0)
g.addEdge(13, 6)
g.addEdge(14, 13)
g.addEdge(14, 4)
g.addEdge(15, 1)
g.addEdge(16, 2)
我的初始输入有如下连接：
{0: [10],
1: [15, 17],
2: [3, 1],
3: [],
4: [12],
5: [7],
6: [11],
7: [8, 9],
8: [9],
9: [10],
10: [],
11: [14],
12: [0],
13: [6],
14: [13, 4],
15: [1],
16: [2],
17: []}
运行上述算法后，我得到的强连通分量如下：
Following are strongly connected components in given graph
16
*****
6
13
14
11
*****
5
*****
7
*****
8
*****
9
*****
4
*****
12
*****
2
*****
3
*****
1
15
*****
17
*****
0
*****
10
*****
如果我添加以下连接，请点击并试用。我的图变得完全连接：
##### New Additions ############
g.addEdge(9, 5)
g.addEdge(5, 11)
g.addEdge(12, 7)
g.addEdge(10, 13)
g.addEdge(3, 4)
g.addEdge(17, 16)
g.addEdge(14, 15)
再次运行上述强连接组件算法，最终输出为：
Following are strongly connected components in given graph
0
12
4
14
11
5
9
7
8
6
13
10
3
2
16
17
1
15
*****
代码参考在以下链接：
Strongly Connected Components
注意：我已经根据您的问题进行了尝试，必须有更好的方法和更好的方法，而不是 Hit and Trail。如果找到更好的方法，请随时改进答案。此答案的目的是介绍一种分析您的问题的方法。