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

This article mainly introduces the example analysis of the unauthorized undirected graph in Java, which has a certain reference value, and interested friends can refer to it. I hope you will gain a lot after reading this article.

1. Definition of graph

We know that all the data structures discussed above have a framework, and this framework is implemented by corresponding algorithms, such as a binary tree search tree, where the value of all nodes on the left subtree is less than the value of its root node. The value of all nodes in the right subtree is greater than the value of its root node, similar to this shape makes it easy to search for data and insert data, and the edges of the tree represent shortcuts from one node to another.

A graph usually has a fixed shape, which is determined by physical or abstract problems. For example, the node in the figure represents the city, while the edge may represent the flight routes between cities. The picture below shows the simplified highway network in California, USA:

①, adjacency:

If two vertices are connected by the same edge, the two vertices are said to be adjacent. For example, I and G are adjacent, but I and F are not. Sometimes the vertex adjacent to a specified vertex is called its neighbor, for example, the neighbors of vertex G are I, H, F.

②, path:

A path is a sequence of edges, for example, the path from vertex B to vertex J is BAEJ, and of course there are other paths BCDJ,BACDJ and so on.

③, connected and unconnected graphs:

If there is at least one path that connects all vertices, the graph is called connected; if there is a graph that cannot reach another vertex from one vertex, it is called unconnected.

④, directed graph and undirected graph:

If the edge in the graph has no direction and can reach the other side from either side, it is called an undirected graph; for example, a two-way highway, from city A to city B, can drive from city A to city B, or from city B to city A. But if you can only drive from city A to city B, it is called a directed graph.

⑤, weighted graphs and unauthorized graphs:

The edges in a graph are given a weight, and the weight is a number, which can represent the physical distance between two vertices, or the time from one vertex to another. This kind of graph is called a weighted graph; on the contrary, an edge with no assignment is called an unauthorized graph.

In this blog, we are talking about undirected graphs without power.

2. Show the graph in the program

We know that a graph is made up of vertices and edges, so how to simulate vertices and edges in a computer?

①, Vertex:

In most cases, vertices represent a real-world object that must be described by data items. For example, in an aircraft route simulation program, the vertex represents the city, then it needs to store the city's name, altitude, geographical location and other related information, so a vertex is usually represented by a vertex class object. here we store only one letter in the vertex to identify the vertex, as well as a flag bit to determine whether the vertex has been accessed (for later search).

/ * vertex class * @ author vae * / public class Vertex {public char label; public boolean wasVisited; public Vertex (char label) {this.label = label; wasVisited = false;}}

Vertex objects can be placed in an array and then indicated by subscripts, or in linked lists or other data structures, no matter what structure is used, they are stored just for convenience, regardless of how the edges connect the points.

②, Edge:

In the previous description of the data structure of various trees, most trees are references to each node containing its child nodes, such as red-black tree and binary tree. The tree is also represented by an array, and the position of the node in the tree group determines its relationship with other nodes, for example, the heap is represented by an array.

However, unlike a tree, a graph has no fixed structure, and each vertex of a graph can be connected to any number of vertices. In order to simulate this free-form organizational structure, the graph is represented in the following two ways: the adjacency matrix and the adjacency table (if an edge connects two vertices, then the two vertices are adjacent)

Adjacency matrix:

The adjacency matrix is a two-dimensional array, and the data item indicates whether there is an edge between the two points. If there are N vertices in the graph, the adjacency matrix is an array of Numern. The above figure is represented by an adjacency matrix as follows:

1 means there are edges, 0 means no edges, and it can also be represented by Boolean variables true and false. Vertices connected to themselves are represented by zeros, so the diagonals of the matrix from the upper left corner to the upper right corner are all zeros.

Note: the upper triangle of this matrix is a mirror image of the lower triangle, and the two triangles contain the same information. This redundant information seems inefficient, but in most computers, it is difficult to create an array of triangles, so we have to accept this redundancy. This also requires that in the program processing, when we add an edge, such as updating two parts of the adjacency matrix, rather than a part.

Adjacency table:

An adjacency list is an array of linked lists (or linked lists), and each separate linked list indicates which vertices are adjacent to the current vertex.

3. Search

One of the most basic operations in the diagram is to search which vertices can be reached from a specified vertex, such as which cities can be reached by high-speed rail from Wuhan, some cities can go directly, and some cities cannot. Now there is a national high-speed rail simulation map that starts from one city (vertex) and moves along the rail (edge) to another city (vertex). There are two ways to search the map: depth-first search (DFS) and breadth-first search (BFS). They will eventually reach all connected vertices. Depth-first search is achieved through the stack, while breadth-first search is achieved through queues. Different implementation mechanisms lead to different search methods.

①, depth first search (DFS)

The depth first search algorithm has the following rules:

Rule 1: if possible, access an adjacent unaccessed vertex, mark it, and put it on the stack.

Rule 2: when rule 1 cannot be executed, if the stack is not empty, a vertex pops up from the stack.

