Duyệt đồ Thị Theo Chiều Sâu Java - Jundat95

Trang chủ » Duyệt đồ Thị Dfs » Duyệt đồ Thị Theo Chiều Sâu Java - Jundat95

Có thể bạn quan tâm

Jundat95

System.out.print('Hello world!');

Header Ads

  • Home
    • Knowledge
    • _Android
    • _React Native
    • _IOS
    • _Java
    • _JavaScript
    • _C#
    • _HTML
    • Operating system
    • _Windows
    • _Ubuntu
    • Tutorial
    • Tools
    • Ebook
    Home Algorithm Học Tập Duyệt đồ thị theo chiều sâu Java Duyệt đồ thị theo chiều sâu Java October 22, 2017 Algorithm, Học Tập

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

    graph DFS

    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

    Related Posts

    Học Tập

    Post a Comment

    No comments

    Subscribe to: Post Comments ( Atom )

    Translate

    STAY WITH US

    • 114 followers
    • 250 followers
    • 500 likes
    • 0 followers
    • 1000 subscribers
    • 266 followers

    Facebook

    Popular Posts

    • Đề thi trắc nghiệm quản lý dự án công nghệ thông tin Đề thi trắc nghiệm quản lý dự án công nghệ thông tin Đề thi trắc nghiệm quản lý dự án công nghệ thông tin  Cau1 Ai có trách nhiệm chuẩn bị báo cáo đánh giá sau triển khai? A. Ngư...
    • [Ebook] Giáo trình lập trình C++ nâng cao [Ebook] Giáo trình lập trình C++ nâng cao Giáo trình lập trình C/C++ nâng cao  Giáo trình dành cho các bạn yêu thích tìm tòi học hỏi, và đặc biệt yêu thích ngôn ngữ c++ Yêu...
    • Bài Tập Trắc Nghiệm Lập Trình C, Có Đáp Án. Bài Tập Trắc Nghiệm Lập Trình C, Có Đáp Án. Bài Tập Trắc Nghiệm Lập Trình C, Có Đáp Án.    L ink tải bài tập trắc nghiệm C. https://mega.co.nz/#!xJMnWCZI!gp3gYnCVqy9UD-cdX...
    • Hướng dẫn cài đặt docker trên ubuntu 19.04 Hướng dẫn cài đặt docker trên ubuntu 19.04 Hướng dẫn cài đặt docker trên ubuntu 19.04 Hướng dẫn cài đặt Docker trên ubuntu 19.04 đơn giản. 1, Chạy các lệnh sau để cài đặt b...

    Arquivo do blog

    • ▼  2017 (35)
      • ▼  October (7)
        • Cách duyệt đồ thị theo chiều rộng Java
        • Duyệt đồ thị theo chiều sâu Java
        • Java fibonacci algorithm
        • Xử lý xự kiện bấm vào Listview trong app Todo
        • Custom ListView trong Android làm app Todo
        • Thêm dữ liệu vào SQLite Android làm app Todo
        • Hướng dẫn sử dụng SQLite làm app todo trong android

    Recent Posts

    Recent Comments

    Created By Tinh Ngo

    Từ khóa » Duyệt đồ Thị Dfs