Skip to content

Commit 80dd157

Browse files
mood321mood321
committed
算法 学习笔记
1 parent 6686b61 commit 80dd157

14 files changed

Lines changed: 602 additions & 1 deletion

‎src/main/java/algorithm/basic06/Code_01_BFS.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package algorithm.basic06;
2+
3+
import java.util.HashSet;
4+
import java.util.LinkedList;
5+
import java.util.Queue;
6+
7+
public class Code_01_BFS {
8+
9+
public static void bfs(Node node) {
10+
if (node == null) {
11+
return;
12+
}
13+
Queue<Node> queue = new LinkedList<>();
14+
HashSet<Node> map = new HashSet<>();
15+
queue.add(node);
16+
map.add(node);
17+
while (!queue.isEmpty()) {
18+
Node cur = queue.poll();
19+
System.out.println(cur.value);
20+
for (Node next : cur.nexts) {
21+
if (!map.contains(next)) {
22+
map.add(next);
23+
queue.add(next);
24+
}
25+
}
26+
}
27+
}
28+
29+
}

‎src/main/java/algorithm/basic06/Code_02_DFS.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package algorithm.basic06;
2+
3+
import java.util.HashSet;
4+
import java.util.Stack;
5+
6+
public class Code_02_DFS {
7+
8+
public static void dfs(Node node) {
9+
if (node == null) {
10+
return;
11+
}
12+
Stack<Node> stack = new Stack<>();
13+
HashSet<Node> set = new HashSet<>();
14+
stack.add(node);
15+
set.add(node);
16+
System.out.println(node.value);
17+
while (!stack.isEmpty()) {
18+
Node cur = stack.pop();
19+
for (Node next : cur.nexts) {
20+
if (!set.contains(next)) {
21+
stack.push(cur);
22+
stack.push(next);
23+
set.add(next);
24+
System.out.println(next.value);
25+
break;
26+
}
27+
}
28+
}
29+
}
30+
31+
}

‎src/main/java/algorithm/basic06/Code_03_TopologySort.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package algorithm.basic06;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
import java.util.Queue;
8+
9+
public class Code_03_TopologySort {
10+
11+
// directed graph and no loop
12+
public static List<Node> sortedTopology(Graph graph) {
13+
HashMap<Node, Integer> inMap = new HashMap<>();
14+
Queue<Node> zeroInQueue = new LinkedList<>();
15+
for (Node node : graph.nodes.values()) {
16+
inMap.put(node, node.in);
17+
if (node.in == 0) {
18+
zeroInQueue.add(node);
19+
}
20+
}
21+
List<Node> result = new ArrayList<>();
22+
while (!zeroInQueue.isEmpty()) {
23+
Node cur = zeroInQueue.poll();
24+
result.add(cur);
25+
for (Node next : cur.nexts) {
26+
inMap.put(next, inMap.get(next) - 1);
27+
if (inMap.get(next) == 0) {
28+
zeroInQueue.add(next);
29+
}
30+
}
31+
}
32+
return result;
33+
}
34+
}

