Я реализовал алгоритм сильно связанных компонентов Tarjan, согласно wikipedia, в Python, но он не работает. Алгоритм довольно короткий, и я не могу найти разницы, поэтому я не могу сказать, почему он не работает. Я попытался проверить оригинальную бумагу, но не смог ее найти.
Вот код.
def strongConnect(v):
global E, idx, CCs, c, S
idx[v] = (c, c) #idx[v][0] for v.index # idx[v][1] for v.lowlink
c += 1
S.append(v)
for w in [u for (v2, u) in E if v == v2]:
if idx[w][0] < 0:
strongConnect(w)
# idx[w] = (idx[w][0], min(idx[v][1], idx[w][1])) #fixed, thx
idx[v] = (idx[v][0], min(idx[v][1], idx[w][1]))
elif w in S:
idx[v] = (idx[v][0], min(idx[v][1], idx[w][0]))
if (idx[v][0] == idx[v][1]):
i = S.index(v)
CCs.append(S[i:])
S = S[:i]
E = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), ('D', 'F'), ('F', 'B'), ('E', 'F')]
idx = {}
CCs = []
c = 0
S = []
for (u, v) in E:
idx[u] = (-1, -1)
idx[v] = (-1, -1)
for v in idx.keys():
if idx[v][0] < 0:
strongConnect(v)
print(CCs)
Вы можете проверить график визуально, если хотите. Как вы можете видеть, это довольно прямой перевод псевдокода в википедию. Однако это результат:
[['D', 'E', 'F'], ['B', 'C'], ['A']]
Должен быть только один сильно связанный компонент, а не три. Надеюсь, этот вопрос прав во всех его аспектах, если не извините. В любом случае, спасибо вам большое.