How graphs are stored

• Adjacent table
• Adjacent matrix

express

• Point set/edge set
• Directed graph/undirected graph

A set of points and a set of edges

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

Node (collection of points)

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

Edge (Edge set)

public class Edge { public int weight; 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

Interface functions (to convert an unknown topic type to a familiar type, as shown in the figure above)

Public class GraphGenerator {// matrix all edges // N*3 matrix // [weight, from the value of the node, to the value of the node] The second represents to, the third represents weight // [6,1,2] // [4,2, 0】 public static Graph createGraph(Integer[][] matrix) {Graph Graph = new Graph(); for (int i = 0; i < matrix.length; I ++) {// from: matrix[0][0], to: matrix[0][1] weight: matrix[0][2] Integer from = matrix[I][0]; Integer to = matrix[i][1]; Integer weight = matrix[i][2]; if (! Graph.nodes. ContainsKey (from)) {graph.nodes. Put (from, new Node(from)); } if (! Graph.nodes.containskey (to)) {// Put the missing to into the point set graph.nodes.put(to, new Node(to)); } Node fromNode = graph.nodes.get(from); Nodetonode = graph.nodes. Get (to); NewEdge = newEdge (weight, fromNode, toNode); // Create edge fromNode.nexts.add(toNode); / / the from neighbor fromNode. Out++; // Outdegree ++ tonode.in ++; Edges ++ fromnode.edges. Add (newEdge); // Edges ++ fromnode.edges. // Place edges into the set of edges I have graph.edges. Add (newEdge); } return graph; }}Copy the code

Graph traversal

Width first traversal

code

import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; Public class Code01_BFS {public static void BFS (node node) {if (node == null) {return; } Queue<Node> queue = new LinkedList<>(); HashSet<Node> set = new HashSet<>(); Queue. Add (node); set.add(node); while (! queue.isEmpty()) { Node cur = queue.poll(); System.out.println(cur.value); for (Node next : cur.nexts) { if (! set.contains(next)) { set.add(next); queue.add(next); } } } } }Copy the code

Depth first traversal

code

import java.util.HashSet; import java.util.Stack; public class Code02_DFS { public static void dfs(Node node) { if (node == null) { return; } Stack<Node> stack = new Stack<>(); // Guaranteed depth path HashSet<Node> set = new HashSet<>(); stack.add(node); set.add(node); System.out.println(node.value); while (! stack.isEmpty()) { Node cur = stack.pop(); for (Node next : cur.nexts) { if (! set.contains(next)) { stack.push(cur); stack.push(next); set.add(next); System.out.println(next.value); break; } } } } }Copy the code

Topological sorting algorithm

• It needs to be a directed graph with zero input nodes and no loops

code

package class06; import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Code03_TopologySort { // directed graph and no loop public static List<Node> sortedTopology(Graph graph) { // value: the remaining input HashMap< node, Integer> inMap = new HashMap<>(); <Node> zeroInQueue = new LinkedList<>(); for (Node node : graph.nodes.values()) { inMap.put(node, node.in); if (node.in == 0) { zeroInQueue.add(node); }} result List<Node> result = new ArrayList<>(); while (! zeroInQueue.isEmpty()) { Node cur = zeroInQueue.poll(); result.add(cur); for (Node next : cur.nexts) { inMap.put(next, inMap.get(next) - 1); if (inMap.get(next) == 0) { zeroInQueue.add(next); } } } return result; }}Copy the code

Kruskal’s algorithm

Undirected graph

• Add the smallest edge, as long as it doesn’t form a ring, add it, otherwise don’t add it

code

package class06; import java.util.ArrayList; import java.util.Collection; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.PriorityQueue; import java.util.Set; import java.util.Stack; //undirected graph only public class Code04_Kruskal { public static class MySets{ public HashMap<Node, List<Node>> setMap; public MySets(List<Node> nodes) { for(Node cur : nodes) { List<Node> set = new ArrayList<Node>(); set.add(cur); setMap.put(cur, set); }} public Boolean isSameSet(Node from, Node to) {List<Node> fromSet = setmap.get (from); List<Node> toSet = setMap.get(to); return fromSet == toSet; Public void union(Node from, Node to) {// List<Node> fromSet = setmap.get (from); List<Node> toSet = setMap.get(to); for(Node toNode : toSet) { fromSet.add(toNode); setMap.put(toNode, fromSet); }}} public static class UnionFind {public static class UnionFind {public static class UnionFind} Value key Node above the Node private HashMap<Node, Node> fatherMap; Private HashMap<Node, Integer> sizeMap; // value Specifies the number of nodes in a collection. public UnionFind() { fatherMap = new HashMap<Node, Node>(); sizeMap = new HashMap<Node, Integer>(); } public void makeSets(Collection<Node> nodes) { fatherMap.clear(); sizeMap.clear(); for (Node node : nodes) { fatherMap.put(node, node); sizeMap.put(node, 1); } } private Node findFather(Node n) { Stack<Node> path = new Stack<>(); while(n ! = fatherMap.get(n)) { path.add(n); n = fatherMap.get(n); } while(! path.isEmpty()) { fatherMap.put(path.pop(), n); } return n; } public boolean isSameSet(Node a, Node b) { return findFather(a) == findFather(b); } public void union(Node a, Node b) { if (a == null || b == null) { return; } Node aDai = findFather(a); Node bDai = findFather(b); if (aDai ! = bDai) { int aSetSize = sizeMap.get(aDai); int bSetSize = sizeMap.get(bDai); if (aSetSize <= bSetSize) { fatherMap.put(aDai, bDai); sizeMap.put(bDai, aSetSize + bSetSize); sizeMap.remove(aDai); } else { fatherMap.put(bDai, aDai); sizeMap.put(aDai, aSetSize + bSetSize); sizeMap.remove(bDai); } } } } public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set<Edge> kruskalMST(Graph graph) { UnionFind unionFind = new UnionFind(); unionFind.makeSets(graph.nodes.values()); PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); Edge: graph. Edges) {priorityQueue. Add (Edge); // O(logM) } Set<Edge> result = new HashSet<>(); while (! Priorityqueue.isempty ()) {// Edge Edge = priorityQueue.poll(); // O(logM) if (! unionFind.isSameSet(edge.from, edge.to)) { // O(1) result.add(edge); unionFind.union(edge.from, edge.to); } } return result; }}Copy the code

Prim algorithm

Undirected graph

code

package class06; import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; // undirected graph only public class Code05_Prim { public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; }} public static Set<Edge> primMST(Graph Graph) {PriorityQueue<Edge> PriorityQueue = new PriorityQueue<>(  new EdgeComparator()); HashSet<Node> set = new HashSet<>(); Set<Edge> result = new HashSet<>(); For (Node Node: graph.nodes.values()) {// Select a point from Node if (! set.contains(node)) { set.add(node); Edges; for (Edge Edge: node.edges) {// Unlock all connected edges from one point priorityQueue.add(Edge); } while (! priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); // Pop-up unlocked edge, the smallest edge Node toNode = edge.to; // Possible new point if (! Set.contains (toNode)) {// if it does not contain, it is the new point set.add(toNode); result.add(edge); for (Edge nextEdge : toNode.edges) { priorityQueue.add(nextEdge); } } } } //break; } return result; } // make sure the graph is connected // graph[I][j] indicates the distance from point I to point j, Public static int prim(int[][] graph) {int size = graph. Length; int[] distances = new int[size]; boolean[] visit = new boolean[size]; visit[0] = true; for (int i = 0; i < size; i++) { distances[i] = graph[0][i]; } int sum = 0; for (int i = 1; i < size; i++) { int minPath = Integer.MAX_VALUE; int minIndex = -1; for (int j = 0; j < size; j++) { if (! visit[j] && distances[j] < minPath) { minPath = distances[j]; minIndex = j; } } if (minIndex == -1) { return sum; } visit[minIndex] = true; sum += minPath; for (int j = 0; j < size; j++) { if (! visit[j] && distances[j] > graph[minIndex][j]) { distances[j] = graph[minIndex][j]; } } } return sum; } public static void main(String[] args) { System.out.println("hello world!" ); }}Copy the code

Dijkstra algorithm

• I want no edges with negative weights

code

package class06; import java.util.HashMap; import java.util.HashSet; import java.util.Map.Entry; // no negative weight public class Code06_Dijkstra { public static HashMap<Node, Integer> dijkstra1(Node head) {// The minimum distance from head to all points // key: the distance from head to key // value: HashMap<Node, Integer> distanceMap = new HashMap<>(); // If there is no record of T in the table, it means that the distance from head to T is infinity. distanceMap.put(head, 0); HashSet<Node> selectedNodes = new HashSet<>(); selectedNodes = new HashSet<>(); Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); while (minNode ! = null) { int distance = distanceMap.get(minNode); for (Edge edge : minNode.edges) { Node toNode = edge.to; if (! distanceMap.containsKey(toNode)) { distanceMap.put(toNode, distance + edge.weight); } else { distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight)); } } selectedNodes.add(minNode); minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); } return distanceMap; } public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) { Node minNode = null; int minDistance = Integer.MAX_VALUE; for (Entry<Node, Integer> entry : distanceMap.entrySet()) { Node node = entry.getKey(); int distance = entry.getValue(); if (! touchedNodes.contains(node) && distance < minDistance) { minNode = node; minDistance = distance; } } return minNode; } public static class NodeRecord { public Node node; public int distance; public NodeRecord(Node node, int distance) { this.node = node; this.distance = distance; } } public static class NodeHeap { private Node[] nodes; Private HashMap< node, Integer> heapIndexMap; private HashMap< node, Integer> heapIndexMap; Private HashMap<Node, Integer> distanceMap; private HashMap<Node, Integer> distanceMap; private HashMap<Node, Integer> distanceMap; private int size; Public NodeHeap(int size) {nodes = new Node[size]; heapIndexMap = new HashMap<>(); distanceMap = new HashMap<>(); size = 0; } public boolean isEmpty() { return size == 0; } // There is a point called node, and now it finds a distance from the source node to the node that is distance // Decide whether to update it, if necessary, Public void addOrUpdateOrIgnore(Node Node, int distance) {if (inHeap(Node)) {distancemap.put (Node, Math.min(distanceMap.get(node), distance)); insertHeapify(node, heapIndexMap.get(node)); } if (! isEntered(node)) { nodes[size] = node; heapIndexMap.put(node, size); distanceMap.put(node, distance); insertHeapify(node, size++); } } public NodeRecord pop() { NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0])); swap(0, size - 1); heapIndexMap.put(nodes[size - 1], -1); distanceMap.remove(nodes[size - 1]); // free C++ nodes[siz-1] = null; // free C++ nodes[siz-1] = null; heapify(0, --size); return nodeRecord; } private void insertHeapify(Node node, int index) { while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) { swap(index, (index - 1) / 2); index = (index - 1) / 2; } } private void heapify(int index, int size) { int left = index * 2 + 1; while (left < size) { int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ? left + 1 : left; smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index; if (smallest == index) { break; } swap(smallest, index); index = smallest; left = index * 2 + 1; } } private boolean isEntered(Node node) { return heapIndexMap.containsKey(node); } private boolean inHeap(Node node) { return isEntered(node) && heapIndexMap.get(node) ! = 1; } private void swap(int index1, int index2) { heapIndexMap.put(nodes[index1], index2); heapIndexMap.put(nodes[index2], index1); Node tmp = nodes[index1]; nodes[index1] = nodes[index2]; nodes[index2] = tmp; } // Dijkstra's improved algorithm // Start from head, all nodes that head can reach, Public static HashMap<Node, Integer> dijkstra2(Node head, int size) { NodeHeap nodeHeap = new NodeHeap(size); nodeHeap.addOrUpdateOrIgnore(head, 0); HashMap<Node, Integer> result = new HashMap<>(); while (! nodeHeap.isEmpty()) { NodeRecord record = nodeHeap.pop(); Node cur = record.node; int distance = record.distance; for (Edge edge : cur.edges) { nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance); } result.put(cur, distance); } return result; }}Copy the code