Shulou(Shulou.com)06/01 Report--

This article mainly introduces "Java depth-first traversal and breadth-first traversal how to understand", in daily operation, I believe many people in Java depth-first traversal and breadth-first traversal how to understand the problem there are doubts, Xiaobian consulted all kinds of information, sorted out simple and easy to use operation methods, hope to answer "Java depth-first traversal and breadth-first traversal how to understand" doubts helpful! Next, please follow the small series to learn together!

Common concepts of graphs

A graph is a data structure in which nodes can have zero or more adjacent elements. The connection between two nodes is called an edge. Nodes can also be called vertices.

Vertex

edge

path

undirected graph

directed graph

weighted graph

Representation of graphs

There are two ways to represent graphs: two-dimensional array representation (adjacency matrix); linked list representation (adjacency list).

adjacency matrix

An adjacency matrix is a matrix representing the adjacency relationship between vertices in a graph. For a graph with n vertices, the matrix is row and col represent 1... N points.

adjacency list

An adjacency matrix needs to assign n edges to each vertex. In fact, many edges do not exist, which will cause a certain loss of space.

The implementation of adjacency tables cares only about edges that exist, not about edges that do not exist. So there is no wasted space, adjacency lists consist of arrays + linked lists

code implementation package com.guizimo;import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;public class Graph { private ArrayList vertexList; private int[][] edges; private int numOfEdges; private boolean[] isVisited; public static void main(String[] args) { int n = 8; String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"}; Graph graph = new Graph(n); for(String vertex: Vertexs) { graph.insertVertex(vertex); } //insert nodes of graph graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.insertEdge(3, 7, 1); graph.insertEdge(4, 7, 1); graph.insertEdge(2, 5, 1); graph.insertEdge(2, 6, 1); graph.insertEdge(5, 6, 1); //Traverse graph graph.showGraph(); System.out.println("breadth-first traversal graph.dfs(); System.out.println("depth-first traversal graph.bfs(); } public Graph(int n) { edges = new int[n][n]; vertexList = new ArrayList(n); numOfEdges = 0; } public int getFirstNeighbor(int index) { for(int j = 0; j

< vertexList.size(); j++) { if(edges[index][j] >

0) { return j; } } return -1; } public int getNextNeighbor(int v1, int v2) { for(int j = v2 + 1; j

< vertexList.size(); j++) { if(edges[v1][j] >

0) { return j; } } return -1; } //depth-first traversal private void dfs(boolean[] isVisited, int i) { System.out.print(getValueByIndex(i) + "->"); isVisited[i] = true; int w = getFirstNeighbor(i); while(w != -1) { if(! isVisited[w]) { dfs(isVisited, w); } w = getNextNeighbor(i, w); } } public void dfs() { isVisited = new boolean[vertexList.size()]; for(int i = 0; i

< getNumOfVertex(); i++) { if(!isVisited[i]) { dfs(isVisited, i); } } } //广度优先遍历 private void bfs(boolean[] isVisited, int i) { int u ; int w ; LinkedList queue = new LinkedList(); System.out.print(getValueByIndex(i) + "=>

"); isVisited[i] = true; queue.addLast(i); while( ! queue.isEmpty()) { u = (Integer)queue.removeFirst(); w = getFirstNeighbor(u); while(w != -1) { if(! isVisited[w]) { System.out.print(getValueByIndex(w) + "=>"); isVisited[w] = true; queue.addLast(w); } w = getNextNeighbor(u, w); } } } public void bfs() { isVisited = new boolean[vertexList.size()]; for(int i = 0; i

< getNumOfVertex(); i++) { if(!isVisited[i]) { bfs(isVisited, i); } } } public int getNumOfVertex() { return vertexList.size(); } //遍历 public void showGraph() { for(int[] link : edges) { System.err.println(Arrays.toString(link)); } } public int getNumOfEdges() { return numOfEdges; } public String getValueByIndex(int i) { return vertexList.get(i); } public int getWeight(int v1, int v2) { return edges[v1][v2]; } //添加邻接矩阵 public void insertVertex(String vertex) { vertexList.add(vertex); } //插入权值 public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }}图的深度优先搜索(Depth First Search) 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点 算法 访问初始结点v，并标记结点v为已访问。 查找结点v的第一个邻接结点w。 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。 查找结点v的w邻接结点的下一个邻接结点，转到步骤3 代码//深度优先遍历private void dfs(boolean[] isVisited, int i) { System.out.print(getValueByIndex(i) + "->

"); isVisited[i] = true; int w = getFirstNeighbor(i); while(w != -1) { if(! isVisited[w]) { dfs(isVisited, w); } w = getNextNeighbor(i, w); }}public void dfs() { isVisited = new boolean[vertexList.size()]; for(int i = 0; i

< getNumOfVertex(); i++) { if(!isVisited[i]) { dfs(isVisited, i); } }}图的广度优先搜索(Broad First Search) 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点 算法 访问初始结点v并标记结点v为已访问。 结点v入队列 当队列非空时，继续执行，否则算法结束。 出队列，取得队头结点u。 查找结点u的第一个邻接结点w。 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤： 若结点w尚未被访问，则访问结点w并标记为已访问。 结点w入队列 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6 代码//广度优先遍历private void bfs(boolean[] isVisited, int i) { int u ; int w ; LinkedList queue = new LinkedList(); System.out.print(getValueByIndex(i) + "=>

"); isVisited[i] = true; queue.addLast(i); while( ! queue.isEmpty()) { u = (Integer)queue.removeFirst(); w = getFirstNeighbor(u); while(w != -1) { if(! isVisited[w]) { System.out.print(getValueByIndex(w) + "=>"); isVisited[w] = true; queue.addLast(w); } w = getNextNeighbor(u, w); } }} public void bfs() { isVisited = new boolean[vertexList.size()]; for(int i = 0; i < getNumOfVertex(); i++) { if(! isVisited[i]) { bfs(isVisited, i); } }} At this point, the study of "Java depth-first traversal and breadth-first traversal" is over, hoping to solve everyone's doubts. Theory and practice can better match to help you learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

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.