This is the sixth day of my participation in the August Text Challenge.More challenges in August

This series of articles is a summary of personal learning, if you find mistakes or questions, welcome to comment!

This paper is the sixth in the relearning data structure series, which includes: 1. Time complexity and space complexity of algorithms 2. Relearn data structure — Linked list 3. Relearn data structure — Queue 4. Relearn data structure — Stack 5. Relearn data structures — trees

1. Why is there a picture?

As we know, there are three kinds of relationships between data: one-to-one, one-to-many and many-to-many. The data of the first two relationships can be stored in linear tables and tree structures respectively, while the many-to-many relationship is represented by graphs.

2. Related concepts of graphs

  • The vertices

  • Side: Some parts of the side are also called arcs

    • In directed graphs, the vertices at the arrowhead ends are usually called initial points or arc tails, and the vertices of the arrowhead lines are called endpoints or arc heads.

  • Undirected graph

  • Path: the path of A->C in the figure above:

    • A->C

    • A->B->C

      If the first vertex in a path is the same as the last vertex, the path is called a “loop” (or “loop”).

  • Directed graph

  • Weighted graph: A weighted graph is also called a net

  • Input and output: The input and output of A in the digraph above is 1 and 2

There are two ways to represent a graph: one is represented by a two-dimensional array (adjacency matrix); The other is to use a linked list (adjacency list)

3. Use a two-dimensional array

Edges [v1][v2]=weight. The array edges store the relationship between two vertices, where V1 and v2 represent the number of two vertices respectively. We agree that weight=0 means there is no connection between two vertices. Weight for other values represents the weight between two vertices (there is no weight here and the default weight is 1).

The specific implementation

