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

Java   3 Июль 2015  Автор статьи: admin 

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

1
2
3
ArrayList<Integer> adj[]; //список смежности
boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
Queue<Integer>; //очередь для добавления вершин при обходе в ширину

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BFS {
   
    private int n; //количество вершин в орграфе
    private int m; //количество дуг в орграфе
    private ArrayList<Integer> adj[]; //список смежности
    private boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
    private Queue<Integer> queue; //очередь для добавления вершин при обходе в ширину
   
    private BufferedReader cin;
    private PrintWriter cout;
    private StringTokenizer tokenizer;
   
    //процедура обхода в ширину
    private void bfs(int v) {
        if (used[v]) { //если вершина является пройденной, то не производим из нее вызов процедуры
            return;
        }
        queue.add(v); //начинаем обход из вершины v
        used[v] = true; //помечаем вершину как пройденную
        while (!queue.isEmpty()) {
            v = queue.poll(); //извлекаем вершину из очереди
            cout.print((v + 1) + " ");
            //запускаем обход из всех вершин, смежных с вершиной v
            for (int i = 0; i < adj[v].size(); ++i) {
                int w = adj[v].get(i);
                //если вершина уже была посещена, то пропускаем ее
                if (used[w]) {
                    continue;
                }
                queue.add(w); //добавляем вершину в очередь обхода
                used[w] = true; //помечаем вершину как пройденную
            }
        }
    }
   
    //процедура считывания входных данных с консоли
    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<Integer>();
        }
       
        //считываем граф, заданный списком ребер
        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);
       
        queue = new LinkedList<Integer>();
    }
   
    private void run() throws IOException {
        readData();
        for (int v = 0; v < n; ++v) {
            bfs(v);
        }
       
        cin.close();
        cout.close();
    }
   
    public static void main(String[] args) throws IOException {
        BFS solution = new BFS();
        solution.run();
    }
}

 

Пример

Рассмотрим работу алгоритма на графе G, изображенном на рисунке.

pic5

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

Входные данные
8 9
1 2
1 4
2 3
3 4
3 5
3 6
5 7
6 7
7 8
Выходные данные
1 2 4 3 5 6 7 8

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++