图
将图拆解为点、边、图三种结构
点的定义
一个点包含自己的值、入度、出度、直接相邻的点(由自己出发的点)、相连的边(由自己出发的点)
代码语言：javascript复制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;
int in = 0;
int out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}边的定义
一条边包含自己的权重、起点和终点
代码语言：javascript复制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;
}
}图的定义
代码语言：javascript复制public class Graph {
//K:点的编号，V:点
public HashMap<Integer, Node> nodes;
public HashSet<Edge> edges;
public Graph() {
nodes = new HashMap<>();
edges = new HashSet<>();
}
}建立一个图
代码语言：javascript复制public static Graph createGraph(Integer[][] matrix) {
Graph graph = new Graph();
for (int i = 0; i < matrix.length; i ) {
// matrix[0][0], matrix[0][1] matrix[0][2]
Integer weight = matrix[i][0];
Integer from = matrix[i][1];
Integer to = matrix[i][2];
//如果from和to不存在图中，则先加到图中去
if (!graph.nodes.containsKey(from)) {
graph.nodes.put(from, new Node(from));
}
if (!graph.nodes.containsKey(to)) {
graph.nodes.put(to, new Node(to));
}
//得到From和to两个点，建立边
Node fromNode = graph.nodes.get(from);
Node toNode = graph.nodes.get(to);
Edge newEdge = new Edge(weight, fromNode, toNode);
//from 出度 ，相邻点 , 相邻边 ; to点入度 , 图的边
fromNode.nexts.add(toNode);
fromNode.out ;
toNode.in ;
fromNode.edges.add(newEdge);
graph.edges.add(newEdge);
}
return graph;
}图的宽度优先遍历(BFS)
按照上面的结构遍历BFS只用输入一个点就可以了。从一个点开始，将其放入到队列和集合中，如果队列不为空则弹出队头元素打印，并将它相邻的点放入队列中(没进入过set),当队列不为空是就打印元素。
代码语言：javascript复制public class 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.va lue);
for (Node next : cur.nexts) {
//防止重复加入元素
if (!set.contains(next)) {
set.add(next);
queue.add(next);
}
}
}
}
}图的深度优先遍历(DFS)
通过一个stack和hashset完成DFS，stack相当与存储当前遍历的一条路径。 从任意一个节点开始，将其放入栈和集合中并打印。当栈不为空时，弹出栈顶作为当前节点，再遍历当前的节点的相邻节点。当前节点任意一个相邻节点没有进过栈则，把当前节点和相邻节点压入栈中去，记录并打印相邻点 break。
代码语言：javascript复制public class 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;
}
}
}
}拓扑排序
拓扑排序算法 1）在图中找到所有入度为0的点 2）把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始 3）图中所有点都被删除后，一次输出的顺序就是拓扑排序 要求：有向图且其中没有环 应用：事件安排、编译顺序 意思就是根据一张有向无环图玩安排时间发生的顺序
代码语言：javascript复制public class TopologySort {
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);
//消除前面入度为0的点的影响，如果产生了新的入度为0的点
//则加入队列中去
for (Node next : cur.nexts) {
inMap.put(next, inMap.get(next) - 1);
if (inMap.get(next) == 0) {
zeroInQueue.add(next);
}
}
}
return result;
}
}图的最小生成树的问题
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树
Kruskal算法
使用并查集来处理这个问题。将所有的边根据权值大小排序。 1）总是从权值最小的边开始考虑，依次考察权值一次变大的边 2）当前的边要么进入最小生成树的集合，要么被舍弃 3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边 4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边 5）考察完所有边之后，最小生成树的集合也得到了
代码语言：javascript复制public class Kruskal {
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 makeSet(Collection<Node> nodes) {
fatherMap.clear();
sizeMap.clear();
for (Node node : nodes) {
fatherMap.put(node, node);
sizeMap.put(node, 1);
}
}
private Node findFather(Node cur) {
Stack<Node> path = new Stack<>();
while(cur != fatherMap.get(cur)) {
path.add(cur);
cur = fatherMap.get(cur);
}
while (!path.isEmpty()) {
fatherMap.put(path.pop(), cur);
}
return cur;
}
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 headA = findFather(a);
Node headB = findFather(b);
if (headA != headB) {
int aSetSize = sizeMap.get(headA);
int bSetSize = sizeMap.get(headB);
if (aSetSize <= bSetSize) {
fatherMap.put(headA, headB);
sizeMap.put(headB, aSetSize bSetSize);
sizeMap.remove(headA);
} else {
fatherMap.put(headB, headA);
sizeMap.put(headA, aSetSize bSetSize);
sizeMap.remove(headB);
}
}
}
}
//比较边的权值大小
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.makeSet(graph.nodes.values());
//使用小根堆
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
for (Edge edge : graph.edges) {
priorityQueue.add(edge);
}
Set<Edge> result = new HashSet<>();
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
//如果边的两点不是同一集合，加入一个集合中去
if (!unionFind.isSameSet(edge.from, edge.to)) {
result.add(edge);
unionFind.union(edge.from, edge.to);
}
}
return result;
}
}Prim算法
1)指定一个出发点将其解锁，并将其相连的边一同解锁 2)在所有解锁的边里选一个最小的边，然后看这个边两侧有没有新节点，则选择这条边，并解锁该新节点 3) 新节点相连的所有边被解锁
代码语言：javascript复制import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
public class 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> nodeSet = new HashSet<>();
Set<Edge> result = new HashSet<>();
for (Node node : graph.nodes.values()) {
if (!nodeSet.contains(node)){
nodeSet.add(node);
for (Edge edge : node.edges) {
priorityQueue.add(edge);
}
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
Node toNode = edge.to;
if (!nodeSet.contains(toNode)) {
nodeSet.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
priorityQueue.add(nextEdge);
}
}
}
}
}
return result;
}
public static int prim(int[][] graph) {
int size = graph.length;
int[] distance = new int[size];
boolean[] visit = new boolean[size];
visit[0] = true;
for (int i = 0; i < size; i ){
distance[i] = graph[0][i];
}
int sum = 0;
for (int i = 0; i < size; i ) {
int minPath = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < size; j ) {
if(!visit[j] && distance[j] < minPath) {
minPath =distance[j];
minIndex = j;
}
}
if (minIndex == -1){
return sum;
}
visit[minIndex] = true;
sum = minPath;
for (int j = 0; j < size; j ){
if (!visit[j] && distance[j] > graph[minIndex][j]) {
distance[j] = graph[minIndex][j];
}
}
}
return sum;
}
}Dijkstra算法
Dijkstra算法用于计算带权有向图中单源最短路径。
代码语言：javascript复制public class Dijkstra {
public static HashMap<Node, Integer> dijkstra1(Node from) {
// 从head出发到所有点的最小距离
// key : 从head出发到达key
// value : 从head出发到达key的最小距离
// 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
HashMap<Node, Integer> distanceMap = new HashMap<>();
distanceMap.put(from, 0);
// 已经求过距离的节点，存在selectedNodes中，以后再也不碰
HashSet<Node> selectedNodes = new HashSet<>();
// from 0
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;
}
}