‎src/main/java/algorithm/basic06/Code_04_Kruskal.java‎

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package algorithm.basic06;
2+
3+
import java.util.Collection;
4+
import java.util.Comparator;
5+
import java.util.HashMap;
6+
import java.util.HashSet;
7+
import java.util.PriorityQueue;
8+
import java.util.Set;
9+
10+
//undirected graph only
11+
public class Code_04_Kruskal {
12+
13+
// Union-Find Set
14+
public static class UnionFind {
15+
private HashMap<Node, Node> fatherMap;
16+
private HashMap<Node, Integer> rankMap;
17+
18+
public UnionFind() {
19+
fatherMap = new HashMap<Node, Node>();
20+
rankMap = new HashMap<Node, Integer>();
21+
}
22+
23+
private Node findFather(Node n) {
24+
Node father = fatherMap.get(n);
25+
if (father != n) {
26+
father = findFather(father);
27+
}
28+
fatherMap.put(n, father);
29+
return father;
30+
}
31+
32+
public void makeSets(Collection<Node> nodes) {
33+
fatherMap.clear();
34+
rankMap.clear();
35+
for (Node node : nodes) {
36+
fatherMap.put(node, node);
37+
rankMap.put(node, 1);
38+
}
39+
}
40+
41+
public boolean isSameSet(Node a, Node b) {
42+
return findFather(a) == findFather(b);
43+
}
44+
45+
public void union(Node a, Node b) {
46+
if (a == null || b == null) {
47+
return;
48+
}
49+
Node aFather = findFather(a);
50+
Node bFather = findFather(b);
51+
if (aFather != bFather) {
52+
int aFrank = rankMap.get(aFather);
53+
int bFrank = rankMap.get(bFather);
54+
if (aFrank <= bFrank) {
55+
fatherMap.put(aFather, bFather);
56+
rankMap.put(bFather, aFrank + bFrank);
57+
} else {
58+
fatherMap.put(bFather, aFather);
59+
rankMap.put(aFather, aFrank + bFrank);
60+
}
61+
}
62+
}
63+
}
64+
65+
public static class EdgeComparator implements Comparator<Edge> {
66+
67+
@Override
68+
public int compare(Edge o1, Edge o2) {
69+
return o1.weight - o2.weight;
70+
}
71+
72+
}
73+
74+
public static Set<Edge> kruskalMST(Graph graph) {
75+
UnionFind unionFind = new UnionFind();
76+
unionFind.makeSets(graph.nodes.values());
77+
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
78+
for (Edge edge : graph.edges) {
79+
priorityQueue.add(edge);
80+
}
81+
Set<Edge> result = new HashSet<>();
82+
while (!priorityQueue.isEmpty()) {
83+
Edge edge = priorityQueue.poll();
84+
if (!unionFind.isSameSet(edge.from, edge.to)) {
85+
result.add(edge);
86+
unionFind.union(edge.from, edge.to);
87+
}
88+
}
89+
return result;
90+
}
91+
}

‎src/main/java/algorithm/basic06/Code_05_Prim.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package algorithm.basic06;
2+
3+
import java.util.Comparator;
4+
import java.util.HashSet;
5+
import java.util.PriorityQueue;
6+
import java.util.Set;
7+
8+
// undirected graph only
9+
public class Code_05_Prim {
10+
11+
public static class EdgeComparator implements Comparator<Edge> {
12+
13+
@Override
14+
public int compare(Edge o1, Edge o2) {
15+
return o1.weight - o2.weight;
16+
}
17+
18+
}
19+
20+
public static Set<Edge> primMST(Graph graph) {
21+
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(
22+
new EdgeComparator());
23+
HashSet<Node> set = new HashSet<>();
24+
Set<Edge> result = new HashSet<>();
25+
for (Node node : graph.nodes.values()) {
26+
if (!set.contains(node)) {
27+
set.add(node);
28+
for (Edge edge : node.edges) {
29+
priorityQueue.add(edge);
30+
}
31+
while (!priorityQueue.isEmpty()) {
32+
Edge edge = priorityQueue.poll();
33+
Node toNode = edge.to;
34+
if (!set.contains(toNode)) {
35+
set.add(toNode);
36+
result.add(edge);
37+
for (Edge nextEdge : toNode.edges) {
38+
priorityQueue.add(nextEdge);
39+
}
40+
}
41+
}
42+
}
43+
}
44+
return result;
45+
}
46+
47+
}

‎src/main/java/algorithm/basic06/Code_06_Dijkstra.java‎