Rule 3: if rules 1 and 2 cannot be executed, the entire search process is completed.

For the image above, apply the depth-first search as follows: suppose vertex An is selected as the starting point and accessed in alphabetical order, then apply rule 1, then access vertex B, then mark it, and put it on the stack; apply rule 1 again, then access vertex F, apply rule 1 again, and access vertex H. At this time, we find that there is no adjacent point of vertex H, and then apply rule 2, pop H from the stack, and return to vertex F, but we find that F also has no adjacent and unvisited vertices besides H, so pop F again, then return to vertex B, the same rule 1 can't be applied, rule 2, pop up B, there is only vertex An in the stack. Then A has unaccessed adjacency points, so then visit vertex C, but C is the end of the line, so pop it out of the stack, go back to An again, then visit DGrai I, and finally go back to A, and then visit E, but finally go back to vertex A, and then we find that A has no unaccessed adjacency points, so we pop it off the stack. Now that there are no vertices in the stack, rule 3 is applied to complete the search process.

Depth-first search is to find vertices that are adjacent to a vertex and have not been visited. Here, take the adjacency matrix as an example, find the row where the vertex is located, and look backward from the first column for a column with a value of 1. The column number is the number of the adjacent vertex, check whether the vertex has not been accessed, and if so, this is the next vertex to visit, if the row has no vertex equal to 1 (adjacency) and is not accessed, then all the vertices adjacent to the specified point have been visited (which will be implemented later by the algorithm).

②, breadth first search (BFS)

The depth-first search should be as far away from the starting point as possible, while the breadth-first search should be as close to the starting point as possible. it first accesses all the adjacent points of the starting vertex, and then visits the farther area. this kind of search can not be realized by stack, but by queue.

Rule 1: access the next unaccessed adjacency point (if any), this vertex must be the adjacency point of the current vertex, mark it, and insert it into the queue.

Rule 2: if there are no unaccessed adjacencies and rule 1 cannot be executed, take a vertex from the queue header (if any) and make it the current vertex.

Rule 3: if rule 2 cannot be executed because the queue is empty, the search ends.

For the above figure, apply breadth-first search: with An as the starting point, first visit all the vertices adjacent to A, and insert them into the queue at the same time. Now you have visited A, B, C, D and E. The queue (from beginning to end) contains BCDE, and there are no unaccessed vertices adjacent to vertex A, so take B out of the queue, find the vertex adjacent to B, and find F, so insert F into the queue. There are no unaccessed vertices adjacent to B, so take C from the queue header, which has no unaccessed adjacencies. Therefore, there are no unvisited adjacency points for taking out D and visiting GMague D, so take out E, now there is FG in the queue, take out F, visit H, then take out G, visit I. now there is HI in the queue. When you take them out, you find that there are no other visiting vertices, then the queue is empty and the search ends.

③, program realization

Stack StackX.class for depth-first search

Package com.ys.graph;public class StackX {private final int SIZE = 20; private int [] st; private int top; public StackX () {st = new int [SIZE]; top =-1;} public void push (int j) {st[ + + top] = j;} public int pop () {return st [top--];} public int peek () {return st [top] } public boolean isEmpty () {return (top = =-1);}}

Queue Queue.class for breadth-first search

Package com.ys.graph;public class Queue {private final int SIZE = 20; private int [] queArray; private int front; private int rear; public Queue () {queArray = new int [SIZE]; front = 0; rear =-1;} public void insert (int j) {if (rear = = SIZE-1) {rear =-1;} queArray [+ + rear] = j } public int remove () {int temp = queArray [front++]; if (front = = SIZE) {front = 0;} return temp;} public boolean isEmpty () {return (rear+1 = = front | | front+SIZE-1 = = rear);}}

Figure code Graph.class

