Заданий неорієнтовані граф, що складається з вершин і ребер. Вихідний граф задається списком ребер. Потрібно зробити обхід в глибину з усіх ще не відвіданих вершин графа в порядку збільшення їх номери.
З метою здійснення обходу в глибину вихідний граф зручно представляти в пам'яті ЕОМ списком суміжності, зберігаючи для кожної вершини графа список суміжних з нею вершин. Булевський масив служить для позначки про те, стала вершина відвідується в процесі обходу в глибину або ще немає. При цьому, якщо, то вершина є відвідується, якщо, то немає.
ArrayList adj []; // список суміжності
boolean used []; // масив для зберігання інформації про пройдені і не пройдених вершинах
Як списку суміжності для представлення графа на мові Java зручно використовувати масив, кожен елемент якого є структурою даних.
У наведеній нижче реалізації дані зчитуються і виводяться в консоль.
У першому рядку вхідного файлу задано два цілих числа: - кількість вершин в графі і - кількість ребер графа відповідно. Кожна з наступних рядків містить опис ребра графа - два цілих числа з діапазону від до - номери-решт ребра.
У рядку вихідного файлу показані вершини графа в порядку обходу в глибину, починаючи з першої вершини.
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;
public class Solution
private int n; // кількість вершин в орграфе
private int m; // кількість дуг в Орграф
private ArrayList adj []; // список суміжності
private boolean used []; // масив для зберігання інформації про пройдені і не пройдених вершинах
private BufferedReader cin;
private PrintWriter cout;
private StringTokenizer tokenizer ;;
// процедура обходу в глибину
private void dfs (int v) // якщо вершина є пройденої, то не робимо з неї виклик процедури
if (used [v]) return;
>
used [v] = true; // помічаємо вершину як пройдену
cout.print ((v + 1) + "");
// запускаємо обхід з усіх вершин, суміжних з вершиною v
for (int i = 0; i ();
>
// зчитуємо граф, заданий списком ребер
for (int i = 0; i
Розглянемо роботу алгоритму обходу в глибину на графі, зображеному на малюнку зліва. Після роботи алгоритму на вихідному графі буде побудований ліс обходу в глибину, зображений на малюнку справа.