Lines changed: 151 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,151 @@
1+
package algorithm.basic06;
2+
3+
import java.util.HashMap;
4+
import java.util.HashSet;
5+
import java.util.Map.Entry;
6+
7+
// no negative weight
8+
public class Code_06_Dijkstra {
9+
10+
public static HashMap<Node, Integer> dijkstra1(Node head) {
11+
HashMap<Node, Integer> distanceMap = new HashMap<>();
12+
distanceMap.put(head, 0);
13+
HashSet<Node> selectedNodes = new HashSet<>();
14+
15+
Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
16+
while (minNode != null) {
17+
int distance = distanceMap.get(minNode);
18+
for (Edge edge : minNode.edges) {
19+
Node toNode = edge.to;
20+
if (!distanceMap.containsKey(toNode)) {
21+
distanceMap.put(toNode, distance + edge.weight);
22+
}
23+
distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
24+
}
25+
selectedNodes.add(minNode);
26+
minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
27+
}
28+
return distanceMap;
29+
}
30+
31+
public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap,
32+
HashSet<Node> touchedNodes) {
33+
Node minNode = null;
34+
int minDistance = Integer.MAX_VALUE;
35+
for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
36+
Node node = entry.getKey();
37+
int distance = entry.getValue();
38+
if (!touchedNodes.contains(node) && distance < minDistance) {
39+
minNode = node;
40+
minDistance = distance;
41+
}
42+
}
43+
return minNode;
44+
}
45+
46+
public static class NodeRecord {
47+
public Node node;
48+
public int distance;
49+
50+
public NodeRecord(Node node, int distance) {
51+
this.node = node;
52+
this.distance = distance;
53+
}
54+
}
55+
56+
public static class NodeHeap {
57+
private Node[] nodes;
58+
private HashMap<Node, Integer> heapIndexMap;
59+
private HashMap<Node, Integer> distanceMap;
60+
private int size;
61+
62+
public NodeHeap(int size) {
63+
nodes = new Node[size];
64+
heapIndexMap = new HashMap<>();
65+
distanceMap = new HashMap<>();
66+
this.size = 0;
67+
}
68+
69+
public boolean isEmpty() {
70+
return size == 0;
71+
}
72+
73+
public void addOrUpdateOrIgnore(Node node, int distance) {
74+
if (inHeap(node)) {
75+
distanceMap.put(node, Math.min(distanceMap.get(node), distance));
76+
insertHeapify(node, heapIndexMap.get(node));
77+
}
78+
if (!isEntered(node)) {
79+
nodes[size] = node;
80+
heapIndexMap.put(node, size);
81+
distanceMap.put(node, distance);
82+
insertHeapify(node, size++);
83+
}
84+
}
85+
86+
public NodeRecord pop() {
87+
NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
88+
swap(0, size - 1);
89+
heapIndexMap.put(nodes[size - 1], -1);
90+
distanceMap.remove(nodes[size - 1]);
91+
nodes[size - 1] = null;
92+
heapify(0, --size);
93+
return nodeRecord;
94+
}
95+
96+
private void insertHeapify(Node node, int index) {
97+
while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
98+
swap(index, (index - 1) / 2);
99+
index = (index - 1) / 2;
100+
}
101+
}
102+
103+
private void heapify(int index, int size) {
104+
int left = index * 2 + 1;
105+
while (left < size) {
106+
int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
107+
? left + 1 : left;
108+
smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
109+
if (smallest == index) {
110+
break;
111+
}
112+
swap(smallest, index);
113+
index = smallest;
114+
left = index * 2 + 1;
115+
}
116+
}
117+
118+
private boolean isEntered(Node node) {
119+
return heapIndexMap.containsKey(node);
120+
}
121+
122+
private boolean inHeap(Node node) {
123+
return isEntered(node) && heapIndexMap.get(node) != -1;
124+
}
125+
126+
private void swap(int index1, int index2) {
127+
heapIndexMap.put(nodes[index1], index2);
128+
heapIndexMap.put(nodes[index2], index1);
129+
Node tmp = nodes[index1];
130+
nodes[index1] = nodes[index2];
131+
nodes[index2] = tmp;
132+
}
133+
}
134+
135+
public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
136+
NodeHeap nodeHeap = new NodeHeap(size);
137+
nodeHeap.addOrUpdateOrIgnore(head, 0);
138+
HashMap<Node, Integer> result = new HashMap<>();
139+
while (!nodeHeap.isEmpty()) {
140+
NodeRecord record = nodeHeap.pop();
141+
Node cur = record.node;
142+
int distance = record.distance;
143+
for (Edge edge : cur.edges) {
144+
nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
145+
}
146+
result.put(cur, distance);
147+
}
148+
return result;
149+
}
150+
151+
}

0 commit comments

Comments
 (0)