1, the preface

I’ve always wondered why the JDK doesn’t implement graphs, but every time we need to use graphs, we have to rewrite the collar matrix, the collar table, etc., and then write the algorithm implementation, which is very troublesome.

So it’s easy to encapsulate graphs as data structures (for study only). See Github for the code

2. How are graphs stored

There are two kinds of realization of graph storage, namely lead matrix and lead table.

2.1. Collar matrix

In fact, we use one2 d arrayTo store the relationship between nodes in the diagram. Row and column subscripts represent a node number, and the value of an array represents an edge. For example, here’s a two-dimensional arrayint[][] graph,graph[3][5]saidNode 3andNode 5There’s an edge between them. In this way we can easily store all the edges and nodes in the graph.

2.2. Collar table

It’s essentially a linked list array or a hash table. For example, if the LinkedList

[] graph is stored, graph[0] represents all nodes adjacent to node 0. For example, if we use hash table Map

> graph, then graph.get(0) represents all nodes adjacent to node 0.
,>

3. Gallery system

It mainly realizes four kinds of graph structure, respectively

  • Collar matrix - unauthorized graph: AdjacencyMatrixGraph
  • Collar matrix - entitlement diagram: AdjacencyMatrixWeightGraph
  • Access form - Entitlement chart: AdjacencyListsGraph
  • Access list - Entitlement chart: AdjacencyListsWeightGraph

The class diagram relationship is as follows

4, functionality,

And the following basic graph theory algorithms are implemented on these four data structures:

  • Depth-first traversal of the graph
  • Breadth-first traversal of the graph
  • Calculate the number of connected components of the graph
  • Minimum spanning tree algorithm
    • Prim algorithm
    • Kruskal algorithm
  • Path algorithm
    • Power graph single source shortest path algorithm Dijkstra
    • Unauthorised graph single source shortest path algorithm
    • Find a path from the start node to the end node
    • Find all paths from the start node to the end node

5. Start fast

5.1. Create a diagram


    Has the following figure * 0 * / / * * \ * 3 * 2 / / \ | * v 5 - > 1 ^ * 4 * 6 v / * * 8 -- > 9 * 12 * /
    // create a tie table
    static Graph<String> noWeightDirectListedGraph = new AdjacencyListsGraph<>(true);
    // Create an undirected and unauthorized adjacency matrix
    static Graph<String> noWeightMatrixGraph = new AdjacencyMatrixGraph<>(50.false);

    static {
        noWeightDirectListedGraph.addEdge("x0"."x2");
        noWeightDirectListedGraph.addEdge("x2"."x6");
        noWeightDirectListedGraph.addEdge("x0"."x3");
        noWeightDirectListedGraph.addEdge("x3"."x4");
        noWeightDirectListedGraph.addEdge("x3"."x5");
        noWeightDirectListedGraph.addEdge("x4"."x5");
        noWeightDirectListedGraph.addEdge("x5"."x1");
        noWeightDirectListedGraph.addEdge("x8"."x9");
        noWeightDirectListedGraph.addEdge("x12"."x12");

        noWeightMatrixGraph.addEdge("x0"."x2");
        noWeightMatrixGraph.addEdge("x2"."x6");
        noWeightMatrixGraph.addEdge("x0"."x3");
        noWeightMatrixGraph.addEdge("x3"."x4");
        noWeightMatrixGraph.addEdge("x3"."x5");
        noWeightMatrixGraph.addEdge("x4"."x5");
        noWeightMatrixGraph.addEdge("x8"."x9");
        noWeightMatrixGraph.addEdge("x12"."x12");

    }
    
	// create an undirected access matrix
    static WeightedGraph<String, Integer> weightListedGraph = new AdjacencyMatrixWeightGraph<>(20.false);
    /* 0 - 2 \ 3 - 4 - 6 a2-a0(10) \ / \ a3-a5(10) 1- 5 7 a3-a4(20) a0-a3(30) a1-a5(40) a6-a4(98) a7-a4(100) */
    static {
        weightListedGraph.addEdge("a0"."a2".10);
        weightListedGraph.addEdge("a0"."a3".10);
        weightListedGraph.addEdge("a3"."a4".20);
        weightListedGraph.addEdge("a3"."a5".10);
        weightListedGraph.addEdge("a5"."a1".40);
        weightListedGraph.addEdge("a4"."a5".50);
        weightListedGraph.addEdge("a4"."a5".60);
        weightListedGraph.addEdge("a4"."a5".36);
        weightListedGraph.addEdge("a6"."a4".98);
        weightListedGraph.addEdge("a4"."a7".100);
    }
