Cybern8.com » Обход в глубину (реализация на Java)

Обход в глубину (реализация на Java)

Java

21 марта 2015 Автор статьи: admin

Статья
Комментарии (0)

Задан неориентированный граф, состоящий из $N$ вершин и $M$ ребер. Исходный граф задается списком ребер. Требуется произвести обход в глубину из всех еще не посещенных вершин графа в порядке увеличения их номера.
С целью осуществления обхода в глубину исходный граф $G$ удобно представлять в памяти ЭВМ списком смежности $adj$ , храня для каждой вершины графа $v$ список $adj[v]$ смежных с ней вершин. Булевский массив $used$ служит для отметки о том, стала вершина $v$ посещенной в процессе обхода в глубину или еще нет. При этом, если $used[v] = true$ , то вершина $v$ является посещенной, если $used[v] = false$ , то нет.

ArrayList adj[]; //список смежности boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах

В качестве списка смежности для представления графа на языке Java удобно использовать массив, каждый элемент которого является структурой данных $ArrayList<Integer>$ .
В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано два целых числа: $N (1 \le N \le 10^5)$ – количество вершин в графе и $M (1 \le M \le 10^6)$ – количество ребер графа соответственно. Каждая из следующих $M$ строк содержит описание ребра графа – два целых числа из диапазона от $1$ до $N$ – номера концов ребра.

Выходные данные

В строке выходного файла показаны вершины графа в порядке обхода в глубину, начиная с первой вершины.

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 < 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(); } }

Пример

Рассмотрим работу алгоритма обхода в глубину на графе $G$ , изображенном на рисунке слева. После работы алгоритма на исходном графе $G$ будет построен лес обхода в глубину $G_\pi$ , изображенный на рисунке справа.