@TOC
并查集、图
并查集
- 有若干个样本a、b、C、d类型假设是V
2)在并查集中一开始认为每个样本都在单独的集合里
3)用户可以在任何时候调用如下两个方法:
boolean isSameSet(Vx, V y):查询样本x和样本y是否属于一个集合
void union(V x, V y):把x和y各自所在集合的所有样本合并成- -个集合 - isSameSet和union方法的代价越低越好
步骤：
建立map，k为节点，v为节点的指向节点
1.首先第一步将所有各自的数目整成一个集合（每个节点单独形成一个集合）
2.在一个集合中每个节点都是自己集合中的代表节点，当集合合并的时候，如果决定将2挂到1的底下，此时2所在集合中，只有1节点指向自己，所以1为这个集合的代表节点。
3.由于每一个集合中都有一个集合的代表节点，所以可以通过代表节点来进行是否在同一个集合的判断，也可以将另外一个集合的代表节点连接到本集合中，此时整个集合也只有一个代表节点，实现集合的整合。（首先进行元素数目的判断，将少元素的集合挂到多元素的底下）
优化：在向上查找的过程中，将路径上的所有元素直接连接到代表节点上。
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code04_UnionFind {
public static class Element<V> {//加了个封装
public V value;
public Element(V value) {
this.value = value;
}
}
public static class UnionFindSet<V> {
public HashMap<V, Element<V>> elementMap;//v为值，Element为元素
public HashMap<Element<V>, Element<V>> fatherMap;//父节点
public HashMap<Element<V>, Integer> sizeMap;//代表节点的集合有多少个节点
public UnionFindSet(List<V> list) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
for (V value : list) {
//初始化
Element<V> element = new Element<V>(value);
elementMap.put(value, element);
fatherMap.put(element, element);//每个节点是自己的父
sizeMap.put(element, 1);//每个节点是自己代表节点
}
}
private Element<V> findHead(Element<V> element) {
Stack<Element<V>> path = new Stack<>();//沿途的路
while (element != fatherMap.get(element)) {
path.push(element);//一直走到代表节点
element = fatherMap.get(element);
}
while (!path.isEmpty()) {
//扁平化，所有的节点都是直接指向代表节点的
fatherMap.put(path.pop(), element);
}
return element;
}
public boolean isSameSet(V a, V b) {
//看a有没有注册过，一个值都有对应的element
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
// 如果有一个点没有登记过则不进行查找
return false;
}
public void union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
//先找代表节点【头结点】
Element<V> aF = findHead(elementMap.get(a));//找a对应的元素的代表节点
Element<V> bF = findHead(elementMap.get(b));//代表节点里面有这个结合的大小
if (aF != bF) {
int aSetsize = sizeMap. get(aHead);
int bSetSize = sizeMap . get(bHead);
// bf 小，将小的节点挂在 大的节点上，直接副高parents中的记录
if (aSetSize >= bSetSize) {
parents . put(bF, aF);
sizeMap. put(aF, aSetSize + bSetSize); .
sizeMap . remove(bF);
} else {
parents . put( aF, bF);
sizeMap . put(bHead, aSetSize + bSetSize);
sizeMap . remove(bF);
}
}
}
}
}
岛屿问题
一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右
- 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？
- 举例：
0 0 1 0 1 0
1 1 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
这个矩阵中有三个岛。
public static int countIslands(Int[][] m){
if(m == null || m[0] == null){
return 0;
}
int N = m.length;
int M = m[0].length;
int res = 0;
for(int i = 0;i<N;i++){
for(int j = 0;j<M;j++{
if(m[i][j] == 1){
res++;
infect(m,i,j,N,M);
}
}
}
return res;
}
public static void infect(int[][]m,int i,int j,int N,int M){
if(i<0 || i>=N||j<0||j>=M || m[i][j] != 1){
return ;
}
m[i][j] =2;
infect(m,i+1,j,N,M);
infect(m,i,j+1,N,M);
infect(m,i-1,j,N,M);
infect(m,i,j-1,N,M);
}
切分矩阵，并行
核心逻辑：切割矩阵。分成n块，记录边界的信息
我们把刀附近的2标记为属于a，之后合并的时候看一下，ac是不是一个集合，不是，但是刀左右，所以合并为一个岛屿。
记录边界信息，建立节点，然后用并查集来判断到底有几个集合
图
1).由点的集合和边的集合构成
2)虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
3)边上可能带有权值
图：
public class Graph {
public HashMap<Integer,Node> nodes;//点的集合
public HashSet<Edge> edges;//边的集合
public Graph() {
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
点：
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<>();
}
}
边：
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 {
public static Graph createGraph(Integer[][] matrix) {//输入一个矩阵
Graph graph = new Graph();//初始化自定义的图
for (int i = 0; i < matrix.length; i++) {
Integer weight = matrix[i][0];//边的权重
Integer from = matrix[i][1];//from节点的序列
Integer to = matrix[i][2];//to节点的序列
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的邻接点增加了一个to节点
fromNode.out++;//from的出度加1
toNode.in++;//to节点的入度加1
fromNode.edges.add(newEdge);//from节点的边集增加
graph.edges.add(newEdge);//加到整个图的边集里
}
return graph;
}
}
广（宽）度优先遍历
1，利用队列实现
2，从源节点开始依次按照宽度进队列，然后弹出
3，每弹出一个点，把该节点所有没有进过队列的邻接点放入队 列
4，直到队列变空
public class Code_01_BFS {
public static void bfs(Node node) {//广(宽)度优先遍历
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
HashSet<Node> map = new HashSet<>();
queue.add(node);
map.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();//将当前节点拿出来
System.out.println(cur.value);//打印当前的节点
for (Node next : cur.nexts) {//遍历当前节点的所有邻接点
if (!map.contains(next)) {//如果有某个邻接点已经在set里边了，就不再需要了
map.add(next);
queue.add(next);
}
}
}
}
}
深度优先遍历
1，利用栈实现
2，从源节点开始把节点按照深 度放入栈，然后弹出
3，每弹出一个点，把该节点下一个没有 进过栈的邻接点放入栈
4，直到栈变空
public class Code_02_DFS {
public 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)){//如果set中没有下一个的节点就继续
stack.push(cur);//先把当前的节点重新放进去栈中
stack.push(next);//再把下一个节点放进去栈中
set.add(next);//set集合中添加下一个节点
System.out.println(next.value);//打印下一个节点的值
break;//不再继续进行当前的这个循环了，重新回到while循环中，继续下一个节点的遍历先
}
}
}
}
}
拓扑排序算法
适用范围：要求有向图，且有入度为0的节点，且没有环
实现的逻辑就是：先找出入度为0的节点，然后把他们打印，并且打印完成之后就马上删除掉，然后继续搜索图，找出新的入度为0的节点，继续前边的操作，直到图被完全遍历。
public class Code_03_TopologySort {
// directed graph and no loop
public static List<Node> sortedTopology(Graph graph) {
HashMap<Node, Integer> inMap = new HashMap<>();//记录所有入点
Queue<Node> zeroInQueue = new LinkedList<>();//记录所有入度为0的节点
for (Node node : graph.nodes.values()) {//values就是当前所有点的意思
inMap.put(node, node.in);//将入点全部登记
if (node.in == 0) {
zeroInQueue.add(node);//将所有入度为0的节点登记
}
}
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);//找出新的入度为0的点
if (inMap.get(next) == 0) {
zeroInQueue.add(next);
}
}
}
return result;
}
}
最小生成树以及相关算法
关于图的几个概念定义：
连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
kruskal算法（K算法） 适用范围：要求无向图
1)总是从权值最小的边开始考虑，依次考察权值依次变大的边
2)当前的边要么进入最小生成树的集合，要么丢弃
3)如果当前的边进入最小生成树的集合中不会形成环，就要当前边
4)如果当前的边进入最小生成树的集合中会形成环，就不要当前边
5)考察完所有边之后，最小生成树的集合也得到了
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
把图中的所有边按代价从小到大排序；
把图中的n个顶点看成独立的n棵树组成的森林；
按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
//undirected graph only
public class Code_04_Kruskal {
// Union-Find Set
public static class UnionFind {
private HashMap<Node, Node> fatherMap;
private HashMap<Node, Integer> rankMap;
public UnionFind() {
fatherMap = new HashMap<Node, Node>();
rankMap = new HashMap<Node, Integer>();
}
private Node findFather(Node n) {
Node father = fatherMap.get(n);
if (father != n) {
father = findFather(father);
}
fatherMap.put(n, father);
return father;
}
public void makeSets(Collection<Node> nodes) {
fatherMap.clear();
rankMap.clear();
for (Node node : nodes) {
fatherMap.put(node, node);
rankMap.put(node, 1);
}
}
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 aFather = findFather(a);
Node bFather = findFather(b);
if (aFather != bFather) {
int aFrank = rankMap.get(aFather);
int bFrank = rankMap.get(bFather);
if (aFrank <= bFrank) {
fatherMap.put(aFather, bFather);
rankMap.put(bFather, aFrank + bFrank);
} else {
fatherMap.put(bFather, aFather);
rankMap.put(aFather, aFrank + bFrank);
}
}
}
}
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) {
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算法（P算法）
此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。
图的所有顶点集合为VV；初始令集合u=,v=V−uu=,v=V−u;
在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。
由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息，：
// undirected graph only
public class Code_05_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()) {
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);
}
}
}
}
}
return result;
}
}
迪杰斯特拉算法
求解单元点的最短路径问题：给定带权有向图G和源点v，求v到G中其他顶点的最短路径
限制条件：图G中不存在负权值的边
迪杰斯特拉算法总共就干了两件事：
【1】不断运行广度优先算法找可见点，计算可见点到源点的距离长度
【2】从当前已知的路径中选择长度最短的将其顶点加入S作为确定找到的最短路径的顶点。
// no negative weight
public class Code_06_Dijkstra {
public static HashMap<Node, Integer> dijkstra1(Node from) {
HashMap<Node, Integer> distanceMap = new HashMap<>();
distanceMap.put(from, 0);
//已经选择过的结点
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);
}
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> distanceMap;
private int size;
public NodeHeap(int size) {
nodes = new Node[size];
heapIndexMap = new HashMap<>();
distanceMap = new HashMap<>();
this.size = 0;
}
public boolean isEmpty() {
return size == 0;
}
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]);
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;
}
}
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;
}
}