Copy the code

5.2 Depth and breadth traversal of the graph

    @Test
    public void testTraverse(a){
        // depth traversal DFS
        noWeightDirectListedGraph.dfsTraverse(e -> System.out.print(e + "- >"));
        System.out.println("\n-------");
        // breadth traversal BFS
        noWeightMatrixGraph.bfsTraverse(e -> System.out.print(e + "- >"));
    }
Copy the code

5.3. Calculate the unicom component

    int count = noWeightDirectListedGraph.componentCount();
    int count1 = noWeightMatrixGraph.componentCount();
    System.out.println(count);
    System.out.println(count1);
Copy the code

5.4. Minimum Spanning Tree Algorithm

    @Test
    public void testGetMinimumSpanningTree(a){
        MstTree<String, Integer> minimumSpanningTree = weightListedGraph.getMinimumSpanningTree();
        / / Prim algorithm
        MstTree<String, Integer> minimumSpanningTreePrim = weightListedGraph.getMinimumSpanningTreePrim();
        / / Kruskal algorithm
        MstTree<String, Integer> minimumSpanningTreeKruskal = weightListedGraph.getMinimumSpanningTreeKruskal();
        List<Edge<String,Integer>> edgeList = minimumSpanningTree.getEdgeList();
        for(Edge<String,Integer> e : edgeList){ System.out.println(e.toString()); }}Copy the code

5.5. Unauthorised graph algorithm for single source Shortest path

        // Find all shortest paths from the start node to other nodes
        String startNoe = "x0";
        Map<String, List<String>> tmp = noWeightDirectListedGraph.findShortPathFromStartNode(startNoe);
        for (Map.Entry<String, List<String>> entry : tmp.entrySet()) {
            String path = entry.getValue().stream().collect(Collectors.joining("- >"));
            System.out.println("From" + startNoe + "To the node" + entry.getKey() + The shortest path to "is:" + path);
        }
Copy the code

5.6. Path algorithm

  System.out.println("=================2. Find a path from the start node to the end node ====");
        // Find a path from x0 to x1.
        List<String> onePath = noWeightDirectListedGraph.findOnePath("x0"."x1");
        System.out.println("Find a path from x0 to x1 as:" + onePath.stream().collect(Collectors.joining("- >")));


        System.out.println("=================3. Find all paths from start node to end node ====");

        List<List<String>> allPath = noWeightDirectListedGraph.findAllPath("x0"."x1");
        for (List<String> list : allPath) {
            System.out.println("The path from x0 to x1 is:" + list.stream().collect(Collectors.joining("- >")));
        }
Copy the code

5.7. Power graph single source shortest path algorithm Dijkstra

    @Test
    public void testShortPathTree(a){
        ShortPathTree<String, Integer> tmp = weightListedGraph.getShortPathTree("a0", Integer.class);
        for (Map.Entry<String, List<Edge<String, Integer>>> entry : tmp.getFormSourceToEndPathEdgeMap().entrySet()) {
            String path = entry.getValue().stream().map(Edge::toString).collect(Collectors.joining("- >"));
            System.out.println("A0 to node" + entry.getKey() + The shortest path to "is:" + path);
        }

        System.out.println();
    }
Copy the code