Spójne składowe grafu

0

Prosiłbym o pomoc w napisaniu programu, który do tablicy wrzuca wszystkie numery wierzchołków tworzacych spójne składowe grafu i oddziela je od siebie znakiem -1.
Przykład:
1 2
2 3
3 1
4 5
5 4
6 7
7 6
8 8

1 2 3 -1 4 5 -1 6 7 -1 8

Czy da się to zrobić jakoś szybk, wykodzilem coś z dfs'em, ale starnie wolno działą :(

0

o ile dobrze rozumiem (nieskierowany?), to w zasadzie, nieinteresuje Cie jak ten graf wyglada, ale jakie numery wierzcholkow wchodza w sklad ktorej skladowej spojnosci.

trzymajac wierzcholki w mapie/tablicy numerskladowej -> posortowana lista wierzcholkow, jestes w stanie sprawdzic czy pojedynczy wierzcholek nalezy do jakiejs skladowej po prostu przez przeszukanie binarne owych list

algo:
zaczynasz z pusta mapa list
w petli:
wczytujesz "krawedz"
szukasz w mapie wierzcholka pierwszego -> numerskladowej1
szukasz w mapie wierzcholka drugiego -> numerskladowej2
jesli:
- udalo sie znalezc i pierwszy i drugi wierzcholek, to nalezy scalic te skladowe w jedna
- jeden z nich nalezal do jakiejs skladowej, drugi do zadnej -- ten nienalezacy nalezy dodac do owej skladowej
- jesli zaden nie nalezal - nalezy dodac nowa skladowa zawierajaca te dwa wierzcholki

po przetworzeniu wszystkich krawedzi, w mapie zostana rozdzielone skladowe

to tyle slowem lopatologii.
mozna to zrobic szybciej: trzymaj dwie mapy/tablice:
a) wierzcholek->numerskladowej
b) numerskladowej->listawierzcholkow
pierwszej uzywaj do sprawdzania kto do czego nalezy, drugiej - do scalania skladowych. oczywiscie obie musza byc pilnie synchronizowane.

0
quetzalcoatl napisał(a)

o ile dobrze rozumiem (nieskierowany?), to w zasadzie, nieinteresuje Cie jak ten graf wyglada, ale jakie numery wierzcholkow wchodza w sklad ktorej skladowej spojnosci.

trzymajac wierzcholki w mapie/tablicy numerskladowej -> posortowana lista wierzcholkow, jestes w stanie sprawdzic czy pojedynczy wierzcholek nalezy do jakiejs skladowej po prostu przez przeszukanie binarne owych list

algo:
zaczynasz z pusta mapa list
w petli:
wczytujesz "krawedz"
szukasz w mapie wierzcholka pierwszego -> numerskladowej1
szukasz w mapie wierzcholka drugiego -> numerskladowej2
jesli:
- udalo sie znalezc i pierwszy i drugi wierzcholek, to nalezy scalic te skladowe w jedna
- jeden z nich nalezal do jakiejs skladowej, drugi do zadnej -- ten nienalezacy nalezy dodac do owej skladowej
- jesli zaden nie nalezal - nalezy dodac nowa skladowa zawierajaca te dwa wierzcholki

po przetworzeniu wszystkich krawedzi, w mapie zostana rozdzielone skladowe

to tyle slowem lopatologii.
mozna to zrobic szybciej: trzymaj dwie mapy/tablice:
a) wierzcholek->numerskladowej
b) numerskladowej->listawierzcholkow
pierwszej uzywaj do sprawdzania kto do czego nalezy, drugiej - do scalania skladowych. oczywiscie obie musza byc pilnie synchronizowane.

Ale kombinujesz
A nie prościej

  • wczytujemy graf (tablica std::list<int> a[x], gdzie lista to zbior krawedzi dla wierzcholka x)
  • tworzymy tablice 'bool bylo[x]'
  • tworzymy zmienna globalna int ktora = 0;
  • modyfikujemy funkcje DFS tak, aby przyjmowala dwa parametry: DFS(wierzcholek, ktora) oraz na poczatku swojego dzialania ustawiala "bylo[wierzcholek] = true", a pozniej wypisala numer wierzcholka
  • wywolujemy po kolei dfs dla wszystkich wierzcholkow np. tak:
for(int i = 0; i < ileWierzcholkow; i++) { if(!bylo[i]) DFS(i, ktora++); std::cout << " -1"; }

Mając kod DFS to max minuta roboty

0

Uuu nie doczytałem, zamień sobie 'wypisz' na 'zapisz w tablicy'

0

kombinuje, bo podstawowy problem to nie jak to zrobic jakos, ale:

adasiek napisał(a)

wykodzilem coś z dfs'em, ale starnie wolno działą

0

quetzalcoatl, DFS i tak byłby szybszy
"szukasz w mapie wierzcholka" - kosztuje (zbiór)
"nalezy scalic te skladowe w jedna" - kosztuje (kolejny zbiór).

Ogólnie każda operacja na mapach kosztuje, a będzie ich proporcjonalnie dużo do kroków DFS'a.
Graf sam w sobie jest zbiorem i szkoda tworzyć dodatkowe zbiory.

Poza tym, co tu może być wolnego ?? Przy 10 sąsiedztwach to będą milisekundy.

0

moj pomysl zakladal przetwarzanie w trakcie czytania listy krawedzi i 'kolorowanie' ich na biezaco..
po dokladniejszym przemysleniu -- wydaje mi sie, ze dla malej ilosci skladowych moglby byc szybszy, zas dla duzej -- rzeczywiscie, na pewno bedzie wolniejszy, bo update indeksu kolorow wierzcholkow przy scalaniu bedzie szeregiem:) ups, pardon

0
quetzalcoatl napisał(a)

ups, pardon
nie koniecznie :) Jeśli właśnie by założyć, że zadanie polega jedynie na pogrupowaniu wierzchołków ze względu na spójność (z samym grafem nie będziemy robić już nic więcej) to nawet lepsiejsze byłby mapy, mniej kodu.

1 użytkowników online, w tym zalogowanych: 0, gości: 1