Se dă un grafic nedirecționat format din vârfuri și muchii. Graficul inițial este dat de lista de margini. Este necesară trecerea în profunzime a tuturor vârfurilor care nu au fost încă vizitate, în scopul creșterii numărului acestora.
Pentru a face o plimbare până la adâncime, graficul inițial este reprezentat convenabil în memoria calculatorului printr-o listă de adjacitate, stocând pentru fiecare vârf al graficului o listă de vârfuri adiacente. Matricea booleană servește pentru a marca dacă topul vizitat în procesul de trecere în adâncime sau nu încă. În acest caz, dacă, atunci este vizitat topul, dacă nu, atunci.
ArrayList adj []; // lista de adjacități
boolean folosit []; // array pentru stocarea informațiilor despre nodurile care au trecut și nu au trecut
Ca o listă de adjuvantă pentru reprezentarea unui grafic în limba Java, este convenabil să se utilizeze o matrice, fiecare element al căreia este o structură de date.
În următoarea implementare, datele sunt citite și afișate în consola.
Prima linie a fișierului de intrare are două numere întregi: - numărul de vârfuri din grafic și - numărul de margini ale graficului respectiv. Fiecare dintre liniile următoare conține o descriere a marginii graficului - două numere întregi de la intervalul până la - numărul de margini ale marginii.
În linia de fișiere de ieșire, vârfurile de grafic sunt afișate în ordinea traversării în profunzime, începând de la primul vârf.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
Soluția publică de clasă
private int n; // numărul de noduri din digraf
private int; // numărul de arce din digraf
privat ArrayList adj []; // lista de adjacități
boolean privat folosit []; // array pentru stocarea informațiilor despre nodurile care au trecut și nu au trecut
private BufferedReader cin;
privat PrintWriter cout;
privat StringTokenizer tokenizer;
// procedura de trecere în profunzime
privat void dfs (int v) // daca vertexul este traversat, nu facem un apel de procedura de la acesta
dacă (returnat [v]) returnat;
>
folosit [v] = adevărat; // marcați vârful ca fiind trecut
cout.print ((v + 1) + "");
// rulați traversalul de la toate nodurile adiacente vârfului v
pentru (int i = 0; i ();
>
// citiți graficul specificat de lista margini
pentru (int i = 0; i
Luați în considerare lucrarea algoritmului de traversare în profunzime pe graficul prezentat în figura din stânga. După ce algoritmul rulează, pădurea de bypass în profunzime, prezentată în figura din dreapta, va fi construită pe graficul inițial.
Articole similare
Trimiteți-le prietenilor: