Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to use Java depth-first and breadth-first traversal". In daily operation, I believe many people have doubts about how to use Java depth-first and breadth-first traversal. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts of "Java depth-first and breadth-first traversal". Next, please follow the editor to study!

# traversal

The traversal of the graph, the so-called traversal, is the access to the node. There are so many nodes in a graph. How to traverse these nodes requires a specific policy. Generally, there are two access policies:

Depth first traversal

Breadth first traversal # depth first

Depth-first traversal, starting from the initial access node, we know that the initial access node may have multiple adjacency nodes, and the strategy of depth-first traversal is to visit the first adjacency node first, and then use the accessed adjacency node as the initial node to visit its first adjacency node. To sum up, it can be said that every time after visiting the current node, the first adjacent node of the current node is visited first. We can see from here that such an access strategy gives priority to vertical mining rather than horizontal access to all adjacent nodes of a node. The specific algorithm is as follows:

Access the initial node v and mark node v as visited.

Find the first adjacency node w of node v.

If w exists, continue to execute 4, otherwise the algorithm ends.

If w is not accessed, depth-first traversal recursion is performed on w (that is, w is regarded as another v, and then step 123).

Find the next adjacency node of the w adjacency node of node v and go to step 3.

For example, in the following figure, the depth-first traversal order is 1-> 2-> 4-> 8-> 5-> 3-> 6-> 7.

# breadth first

Similar to a hierarchical search process, breadth-first traversal requires the use of a queue to maintain the order of visited nodes in order to access their adjacency nodes in that order. The specific algorithm is as follows:

Access the initial node v and mark node v as visited.

Node v queued

When the queue is not empty, continue execution, otherwise the algorithm ends.

Get out of the queue and get the head node u.

Find the first adjacency node w of node u.

If the adjacency node w of node u does not exist, go to step 3; otherwise, cycle through the following three steps:

1)。 If node w has not been accessed, access node w and mark it as visited.

2)。 Node w is queued

3)。 Find the next adjacency node w after the w adjacency node of the node u and go to step 6.

As shown in the following figure, the traversal order of the breadth-first algorithm is 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8.

Package com.lifeibigdata.algorithms.graph.liantongfenliang;import java.util.LinkedList;import java.util.Queue;/** * Created by leofei.li on 2016-5-21. * / public class BFS {static int verNum; static boolean [] visited; static String [] ver= {"A", "B", "C", "D", "E"}; static int [] [] edge; void addEdge (int itemint j) {if (I = j) return; edge [I] [j] = 1; edge [j] [I] = 1;} void dfsTraverse () {visited = new boolean [verNum] For (int I = 0; I < verNum; I + +) {if (visited[ I] = = false) {dfs (I);}} void dfs (int I) {visited [I] = true; System.out.print (verI + "); for (int j = 0; j < verNum) ) {if (Visited [j] = = false & & edge [I] [j] = 1) {dfs (j);} void bfsTraverse () {visited = new boolean [verNum]; Queue quene = new LinkedList (); for (int I = 0; I < verNum) I + +) {if (visited[ I] = = false) {visited [I] = true; System.out.print (ver[ I] + ""); quene.add (I) / / here is the index while (! quene.isEmpty ()) {/ / Note the end condition int j = quene.poll (); for (int k = 0; k < verNum) Visited +) {/ / find all the children of the node if (edge [j] [k] = = 1 & & visited [k] = = false) {visited [k] = true; System.out.print (verk] + "); quene.add (k) }} void con () {int count = 0; visited = new boolean [verNum]; for (int I = 0; I < verNum; I + +) {if (! visited [I]) {count++; dfsTraverse () }} System.out.println ("common" + count+ "connected components!");} public static void main (String [] args) {verNum = ver.length; edge = new int [verNum] [verNum]; for (int iTuno [I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.