Package com.ys.graph;public class Graph {private final int MAX_VERTS = 20 private final int MAX_VERTS / indicates the number of vertices private Vertex vertexList []; / the array private int adjMat used to store vertices [] []; / / the edges are stored with adjacency matrix, with array element 0 indicating no boundary, 1 indicating the number of bounded private int nVerts;// vertices private StackX theStack;// uses stack to realize depth-first search private Queue queue / / use queue to achieve breadth-first search / * vertex class * @ author vae * / class Vertex {public char label; public boolean wasVisited; public Vertex (char label) {this.label = label; wasVisited = false;}} public Graph () {vertexList = new Vertex [Max _ VERTS] AdjMat = new int [Max _ VERTS] [MAX_VERTS]; nVerts = 0 / the number of initialization vertices is 0 / / all elements of the initial adjacency matrix are 0, that is, all vertices have no edge for (int I = 0; I < MAX_VERTS; iTunes +) {for (int j = 0; j < MAX_VERTS; jacks +) {adjMat [I] [j] = 0 }} theStack = new StackX (); queue = new Queue ();} / / add vertices to the array, whether the access flag is set to wasVisited=false (not accessed) public void addVertex (char lab) {vertexList [nVerts++] = new Vertex (lab) } / / Note that the edge is represented by an adjacency matrix, which is symmetrical. Both parts should be assigned public void addEdge (int start, int end) {adjMat [start] [end] = 1; adjMat [end] [start] = 1;} / print the value public void displayVertex (int v) {System.out.print (vertexList [v] .label) represented by a vertex. } / * * depth-first search algorithm: * 1. Use the peek () method to check the vertices at the top of the stack * 2, use the getAdjUnvisitedVertex () method to find the vertices adjacent to the current stack vertices that are not accessed * 3, and find the next unaccessed adjacent vertex if the return value of the second step method is not equal to-1, visit the vertex, and enter the stack * if the return value of the second step method is equal to-1 Is not found, unstack * / public void depthFirstSearch () {/ / access vertexList [0] .wasVisited = true from the first vertex / / Mark as true displayVertex (0) after access; / / print the first vertex accessed theStack.push (0); / / put the first vertex on the stack while (! theStack.isEmpty ()) {/ / find the vertex int v = getAdjUnvisitedVertex (theStack.peek ()) that is adjacent to the current vertex of the stack and is not accessed. If (v =-1) {/ / if the current vertex value is-1, it means that there is no adjacency and no vertex is accessed, then the vertex of the stack is theStack.pop ();} else {/ / otherwise access the next adjacent vertex vertexList [v] .wasVisited = true; displayVertex (v) TheStack.push (v);}} / / after stack access, reset all tag bits wasVisited=false for (int I = 0; I < nVerts; iTunes +) {vertexList [I] .wasVisited = false;}} / / find vertex public int getAdjUnvisitedVertex (int v) {for (int I = 0) that is adjacent to a vertex and is not accessed I < nVerts; iTunes +) {/ v vertex is adjacent to vertex I (adjacency matrix value is 1) and wasVisited==false if is not accessed (adjma [v] [I] = = 1 & & vertexList [I] .wasVisited = = false) {return I;}} return-1 } / * breadth-first search algorithm: * 1. Check the vertex at the top of the stack with the remove () method * 2, try to find the adjacent node that the vertex has not been accessed * 3, if not found, the vertex is dequeued * 4, if such a vertex is found, visit the vertex And put it in the queue * / public void breadthFirstSearch () {vertexList [0] .wasVisited = true DisplayVertex (0); queue.insert (0); int v2; while (! queue.isEmpty ()) {int v1 = queue.remove (); while ((v2 = getAdjUnvisitedVertex (v1)! =-1) {vertexList [v2] .wasVisited = true; displayVertex (v2); queue.insert (v2) }} / / search completed and initialized to facilitate the next search for for (int I = 0; I < nVerts; iTunes +) {vertexList [I] .wasVisited = false;}} public static void main (String [] args) {Graph graph = new Graph (); graph.addVertex ('A'); graph.addVertex ('B') Graph.addVertex ('C'); graph.addVertex ('D'); graph.addVertex ('E'); graph.addEdge (0,1); / / AB graph.addEdge (1,2); / / BC graph.addEdge (0,3); / / AD graph.addEdge (3,4); / / DE System.out.println ("depth-first search algorithm:") Graph.depthFirstSearch (); / / ABCDE System.out.println (); System.out.println ("- -"); System.out.println ("breadth first search algorithm:"); graph.breadthFirstSearch (); / / ABDCE}}

Test results:

4. Minimum spanning tree

For graph operations, one of the most common is to find the minimum spanning tree, which connects all vertices with the least number of edges. For a given set of vertices, there may be many minimum spanning trees, but the number of edges E of the minimum spanning tree is always 1 less than the number of vertices V, that is:

V = E + 1

There is no need to care about the length of edges, not to find the shortest path (which will be explained in the weighted graph), but to find the least number of edges, which can be achieved based on depth-first search and breadth-first search.

For example, based on depth-first search, we record the edges we have passed, and we can create a minimum spanning tree. Because DFS visits all vertices, but only once, it will never visit the same vertex twice, but when she sees that an edge will reach an already visited vertex, it will not take this edge, it never traverses the impossible edges, so the path of the DFS algorithm through the whole graph must be the minimum spanning tree.

/ find the minimum spanning tree public void mst () {vertexList [0] .wasVisited = true; theStack.push (0) based on depth-first search; while (! theStack.isEmpty ()) {int currentVertex = theStack.peek (); int v = getAdjUnvisitedVertex (currentVertex); if (v = =-1) {theStack.pop ();} else {vertexList [v] .wasVisited = true TheStack.push (v); displayVertex (currentVertex); displayVertex (v); System.out.print ("");}} / / search completed and initialized to facilitate the next search for for (int I = 0; I < nVerts; iTunes +) {vertexList [I] .wasVisited = false }} Thank you for reading this article carefully. I hope the article "sample Analysis of undirected graphs without Power in Java" shared by the editor will be helpful to you. At the same time, I also hope that you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.