Vomitting blood collates programmer to read list: github.com/silently952…

Wechat official account: Beta learning Java

preface

From the beginning of this article we will learn the graph related algorithm, graph calculation has a lot of quite practical algorithms, such as: garbage collector mark removal algorithm, the shortest path on the map, topology sorting, etc.. Before we start learning about these algorithms we need to understand the basic definition of the graph below and which data structure to use to represent a graph. In this article we will start with undirected graphs.

The definition of the figure

Figure: consists of a set of vertices and a set of vertices that connect two orders. An edge connecting two vertices with no direction is called an undirected graph.

Figure of the term

Two vertices that are connected by the same edge are said to be adjacent;

The degree of a vertex is the total number of edges connected to the vertex; As shown in the figure above: Vertex 1 has degree 3

An edge that connects a vertex to itself is called a self ring

Edges that connect the same pair of vertices are called parallel edges

There are many other terms. For the time being, only the terms we need to use in this paper are listed here, and other terms will be explained later. Too many terms are not easy to remember

How do I represent the graph

What data structure should be used to represent the graph mainly refers to two requirements:

  1. In the development of graph correlation algorithm, the graph data structure is the basis, so this data structure is high efficiency
  2. In the actual process, the size of the graph is uncertain and may be large, so you need to leave enough space

After considering these two requirements, the leaders suggested the following three options:

  • Adjacency matrix

If vertex V is connected to w, set row V and column W to true. This means that two vertices are connected. However, there is a problem with this method. The second point is not satisfied. And secondly, you can’t represent parallel edges in this way

  • The edge of the array

We can define a representation edge object with two ints representing vertices, but if we need to find what vertices are connected to a vertex, we need to iterate over all the edges. This data structure is inefficient

  • Adjacency list array

Define an array where the size of the array is the number of vertices and the subscript is the vertex. Each element in the array is a LinkedListQueue. The value in the list is the vertex that is connected to the vertex. (LinkedListQueue, which we implemented in previous articles, can be found at juejin.cn/post/692668…

API definition of undirected graphs

public class Graph { public Graph(int V); // create graph with v vertices without edges public int v (); Public int E(); Public void addEdge(int v, int w); V -w public Iterable<Integer> adj(int v); Public String toString(); // Use string to print graph relation}Copy the code

Implementation of undirected graph API

To implement the API defined above, we need three member variables: v represents the number of vertices in the graph, e represents the total edge of the graph, and the array LinkedListQueue is used to store the nodes adjacent to vertex V.

The constructor initializes the empty adjacency list array

Because it is an undirected graph, addEdge method needs to add both a V -> W edge and a W -> V edge to the graph

public class Graph { private final int v; private int e; private LinkedListQueue<Integer>[] adj; public Graph(int v) { this.v = v; this.adj = (LinkedListQueue<Integer>[]) new LinkedListQueue[v]; for (int i = 0; i < v; i++) { this.adj[i] = new LinkedListQueue<>(); } } public int V() { return v; } public int E() { return e; } public void addEdge(int v, int w) { this.adj[v].enqueue(w); this.adj[w].enqueue(v); this.e++; } public Iterable<Integer> adj(int v) { return this.adj[v]; } @Override public String toString() { StringBuilder sb = new StringBuilder(); Sb. Append (v), append (vertices, ""). Append (e), append (" side \ n"); for (int i = 0; i < v; i++) { sb.append(i).append(": "); for (int j : this.adj[i]) { sb.append(j).append(" "); } sb.append("\n"); } return sb.toString(); }}Copy the code

Common tool methods for graphs

Based on the implementation of graph data structures, we can provide some tool methods

  1. Calculate the degree of vertex V

The degree of a vertex is equal to the number of vertices connected to it

public static int degree(Graph graph, int v) {
    int degree = 0;
    for (int w : graph.adj(v)) {
        degree++;
    }
    return degree;
}
Copy the code
  1. Calculates the maximum degree of all vertices
public static int maxDegree(Graph graph) {
    int maxDegree = 0;
    for (int v = 0; v < graph.V(); v++) {
        int degree = degree(graph, v);
        if (maxDegree < degree) {
            maxDegree = degree;
        }
    }
    return maxDegree;
}
Copy the code
  1. Calculate the average degree of all vertices

Each edge has two vertices, so the total degree of all the vertices on the graph is twice that of the edges

Public static double avgDegree(Graph Graph) {return 2.0 * graph.e ()/graph.v (); }Copy the code
  1. Calculate the number of self-loops in the graph

For vertex V, if V also appears in the adjacency list of V, then v has a self-loop; Since it’s an undirected graph, every edge is recorded twice (print out the toString of the graph if you don’t understand it)

public static int numberOfSelfLoops(Graph graph) {
    int count = 0;
    for (int v = 0; v < graph.V(); v++) {
        for (int w : graph.adj(v)) {
            if (v == w) {
                count++;
            }
        }
    }
    return count / 2;
}
Copy the code

conclusion

In this article we mainly learn what kind of data structure to represent a graph, and based on this data structure to achieve a few simple tool methods, in the next chapter we will learn the first graph search algorithm – depth-first search

All the source code has been put into github repository: github.com/silently952…

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