Обход в глубину (реализация на Java)
Задан неориентированный граф, состоящий из вершин и
ребер. Исходный граф задается списком ребер. Требуется произвести обход в глубину из всех еще не посещенных вершин графа в порядке увеличения их номера.
С целью осуществления обхода в глубину исходный граф удобно представлять в памяти ЭВМ списком смежности
, храня для каждой вершины графа
список
смежных с ней вершин. Булевский массив
служит для отметки о том, стала вершина
посещенной в процессе обхода в глубину или еще нет. При этом, если
, то вершина
является посещенной, если
, то нет.
ArrayList
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
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 < adj[v].size(); ++i) {
int w = adj[v].get(i);
dfs(w); //вызов обхода в глубину от вершины w, смежной с вершиной v
}
}
//процедура считывания входных данных с консоли
private void readData() throws IOException {
cin = new BufferedReader(new InputStreamReader(System.in));
cout = new PrintWriter(System.out);
tokenizer = new StringTokenizer(cin.readLine());
n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа
m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа
//инициализируем список смежности графа размерности n
adj = new ArrayList[n];
for (int i = 0; i < n; ++i) {
adj[i] = new ArrayList
}
//считываем граф, заданный списком ребер
for (int i = 0; i < m; ++i) {
tokenizer = new StringTokenizer(cin.readLine());
int v = Integer.parseInt(tokenizer.nextToken());
int w = Integer.parseInt(tokenizer.nextToken());
v--;
w--;
adj[v].add(w);
adj[w].add(v);
}
used = new boolean[n];
Arrays.fill(used, false);
}
private void run() throws IOException {
readData();
for (int v = 0; v < n; ++v) {
dfs(v);
}
cin.close();
cout.close();
}
public static void main(String[] args) throws IOException {
Solution solution = new Solution();
solution.run();
}
}
Рассмотрим работу алгоритма обхода в глубину на графе , изображенном на рисунке слева. После работы алгоритма на исходном графе
будет построен лес обхода в глубину
, изображенный на рисунке справа.
Входные данные |
---|
11 13 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 9 6 10 6 11 7 10 7 11 |
Выходные данные |
1 2 4 8 9 5 3 6 10 7 11 |