Duyệt đồ thị theo chiều sâu Java

Duyệt đồ thị theo chiều sâu Java

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

File Code Duyệt chiều sâu DFS:

Cách một duyệt theo chiều sâu DFS:

package graph;

import java.io.*;

public class DFS {

    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 int[] back;
    private static PrintWriter printWriter;

    public static void DFS(int u) {
        int v;
        for (v = 0;  v < n; v++) {
            if(arrays[u][v] == 1 && back[v] == 0) {
                back[v] = u;
                DFS(v);
            }
        }

    }

    public static void main(String[] args) {
        ReadFile();
        for (int i = 0; i < n; i++){
            back[i] = 0;
        }
        back[start] = 1;
        DFS(start);

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

        printWriter.print(""+end);

        while (start != end) {
            end = back[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];
            back = new int[n+1];

            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 sâu DFS:

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


public class DepthFirstSearch {

    private static final String InputFile = "PATH.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 DepthFirstSearch() {
        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;
        DFS(Start);
        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 DFS(int U) {
        for (int V = 0; V < n; V++) {
            if (A[U][V] && Trace[V] == 0) {
                Trace[V] = U;
                DFS(V);
            }
        }
    }

    private void Result() {
        out.println("From " + Start + " you can visit: ");
        for (int V = 0; V < n; V++) {
            if (Trace[V] != 0) {
                out.print(V + ", ");
            }
        }
        out.println();
        out.println("The path from " + Start + " to " + 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 DepthFirstSearch();
    }
}

Hãy like và share fanpage để ủng hộ blog nhé :D