Търсене на свързани компоненти

Определяне на свързаните компоненти

Концепцията на свързаните компоненти, получени от концепцията за свързване на графиката. Казано по-просто, свързан компонент - част от графиката (подграф) е свързан. Формално, свързан компонент - набор от върхове, между всеки два от които има път.

Разчитайте на илюстрацията има три свързани компоненти, боядисани в различни цветове. Може да се отбележи, че дори един връх, изолиран от останалата част на графиката е свързан компонент.

Най-общата концепция за свързаност се отнася само за неориентирани графа. За описание на графики, насочени се използват понятията силен и слаб съгласуваност, но те са извън границите на материала в тази глава.

Алгоритъм за търсене, свързани компоненти

За свързани компоненти се използват конвенционални DFS практически без модификация (може да се използва BFS). При стартиране на обхождане от върха на един, това е гарантирано за посещение на всички върхове, на които е възможно да се получи, това е, всички от свързания компонент, към която принадлежи първоначалната връх. За да намерите всички компоненти просто се опитват да тече кръг от всеки връх в даден момент, ако не сме пощадени му компонент по-рано.

изпълнение

Даваме две изпълнения на метода с различни съхранение свързани компоненти.

Най-лесният вариант: трябва само да попълните масив комп $ $, където $ комп [в] $ - брой на свързани компоненти, към която принадлежи връх $ аз $.

Алтернативно, изрично се съхранява за всеки компонент на вектора на върховете, принадлежащи към него. Компоненти (вектори), съхранявани във вектора (вектори).