Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > граф связность

Автор: implements 4.2.2013, 16:11

Здравствуйте, не подскажите ли алгоритм проверки графа на связность
(связность -что от любой вершины графа можно дойти до любой другой), дали такое описание
т.е. получается, если от одной вершины можно добраться до всех остальных, то это связной граф, если до какой либо добраться нельзя, значит нет, так?

Автор: Akina 4.2.2013, 16:22

http://algolist.manual.ru/maths/graphs/linked.php

Автор: implements 4.2.2013, 16:32

Цитата(Akina @ 4.2.2013, 16:22

)

http://algolist.manual.ru/maths/graphs/linked.php

спасибо, почитаю, вообще я так понял,для любого графа, что из любой вершины можно дойти до любой другой, или я не так, что-то понимаю?

Автор: Akina 4.2.2013, 16:39

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

Автор: implements 4.2.2013, 16:42

Akina, так ну с алгоритмом в принципе более менее понятно, не понятно каким образом(видом) задать граф для этой задачи

Автор: Akina 4.2.2013, 17:10

Цитата(implements @ 4.2.2013, 17:42

)

каким образом(видом) задать граф для этой задачи

Вектором связности. Скажем, в терминах SQL это может быть (схематично):

Код


CREATE TABLE vertex(id INTEGER AUTO_INCREMENT, color BIT)
PRIMARY CLUSTERED INDEX id (id)

CREATE TABLE links (vertex_from INTEGER, vertex_to INTEGER) 
PRIMARY CLUSTERED INDEX vertex_pair (vertex_from, vertex_to)
FOREIGN KEY vertex_from (vertex_from) REFERENCES vertex(id)
FOREIGN KEY vertex_to (vertex_to) REFERENCES vertex(id)
CHECK CONSTRAINT vertex_from != vertex_to