Public class Graph {// Private ArrayList<String> vertexList; // Store the corresponding adjacent matrix of the graph private int[][] edges; Private int numOfEdges; Public Graph(int n){edges = new int[n][n]; vertexList = new ArrayList<>(n); numOfEdges = 0; } public int getNumOfVertex(){return vertexlist.size (); } public void showGraph(){for (int[] link: edges){system.out.println (arrays.toString (link)); }} public int getNumOfEdges(){return numOfEdges; } /** * public String getValueByIndex(int index){return vertexlist.get (index); } /** * returns the corresponding weights * @param v1 * @param v2 * @return */ public int getWeight(int v1,int v2){return edges[v1][v2]; } @param vertex */ public void insertVertex(String vertex){vertexlist.add (vertex); } public void insertEdge(int v1,int v2,int weight){public void insertEdge(int v1,int v2,int weight){ edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }}Copy the code

test

Public static void main(String[] args) {public static void main(String[] args) {public static void main(String[] args) { / / the number of nodes in the String Vertexs [] = {" A ", "B", "C", "D", "E"}; Graph Graph = new Graph(n); For (String vertex: Vertexs) {graph.insertvertex (vertex); } // add edge // a-b a-c b-c b-d b-e graph.insertedge (0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.showGraph(); }Copy the code

4. Two ways to traverse the graph

1. Depth-first search

Depth-first search is also called deep search or DFS.

Access idea:

  • Depth-first search starts from the initial access node, which may have multiple adjacent nodes. The strategy of depth-first traversal is access first

    The first adjacency is accessed, and the first adjacency is accessed using the accessed adjacency as the initial node, which can be interpreted as:

    Each time, the first adjacent node of the current node is accessed first after the current node is accessed.

  • Such an access strategy is to preferentially dig deep vertically, rather than horizontally access all the adjacent nodes of a node.

  • Obviously, depth-first search is a recursive process

Array storage: String Vertexs [] = {” v1 “, “v2”, “v3”, “v4”, “the v5,” “v6”, “v7”, “v8”};

The depth-first search process is similar to the sequential traversal of trees. For example, the depth-first traversal of the graph is carried out in the figure above. The traversal process is as follows:

  • First, find an arbitrary vertex that has not been traversed. Here, the node v1 is used as the initial node for access, and mark v1 as visited
  • Iterate over the adjacency of V1, V1’s first adjacency is v2, mark v2 has been visited, iterate over the adjacency of v2, v2’s first adjacency is v3, but v2 has no connection to V3, continue the next adjacency is V4 (mark), then V8 (mark), then V5
  • As we continue to traverse v5’s adjacency nodes, all associated adjacency nodes have been accessed based on the previous marks. At this point, back up from V5 to V8 to see if V8 has any unaccessed adjacent nodes. If not, back up to V4, v2, v1.
  • By traversing v1, find an unvisited vertex v3, then access v3’s adjacent node v6, then v7
  • Since v7 has no unvisited adjacent nodes, it falls back to v6, V3, v1, and has no unvisited adjacent nodes
  • The last step is to determine whether all vertices are visited. If there are any unvisited vertices, take the unvisited vertex as the first vertex and continue to traverse in the same way as above.

According to the above process, the traversal order of vertices obtained by depth-first search in the figure above can be obtained as follows:

V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7
Copy the code

The specific implementation

Take the two-dimensional array representation in the figure above as a benchmark

Private Boolean [] isVisited; @param index @return */ public int getFirstNeighbor(int index){for (int j = 0; j < vertexList.size(); j++) { if(edges[index][j]>0){ return j; } } return -1; } /** ** Obtains the next adjacent node based on the subscript of the previous adjacent node * @param v1 Current traversal node number * @param v2 v1 node number that has been accessed * @return */ 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; } /** * private void DFS (Boolean [] isVisited,int I){/** * 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); } // if the w node is already accessed 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); }}}Copy the code

test

Public static void main(String[] args) {public static void main(String[] args) {public static void main(String[] args) { / / the number of nodes in the String Vertexs2 [] = {" v1 ", "v2", "v3", "v4", "the v5," "v6", "v7", "v8"}; // Create the Graph object Graph graph2 = new Graph(n); For (String vertex: Vertexs2) {graph2.insertVertex(vertex); } graph2.insertEdge(0, 1, 1); graph2.insertEdge(1, 3, 1); graph2.insertEdge(1, 4, 1); graph2.insertEdge(3, 7, 1); graph2.insertEdge(4, 7, 1); graph2.insertEdge(0, 2, 1); graph2.insertEdge(2, 5, 1); graph2.insertEdge(2, 6, 1); graph2.dfs(); }Copy the code

2. Breadth-first search

Breadth-first search is also known as broad search or BFS. Similar to a hierarchical search (a hierarchical traversal of a tree), breadth-first search requires the use of a queue to maintain the order of nodes visited so that their neighbors can be accessed in that order.

Access idea:

  • From the initial access node, enqueue it and mark it as visited
  • Take the header element, find its unvisited adjacent nodes, mark them as visited, and join the queue in turn
  • If the queue is not empty, continue to fetch the queue head element and find its unvisited adjacent nodes marked as visited and queued
  • Until the queue is empty

For example, the traversal process is as follows:

  • V1 joins the queue and is marked as visited and out of the queue. V1’s adjacent nodes V2 and V3 join the queue and are marked as visited
  • V2 out of the queue, V4, V5 in the queue and marked; V3 out, V6, V7 in and marked
  • V4 out, V8 in and marked; V5 out, V6 out, V7 out, V8 out.

The final traversal result is:

V1 -> V2 -> v3 -> V4 -> V5 -> V6 -> V7 -> V8
Copy the code

The specific implementation

Again, this is based on the two-dimensional array representation in the figure above

/** * private void BFS (Boolean [] isVisited,int I){private void BFS (Boolean [] isVisited,int I){ // next node w int w; <Object> queue = new LinkedList<>(); System.out.print(getValueByIndex(i)+"->"); isVisited[i] = true; queue.addLast(i); while (! Queue. IsEmpty ()){queue = (Integer) queue.removeFirst(); W = getFirstNeighbor(u); 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); }}}Copy the code

Testing:

Public static void main(String[] args) {public static void main(String[] args) {public static void main(String[] args) { / / the number of nodes in the String Vertexs2 [] = {" v1 ", "v2", "v3", "v4", "the v5," "v6", "v7", "v8"}; // Create the Graph object Graph graph2 = new Graph(n); For (String vertex: Vertexs2) {graph2.insertVertex(vertex); } graph2.insertEdge(0, 1, 1); graph2.insertEdge(1, 3, 1); graph2.insertEdge(1, 4, 1); graph2.insertEdge(3, 7, 1); graph2.insertEdge(4, 7, 1); graph2.insertEdge(0, 2, 1); graph2.insertEdge(2, 5, 1); graph2.insertEdge(2, 6, 1); graph2.bfs(); }Copy the code

\