Scadenţă: săpt. 7-8
Rezolvaţi problemele asignate, din cele două liste de mai jos. În plus, puteţi rezolva dintre problemele suplimentare (pentru bonificaţii) de la sfârşitul paginii. Utilizaţi tipul abstract de date de la laboratorul 1; modificaţi-l la nevoie.
Lista 1 - Componente conexe şi drumuri de lungime minimă
1. Scrieţi un program care, dându-se un graf şi două vârfuri, determină un drum de cost minim între vârfurile date, utilizând parcurgerea în lăţime mergând de la vârful de start spre înainte.
2. Scrieţi un program care, dându-se un graf şi două vârfuri, determină un drum de cost minim între vârfurile date, utilizând parcurgerea în lăţime căutând invers, de la vârful final spre înapoi.
3. Scrieţi un program care determină componentele conexe ale unui graf neorientat, utilizând o parcurgere în adâncime înspre înainte.
4. Scrieţi un program care determină componentele conexe ale unui graf neorientat, utilizând o parcurgere în adâncime inversată (înspre înapoi).
5. Scrieţi un program care determină componentele conexe ale unui graf neorientat, utilizând o parcurgere în lăţime înspre înainte.
6. Scrieţi un program care determină componentele conexe ale unui graf neorientat, utilizând o parcurgere în lăţime inversată (înspre înapoi).
Lista 2 - drumuri de cost minim
1. Scrieţi un program care, dându-se un graf cu costuri pozitive şi două vârfuri, determină un drum de cost minim între cele două vârfuri, utilizând algoritmul lui Dijkstra.
2. Scrieţi un program care, dându-se un graf cu costuri pozitive şi două vârfuri, determină un drum de cost minim între cele două vârfuri, utilizând algoritmul lui Dijkstra "inversat" (căutare înapoi, de la vârful final).
3. Scrieţi un program care, dându-se un graf cu costuri şi două vârfuri, determină un drum de cost minim între cele două vârfuri sau tipăreşte un mesaj dacă există cicluri de cost negativ accesibile din vârful de start. Utilizaţi o matrice definită prin d[x,k]=costul drumului de cost minim de la s la x şi de lungime cel mult k, unde s este vârful de start.
4. Scrieţi un program care, dându-se un graf cu costuri şi două vârfuri, determină un drum de cost minim între cele două vârfuri sau tipăreşte un mesaj dacă există cicluri de cost negativ accesibile din vârful de start. Utilizaţi o matrice definită prin d[x,k]=costul drumului de cost minim de la s la x şi de lungime exact k, unde s este vârful de start.
5. Scrieţi un program care, dându-se un graf cu costuri şi două vârfuri, determină un drum de cost minim între cele două vârfuri sau tipăreşte un mesaj dacă există cicluri de cost negativ accesibile din vârful de start. Utilizaţi algoritmul lui Ford.
6. Scrieţi un program care, dându-se un graf cu costuri şi două vârfuri, determină un drum de cost minim între cele două vârfuri sau tipăreşte un mesaj dacă există cicluri de cost negativ accesibile din vârful de start. Utilizaţi algoritmul cu înmulţirea matricilor.
7. Scrieţi un program care, dându-se un graf cu costuri, în care nu există cicluri de cost negativ, şi două vârfuri, determină un drum de cost minim între cele două vârfuri sau tipăreşte un mesaj dacă există cicluri de cost negativ accesibile din vârful de start. Utilizaţi algoritmul Floyd-Warshall.
Probleme suplimentare (bonificaţie)
1B. Scrieţi un program care determină componentele tare conexe ale unui graf orientat, în timp O(n+m) (n=nr. vârfuri, m=nr. arce).
2B. Scrieţi un program care determină componentele biconexe ale unui graf în timp O(n+m).
3B. Scrieţi un program care, dându-se un graf cu costuri, în care nu există cicluri de cost negativ, şi două vârfuri, determină numărul de drumuri (nu neapărat elementare) distincte, de cost minim, între cele două vârfuri.
4B. Scrieţi un program care, dându-se un graf cu costuri şi fără cicluri (graf orientat aciclic) şi două vârfuri, determină numărul de drumuri distincte, de cost minim, între cele două vârfuri.
Radu-Lucian LUPŞA