Cách duyệt đồ thị theo chiều rộng Java

Cách duyệt đồ thị theo chiều rộng BFS

Thuật toán duyệt đồ thị theo chiều sâu DFS, mình không nói về lý thuyết nữa vì lý thuyết có trong quyển  sách của thầy Lê Mình Hoàng rồi mọi người tải về xem nhé.

File graph.inp 

8 7 1 5

1 2

1 3

2 3

2 4

3 5

4 6

7 8 

Sau đây là phần code của thuật toán duyệt đồ thị theo chiều rộng BFS :

Cách 1:

package graph;

import java.io.*;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class BFS {

    private static final String pathIn = "graph.inp";
    private static final String pathOut = "graph.out";
    private static int n, m, start, end;
    private static int[][] arrays;
    private static  PrintWriter printWriter;
    public static int[] free;
    public static int[] back;
    public static Queue queues = new LinkedList<>();
    public static StringBuffer str = new StringBuffer();

    public static void BSF(int s) {
        queues.add(s);
        free[s] = 1;
        while (!queues.isEmpty()) {
            int u = queues.poll();
            for (int v = 0; v < n; v++) {
                if(free[v] == 0 && arrays[u][v] != 0) {
                    free[v] = 1;
                    back[v] = u;
                    queues.add(v);
                    str.append(", "+v);
                }
            }
        }

    }

    public static void main(String[] args) {

        ReadFile();
        for (int i = 0; i < n; i++) {
            free[i] = 0;
        }
        free[start] = 1;
        BSF(start);

        try {
            printWriter = new PrintWriter(pathOut,"UTF-8");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }

        System.out.println("From 1 you can visit: "+str.toString());
        printWriter.println("From 1 you can visit: "+str.toString());

        int i = end;
        System.out.print("-"+end);
        printWriter.print(end);
        while (start != end) {
            end = back[end];
            System.out.print("-"+end);
            printWriter.print("-"+end);
        }

        printWriter.close();

    }

    public static void ReadFile() {
        try {

            FileReader reader = new FileReader(pathIn);
            BufferedReader bufferedReader = new BufferedReader(reader);

            String lineStr = bufferedReader.readLine();

            n = Integer.parseInt(lineStr.split(" ")[0]);
            m = Integer.parseInt(lineStr.split(" ")[1]);
            start = Integer.parseInt(lineStr.split(" ")[2]);
            end = Integer.parseInt(lineStr.split(" ")[3]);

            arrays = new int[n+1][n+1];
            free = new int[n+1];
            back = new int[n+1];
            str.append(start);

            int u = 0, v = 0;
            for(int i = 0; i < m; i++) {
                lineStr = bufferedReader.readLine();
                u = Integer.parseInt(lineStr.split(" ")[0]);
                v = Integer.parseInt(lineStr.split(" ")[1]);
                arrays[u][v] = 1;
                arrays[v][u] = 1;
            }

            reader.close();

        } catch (IOException e) {
            e.printStackTrace();
        }
    }


}

Cách 2 duyệt đồ thị theo chiều rộng BFS :

package graph;

import java.io.*;
import java.util.Queue;
import java.util.Scanner;

public class BreadthFirstSearch {

    private static final String InputFile = "graph.inp";
    private static final String OutputFile = "PATH.OUT";
    private static final int Max = 100;

    private boolean[][] A;
    private int[] Trace;
    private int n, Start, Finish;

    private PrintWriter out;

    public BreadthFirstSearch() {
        A = new boolean[Max][Max];
        Trace = new int[Max];


        Enter();

        FileOutputStream fo = null;
        try {
            fo = new FileOutputStream(OutputFile);
            if (fo == null) {
                PrintWriter writer = null;
                try {
                    writer = new PrintWriter(OutputFile, "UTF-8");
                } catch (UnsupportedEncodingException e) {
                    e.printStackTrace();
                }
                writer.close();
                fo = new FileOutputStream(OutputFile);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        out = new PrintWriter(fo);


        Trace[Start] = -1;
        BFS();
        Result();

        out.close();
    }

    private void Enter() {
        FileInputStream fi = null;
        try {
            fi = new FileInputStream(InputFile);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        Scanner inp = new Scanner(fi, "UTF-8");

        String[] st = inp.nextLine().split(" ");

        n = Integer.parseInt(st[0]);
        int m = Integer.parseInt(st[1]);
        Start = Integer.parseInt(st[2]);
        Finish = Integer.parseInt(st[3]);

        for (int i = 0; i < m; i++) {

            String[] tmp = inp.nextLine().split(" ");
            int U = Integer.parseInt(tmp[0]);
            int V = Integer.parseInt(tmp[1]);
            A[U][V] = true;
            A[V][U] = true;
        }
        inp.close();

    }

    private void BFS() {

        int[] Queue = new int[Max];
        int Front = 1, Rear = 1;

        Queue[1] = Start;

        Trace[Start] = -1;

        while (Front <= Rear){
            int U = Queue[Front];
            Front++;
            for (int V = 0; V < n; V++) {
                if(A[U][V] && Trace[V]==0){
                    Rear++;
                    Queue[Rear] = V;
                    Trace[V] = U;
                }
            }
        }

    }

    private void Result() {
        out.println("Từ " + Start + " bạn có thể tới : ");
        for (int V = 0; V < n; V++) {
            if (Trace[V] != 0) {
                out.print(V + ", ");
            }
        }
        out.println();
        out.println("Đường đi từ " + Start + " đến " + Finish + " : ");
        if (Trace[Finish] == 0) {
            out.println("not found");
        } else {
            while (Finish != Start) {
                out.print(Finish + " - ");
                Finish = Trace[Finish];
            }
            out.println(Start);
        }
    }

    public static void main(String args[]) {
        new BreadthFirstSearch();
    }
}

Like và share để ủng hộ blog nhé :D