How to implement the traversal of graphs by Java

This article mainly introduces how to achieve Java map traversal, the article introduces in great detail, has a certain reference value, interested friends must read it!

1. Traversal of graphs

Access the remaining vertices in the graph from one of the vertices in the graph, and each vertex is accessed only once

There are two kinds of graph traversal: depth-first traversal DFS and breadth-first traversal BFS.

two。 Depth first traversal

Depth first traversal takes depth as priority to traverse, which simply means going to the end each time. Preorder traversal similar to binary tree

Train of thought:

1. Do a depth-first traversal from a vertex and mark that the vertex has been accessed

two。 Take this vertex as the starting point, select any path to traverse to the end, and mark the visited vertices

3. Step 2 iterate through to the end, then fall back to the previous vertex, repeat step 2

4. Traverse the end of all vertices

According to the traversal idea, this is a recursive process, in fact, DFS and backtracking are basically the same.

Traverse:

Use this graph as an example for depth-first traversal

Static void dfs (int [] [] graph,int idx,boolean [] visit) {int len = graph.length; / / visited if (Visit[ IDX]) return; / / visited the vertex System.out.println ("V" + idx); / / marked vertex visit [idx] = true; for (int I = 1bot I < len If (graph [IDX] [I] = = 1) {/ / Recursive dfs traversal dfs (graph, I, visit);}

Traversal results:

V1

V2

V3

V4

V5

V6

V7

V8

V9

The code to create the diagram:

Public static void main (String [] args) {Scanner scanner = new Scanner (System.in); / / the number of vertices begins with 1 int n = scanner.nextInt (); int [] [] graph = new int [nasty 1] [nasty 1]; / / number of sides int m = scanner.nextInt () For (int I = 1 position I)