图的存储方式
- 临接表
- 临接矩阵
表达
- 点集/边集
- 有向图/无向图
Graph（大结构就是图）（包含点集合和边集合）
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<>();
}
}
复制代码Node（点集合）
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<>();
edges = new ArrayList<>();
}
}
复制代码Edge（边集合）
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;
}
}
复制代码接口函数（将未知的题目类型转化为我们所熟知的类型，如上图所示）
public class GraphGenerator {
// matrix 所有的边
// N*3 的矩阵
// [weight, from节点上面的值，to节点上面的值]
//example
//【7，0，1】第一个代表from，第二个代表to，第三个代表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)) {//将未出现的from放入点集合
graph.nodes.put(from, new Node(from));
}
if (!graph.nodes.containsKey(to)) {//将未出现的to放入点集合
graph.nodes.put(to, new Node(to));
}
Node fromNode = graph.nodes.get(from);//获取from点
Node toNode = graph.nodes.get(to);//获取to点
Edge newEdge = new Edge(weight, fromNode, toNode);//创建边
fromNode.nexts.add(toNode);//from邻居
fromNode.out++;//出度++
toNode.in++;//入度++
fromNode.edges.add(newEdge);//将边放到我所拥有的边集合里面
graph.edges.add(newEdge);//放入边值
}
return graph;
}
}
复制代码图的遍历
宽度优先遍历
代码
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Code01_BFS {
// 从node出发，进行宽度优先遍历
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);
}
}
}
}
}
复制代码深度优先遍历
代码
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<>();//保证深度的路径
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;
}
}
}
}
}
复制代码拓扑排序算法
- 要求是有向图，入度为0的节点，且没有环
代码
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) {
// key：某一个node
// value：剩余的入度
HashMap<Node, Integer> inMap = new HashMap<>();
// 入度为0的点，才能进这个队列
Queue<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;
}
}
复制代码Kruskal算法（并查集）
无向图
- 加最小的边，只要不形成环，就加上，否则不加入
代码
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) {//判断from和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);
}
}
}
// Union-Find Set
public static class UnionFind {
// key 某一个节点， value key节点往上的节点
private HashMap<Node, Node> fatherMap;
// key 某一个集合的代表节点, value key所在集合的节点个数
private HashMap<Node, Integer> sizeMap;
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());
for (Edge edge : graph.edges) { // M 条边
priorityQueue.add(edge); // O(logM)
}
Set<Edge> result = new HashSet<>();
while (!priorityQueue.isEmpty()) { // M 条边
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;
}
}
复制代码prim算法
无向图
代码
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<>(); // 依次挑选的的边在result里
for (Node node : graph.nodes.values()) { // 随便挑了一个点
// node 是开始点
if (!set.contains(node)) {
set.add(node);
for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边
priorityQueue.add(edge);
}
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
Node toNode = edge.to; // 可能的一个新的点
if (!set.contains(toNode)) { // 不含有的时候，就是新的点
set.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
priorityQueue.add(nextEdge);
}
}
}
}
//break;
}
return result;
}
// 请保证graph是连通图
// graph[i][j]表示点i到点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!");
}
}
复制代码Dijkstra算法（单元最远路径算法）
- 要求没有权值为负的边
代码
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) {
// 从head出发到所有点的最小距离
// key : 从head出发到达key
// value : 从head出发到达key的最小距离
// 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
HashMap<Node, Integer> distanceMap = new HashMap<>();
distanceMap.put(head, 0);
// 已经求过距离的节点，存在selectedNodes中，以后再也不碰
HashSet<Node> 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; // 实际的堆结构
// key 某一个node， value 上面数组中的位置
private HashMap<Node, Integer> heapIndexMap;
// key 某一个节点， value 从源节点出发到该节点的目前最小距离
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;
}
// 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
// 判断要不要更新，如果需要的话，就更新
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++同学还要把原本堆顶节点析构，对java同学不必
nodes[size - 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算法
// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
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;
}
}
复制代码© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
