Graph representation can be generally used adjacency list, adjacency matrix… This is a much more powerful way to deal with basically any algorithm that has to do with graphs, for example

Topological sorting, deep search, wide search, Kruskal, Prim, Dijkstra.

When creating a graph, you pass a two-dimensional array, matrix[I][0] is the weight, matrix[I][1] is the starting point value, matrix[I][2] is the stopping point value, and finally return a graph.

Public class GraphGenerator {// Create Graph public static Graph creatGraph(Integer[][]matrix){Graph Graph = new Graph(); for(int i = 0; i < matrix.length; i++){ Integer weight = matrix[i][0]; Integer from = matrix[i][1]; Integer to = matrix[i][2]; // Create an if(! graph.nodes.containsKey(from)){ graph.nodes.put(from, new Node(from)); } // Create an if(! graph.nodes.containsKey(to)){ graph.nodes.put(to, new Node(to)); } // Get the start Node, end the Node fromNode = graph.nodes.get(from); Node toNode = graph.nodes.get(to); Edge newEdge = newEdge (weight, fromNode, toNode); Add (toNode) fromNode.nexts.add(toNode); //graph.nodes.get(from).nextx.add(toNode); // change the degree of fromNode and toNode fromnode. out++; toNode.in++; // Add the edges to the edge set (Graph,Node) graph.edges. Add (newEdge); fromNode.edges.add(newEdge); } return graph; }}Copy the code

import java.util.HashMap; import java.util.HashSet; import java.util.Set; Public class Graph {// Set of points, set of edges public HashMap<Integer, Node>nodes; Public Set<Edge>edges; public Graph(){ nodes = new HashMap<Integer, Node>(); edges = new HashSet<Edge>(); }}Copy the code

Public class Edge {// This is not an adjacency matrix or adjacency list method. Public Node from; Public Node to; Public Edge(int weight,Node from,Node to){this.weight = weight; this.from = from; this.to = to; }}Copy the code

import java.util.ArrayList; public class Node { public int value; Public int in; Public int out; Public ArrayList<Node>nexts; // Public ArrayList<Edge>edges; Public Node(int value){this.value = value; in = 0; out = 0; nexts = new ArrayList<Node>(); edges = new ArrayList<Edge>(); }}Copy the code

​