Mulakan dari bucu tertentu dalam graf dan lawati bucu yang tinggal dalam graf, dan setiap bucu hanya dilawati sekali
Terdapat dua jenis kedalaman- traversal pertama dalam traversal graf DFS, traversal breadth-first BFS
Traversal depth-first traversal with depth first, yang bermaksud pergi ke penghujung setiap masa. Sama seperti traversal prapesan pokok binari
Idea:
1. Lakukan traversal mendalam-pertama bermula dari bucu tertentu, dan tandakan bucu sebagai dilawati
2. Gunakan bucu ialah titik permulaan, pilih mana-mana laluan dan lalui ke penghujung, dan tandakan bucu yang dilawati 3. Selepas melintasi ke hujung, kembali ke bucu sebelumnya, dan ulangi langkah 2 4 Tamat melintasi semua bucu Mengikut idea traversal, ini adalah proses rekursif, pada asasnya, DFS adalah sama seperti menjejak ke belakang. Traversal: Ambil gambar ini sebagai contoh untuk melakukan depth-first traversalstatic void dfs(int[][] graph,int idx,boolean[]visit) { int len = graph.length; //访问过 if(visit[idx]) return; //访问该顶点 System.out.println("V"+idx); //标志顶点 visit[idx] = true; for(int i = 1;i < len;i++) { //访问该顶点相连的所有边 if(graph[idx][i] == 1) { //递归进行dfs遍历 dfs(graph, i, visit); } } }
V1V2V3V4V5V6V7Kod untuk mencipta graf:V8V9
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //顶点数 以1开始 int n = scanner.nextInt(); int[][] graph = new int[n+1][n+1]; //边数 int m = scanner.nextInt(); for(int i = 1;i <= m;i++) { int v1 = scanner.nextInt(); int v2 = scanner.nextInt(); graph[v1][v2] = 1; graph[v2][v1] = 1; } //标记数组 false表示未访问过 boolean[] visit = new boolean[n+1]; dfs(graph, 1, visit); }
//默认无环 static boolean flag = false; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //顶点数 以1开始 int n = scanner.nextInt(); int[][] graph = new int[n+1][n+1]; //边数 int m = scanner.nextInt(); for(int i = 1;i <= m;i++) { int v1 = scanner.nextInt(); int v2 = scanner.nextInt(); graph[v1][v2] = 1; } //标记数组 true为访问过 boolean[] visit = new boolean[n+1]; dfs(graph, 1, visit,1); if(flag) System.out.println("有环"); } static void dfs(int[][] graph,int idx,boolean[]visit,int parent) { int len = graph.length; System.out.println("V"+idx); //标记顶点 visit[idx] = true; for(int i = 1;i < len;i++) { //访问该顶点相连的所有边 if(graph[idx][i] == 1) { if( !visit[i] ) { dfs(graph, i, visit,idx); } else if(idx != i) { flag = true; } } } }
Nota: Ia adalah graf terarah untuk menentukan sama ada terdapat kitaran, dan graf tidak terarah untuk menentukan sama ada terdapat kitaran adalah tidak bermakna, kerana mana-mana dua bucu dengan laluan boleh menjadi kitaran
4. . Breadth-first traversal Breadth-first traversal adalah berdasarkan lebar (lebar) sebagai priority Traverse. Serupa dengan lintasan tertib aras bagi pokok binari Idea: 1. Lakukan lintasan lebar-pertama bermula dari bucu tertentu, dan tandakan bucu sebagai dilawati<🎜. >2. Lawati semua Bucu yang disambungkan ke bucu ini dan belum dilawati, dan tandai bucu yang dilawati
3 Ulang langkah 1 dan 2 bermula dari bucu yang dilawati dalam langkah 2
. 4. Lintas semua Hujung bucu
dilalui melalui baris gilir, dan susunan baris gilir adalah hasil lintasan lebar-pertama
Traversal
Ambil gambar ini sebagai contoh, gunakan kaedah matriks bersebelahan untuk mencipta graf dan lakukan traversal BFS
rreeeHasil traversal:
V1V2
V6
V3
V7
V9
V5
V4
V8
Kod untuk mencipta graf
static void bfs(int[][] graph) { int len = graph.length; //标记数组 false表示未访问过 boolean[] visit = new boolean[len]; //辅助队列 Queue<Integer> queue = new LinkedList<>(); queue.offer(1); visit[1] = true; while(!queue.isEmpty()) { int num = queue.poll(); System.out.println("V"+num); //遍历该顶点所有相连顶点 for(int i = 1;i < len;i++) { //相连并且没有被访问过 if(graph[num][i] == 1 && !visit[i]) { queue.offer(i); visit[i] = true; } } } }
Atas ialah kandungan terperinci Bagaimana untuk melaksanakan traversal graf di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!