Обсуждение:Построение компонент рёберной двусвязности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Дмитрий Мурзин переименовал страницу Обсуждение:Построение компонент реберной двусвязности в [[Обсуждение:Построение компонент рёбе…)
 
(не показана 1 промежуточная версия 1 участника)
Строка 5: Строка 5:
  
 
Граф:
 
Граф:
8 10 //8 вершин, 10 ребер
+
8 вершин, 10 ребер {(1 2), (2 8), (8 1), (2 3), (3 4), (4 5), (5 3), (3 6), (6 7), (7 3)}
1 2
 
2 8
 
8 1
 
2 3
 
3 4
 
4 5
 
5 3
 
3 6
 
6 7
 
7 3
 

Текущая версия на 23:48, 31 января 2019

"ИТОГО: раньше часть про однопроходный алгоритм выглядела более правдоподобной."

Хм.. не согласен, если про работоспособность, то это не факт. То что описано здесь, работает и было сдано на Лабораторной по АСД. Могу код привести реальный. Да и с точки зрения асимптотики, это лучше и не скрыто в коде асимптотика СНМ. Кроме того этот алгоритм, в отличие от решения СНМ, реализацию на стеке была рассказана на практике, в качестве домашнего задания.


Граф: 8 вершин, 10 ребер {(1 2), (2 8), (8 1), (2 3), (3 4), (4 5), (5 3), (3 6), (6 7), (7 3)}