Возможно ли обнаружить сортировкой Кана изолированные узлы, сортировать сразу рёбра и не использовать степень?

Question

[pavlik 322]

Зачем в алгоритме сортировки Кана вначале требуется степень или просчёт всех соединений, вроде и без неё всё работает?
Есть ли возможность сортировать не узлы, а рёбра сразу?
Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?
*Вопросы маленькие, поэтому разбивать их на отдельные не стал

Answer 1

[Wataru]

Зачем в алгоритме сортировки Кана вначале требуется степень или просчёт всех соединений, вроде и без неё всё работает?

Без нее работает медленно. Смотрите алгоритм. В алгоритме надо брать вершину в которую не входит ни одно ребро, а также удалять вершины. Кончено, можно наивно брать все вершины, потом брать все ребра, смотреть, не удалено ли ребро и не ведет ли оно в эту вершину. Но это будет O(VE) для поиска одной вершины, а суммарно алгоритм будет O(V^2E). Когда как реализация с подсчетом степеней и очередью будет O(V+E).

Есть ли возможность сортировать не узлы, а рёбра сразу?

Не совсем, потому что порядок вершин - это основа. Можно во время работы алгоритма вместо вершины выдавать все исходящие из нее ребра, будет у вас сортировка ребер. Но суть алгоритма остается той же самой.

Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?

Можно. Изолированные узлы - это те в которые ни одно ребро не входит. В алгоритме Кана это те, которые можно вывести до удаления любой вершины.

Comments

[pavlik 322]

Если быть точнее, то под третьим пунктом я подразумевал, если у меня окажется, что существует два несвязных графа

[Wataru]

pavlik 322, Алгоритмам топологической сортировки не надо, чтобы все было одним куском. Конкретно в алгоритме Кана у вас будут вершины без входящих ребер во всех кусках графа. Да, вершины из разных кусков могут в итоге быть в перемешку, но это ничего не портит.