The concept of the diagram
The graph is the expansion of the tree in the algorithm. The tree is a data structure from top to bottom. The nodes have a parent node (except the root node), arranged from top to bottom. The graph has no concept of father-son nodes, and the nodes in the graph are all equal relationships, which makes the result even more complicated.
Undirected graph Directed graph
Figure G=(V,E), where V represents the vertex, E represents the edge edge, and an edge is a fixed-point pair (u,v), where (u,v)∈V.
In the past two days, I encountered an algorithm about graphs. I searched online for a long time and couldn't find the Java version of the graphs in the data structure and their related operations. So I found a Java version of the data structure book and read it. The following is a summary of undirected graph storage and depth priority traversal of graphs compiled based on the explanation in the book. However, this traversal can only traverse the connected graph, and to traverse the non-connected graph, it still needs to be modified. I hope it will be helpful to those in need.
package com.homework;/** * Define the stack class*/class StackX{private final int size = 20;private int[] st;private int top;//Initialize the stack public StackX(){st = new int[size];top = -1;}//Initialize the stack public void push(int j){st[++top] = j;}//Open public int pop(){return st[top--];}//Return the top element of the stack public int peak(){return st[top];}//Determine whether the stack is empty public Boolean isEmpty(){return (top==-1);}}/** * Define the node class in the graph* @author Administrator * */class Vertex{public char label;public Boolean wasVisited;public Vertex(char lab){label = lab; wasVisited = false;}}/** * Define the graph class* @author Administrator * */class Graph{private final int num = 20;private Vertex vertexList[];//Node array private int adjMat[][];//Node matrix private int nVerts;//The current number of nodes private StackX theStack;//Define a stack//The structure of the initialization graph public Graph(){vertexList = new Vertex[num];adjMat = new int[num][num];nVerts = 0;for (int i=0; i<num; i++){for (int j=0; j<num; j++) adjMat[i][j] = 0;}}//Add node public void addVertex(char lab){vertexList[nVerts++] = new Vertex(lab);}//Add an edge between two nodes public void addEdge(int start,int end){adjMat[start][end] = 1;adjMat[end][start] = 1;}//Output a certain node public void displayVertex(int v){System.out.print(vertexList[v].label);}//Get some unreached points public int getAdjUnvisitedVertex(int v){for (int j=0; j<nVerts; j++){if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) return j;}return -1;}//Deep priority traversal (DFS) public void dfs(){vertexList[0].wasVisited=true;displayVertex(0);theStack= new StackX();theStack.push(0); while(!theStack.isEmpty()){int v = getAdjUnvisitedVertex(theStack.peak());if(v==-1)//If the node does not exist theStack.pop(); else {vertexList[v].wasVisited = true;displayVertex(v); theStack.push(v);}}for (int j=0; j<nVerts; j++) vertexList[j].wasVisited = false;}}public class GraphConnect {public static void main(String[] args){{Graph theGraph = new Graph(); theGraph.addVertex('A'); theGraph.addVertex('B'); theGraph.addVertex('C'); theGraph.addVertex('D'); theGraph.addVertex('E'); theGraph.addEdge(0, 1);//AB theGraph.addEdge(1, 2);//BC theGraph.addEdge(0, 3);//AD theGraph.addEdge(3, 4);//DE theGraph.addEdge(2, 4);//CE System.out.print("The order visited:");theGraph.dfs();System.out.println();}}} Results of program running:
The order visited:ABCED
Summarize
The above is all the detailed explanation of the storage and DFS operation code of Java programming undirected graph structure. I hope it will be helpful to everyone. Interested friends can continue to refer to this site:
Java programming implements graph-based depth-first search and breadth-first search complete code
Depth-first and breadth-first Java implementation code example
Java programming conversion code for two tree menu structures
If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!