Aplicare grafuri

[•Mitza444]

Am si eu o intrebare.Cum se pot aplica grafurile pe probleme gen insule de la OJI 2009 sau ai de OJI 2011 ??Am citit teoria grafurilor(http://campion.edu.ro/arhiva/www/arhiva_2009/seds/17/index.htm) de pe .campion ,dar nu prea imi dau seama cum se poate aplica pe probleme de genul celor de mai sus(poate mai imi puteti da ceva de citit de unde sa inteleg mai bine).Stiu ca se pot rezolva cu Lee sau fill unele ,dar am vazut ca desi la indicatii pe .campion da Lee pe  infoarena arata ca se rezolva cu grafuri(si is curios cum se pot aplica:D).
Ma puteti ajuta cu niste explicatii si eventual niste probleme de inceput cu grafuri daca credeti ca insule si ai sunt prea complicate pt inceput ??

[•SpiderMan]

Se rezolva cu algoritmul lui Lee (modificat pentru fiecare pb. in parte), care e de fapt o "reducere" a algoritmului de parcurgere in latime (grafuri), doar pe matrice. Nu trebuie sa inveti grafuri sa faci aceste probleme, grafurile sunt clasele 11-12 iar Lee clasa 10. Daca vrei mai multe detalii despre algoritm poti sa vezi diversele problemele pe infoarena (gen rj, muzeu etc.), sau sa cauti pe net (sunt probleme cu solutii explicate).

[•MciprianM]

Salut!
Intr-adevar, din cate tin minte - nu ai nevoie sa stii grafuri ca sa rezolvi probleme care se pot rezolva cu Lee (Lee nu e algoritmul ala cu "3 foruri" )
Totusi e mai usor daca stii putina teoria grafurilor sa te gandesti in termeni de grafuri (si poti rezolva si variatiuni care nu merg cu un simplu Lee).

Pe scurt:
Celulele matricii le consideri noduri in graf, iar doua noduri sunt conectate printr-o muchie, daca celulele corespunzatoare sunt adiacente(de obicei - dar cum am mai spus pot exista si variatiuni).
Acuma daca tu vrei sa determini drumul minim intre doua celule din matrice trebuie sa determini drumul minim intr-un graf neorientat fara costuri (Hint: Foloseste BFS(Breafth First Search sau algoritmul de cautare in latime)).
In variatiuni ale problemei pot sa existe costuri, de exemplu la trecerea dintr-o celula in alta(de exemplu intr-o matrice cu valori, daca ti se cere sa treci din celula x in celula y, iar costul trecerii din celula a in celula b e diferenta in modul dintre valorile aflate in cele doua celule). Si atunci muchiile in graf au costurile corespunzatoare, iar drumul minim il gasesti cu un algoritm din teoria grafurilor(in cazul de fata Dijkstra ar fi cel mai potrivit - fiecare celula are cel mult 4 vecini asa ca numarul de muchii este mic - mai mic decat 4*n unde n este numarul de celule; totusi atentie Dijkstra functioneaza doar daca costurile de pe muchii sunt nenegative).

Iarasi o variatiune:
Daca ai o matrice care are trei tipuri de celule (obstacol, celula magica si celula obisnuita) si poti face trecerea intre doua celule daca sunt adiacente sau daca sunt celule magice de acelasi tip(avem mai multe tipuri de celule magice) - si bineinteles ca nu poti sa intri intr-o celula obstacol, atunci ai un graf tot neorientat fara costuri, doar ca ai cateva muchii in plus intre celulele magice de acelasi tip. La fel problema ar fi sa gasesti un drum minim.

Alta variatiune ca si problema insule iti poate cere numarul de componente conexe(orice algoritm de cautare merge in latime sau adancime, adica BFS sau DFS) - o componenta conexa in problema insule fiind o insula. (pentru componente conexe nu iei apa ca fiind nod). Pentru pod, trebuie sa determini distanta minima intre doua insule. Pentru asta nu exista un algoritm standard - dar te poti gandi cum poti sa adaptezi algoritmii de drum minim problemei date.

Sper ca te ajuta ce am scris.

[•Mitza444]

Multumesc pt. explicatii .Nu imi puteti recomanda si niste probleme cu grafuri ca sa le mai exersez si astfel cred ca o sa le si inteleg mai bine.

[•scipianus]

Multumesc pt. explicatii .Nu imi puteti recomanda si niste probleme cu grafuri ca sa le mai exersez si astfel cred ca o sa le si inteleg mai bine.

Ai aici o lista a problemelor de pe campion care au legatura cu grafurile (au fost tag-uite cu categoria "graf") http://campion.edu.ro/arhiva/index.php?page=keyword&action=view&id=21