算法基础学习3
一、图
基本模板
Graph
public class Graph {
public HashMap nodes;
public HashSet edges;
public Graph() {
nodes = new HashMap();
edges = new HashSet<>();
}
}
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;
}
}
Node
public class Node {
public int value;
public int in;
public int out;
public ArrayList nexts;
public ArrayList edges;
public Node(int value) {
this.value = https://www.it610.com/article/value;
in = 0;
out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
遍历 广度优先
/**
* 图的广度优先遍历
* 使用队列，为了保证不重复遍历，所以使用了set进行重复判断
*/
public static void BFS(Node node){
Queue queue = new LinkedList<>();
HashSet set = new HashSet<>();
queue.add(node);
set.add(node);
while (! queue.isEmpty()){
//弹出打印
Node poll = queue.poll();
System.out.print(poll.value+" ");
//获取节点的next点
ArrayList nexts = poll.nexts;
for (Node next: nexts){
//是否在set中
if (! set.contains(next)){
set.add(next);
queue.add(next);
}
}
}}
深度优先
/**
* 图的深度优先遍历
* 准备栈和set集合
* 在添加元素进入set时，就处理打印
* 步骤L
* 依次弹出栈一直到空
*获取node的next,遍历next,判断next是否在set中
*1.在set中，继续判断下一个next
*2.不在set中，将本node和该next压入栈，然后将next加入到set，再处理打印set
*
*/
public static void DFS(Node node){
Stack stack = new Stack<>();
HashSet set = new HashSet<>();
stack.add(node);
set.add(node);
System.out.print(node.value+" ");
while (!set.isEmpty()){
Node pop = stack.pop();
ArrayList nexts = pop.nexts;
for (Node next: nexts){
//不在set中
if (!set.contains(next)){
//将原node和该next压入栈
stack.push(pop);
stack.push(next);
set.add(next);
System.out.print(next.value+" ");
//不在处理后面的next节点，退出进行深度遍历
break;
}
}}}
拓扑排序
/**
* 拓扑排序
* 准备HashMap容器，记录每个点的入度
* 准备queue容器用来实现遍历
* 将所有node遍历，将每个点的入度对应记录在map中
*此时然后将入度为零的点加入到queue中，
* 遍历从queue开始，遍历到的点，那么该点的nexts中的next点入度--,更新map
*更新后，如果该点入度为0,加入到queue中
* 循环至queue为空
*/
public static List TopologySort(Graph graph){
List result = new ArrayList<>();
HashMap inMap = new HashMap<>();
Queue zeroInQueue = new LinkedList<>();
//node遍历，将每个点的入度对应记录在map中
for (Node node: graph.nodes.values()){
inMap.put(node,node.in);
if (node.in == 0){
zeroInQueue.add(node);
}
}
//遍历queue
while (!zeroInQueue.isEmpty()){
Node poll = zeroInQueue.poll();
result.add(poll);
//该点的nexts中的next点入度--,更新map
for (Node next: poll.nexts){
//入度更新
Integer in = inMap.get(next);
inMap.put(next,in--);
//入度为0,加入到queue中
if (in == 0){
zeroInQueue.add(next);
}
}
}
return result;
}
Kruskal最小生成树
public class Kruskal {
public static class MySets{
//每个节点的所属集合
private HashMap> setMap;
//构造
public MySets(List nodes){
for (Node node: nodes){
//每个节点初始所属集合中只有自己
List list = new ArrayList<>();
list.add(node);
//为属性赋值
setMap.put(node,list);
}
}
//接口：判断是否在同一集合中
public boolean isSameSet(Node from,Node to){
List fromList = setMap.get(from);
List toList = setMap.get(to);
return fromList == toList;
}
//接口：将集合合并
public void unionSet(Node from,Node to){
List fromList = setMap.get(from);
List toList = setMap.get(to);
//将toList中的节点加入到from集合中，
//并且！ 更改to集合节点所属
for (Node node: toList){
fromList.add(node);
setMap.put(node,fromList);
}
}}/**
* kruskal算法最小生成树
* 接口：1.是否处于一个集合
*2.将集合合并
*
* 按照边的权值从小到大开始连接图，查看时候会出现环（也就是对应代码中两个节点的所属集合是同一个）
* 如果在连接后出现环，则不连接
* 如果不出现环，则连接，并更新from节点的所属集合（将集合合并，用于判断环），将节点添加到结果集中
*/
public static Set kruskalMST(Graph graph){
List list = (List) graph.nodes.values();
//初始化mysets
MySets mySets = new MySets(list);
//按照边的权值大小，加入到queue中并排序
PriorityQueue queue = new PriorityQueue<>(Comparator.comparingInt(x -> x.weight));
queue.addAll(graph.edges);
//结果集
Set result = new HashSet<>();
while (! queue.isEmpty()){
Edge edge = queue.poll();
//不在一个集合中
if (!mySets.isSameSet(edge.from, edge.to)){
//则连接，并更新from节点的所属集合
result.add(edge);
mySets.unionSet(edge.from,edge.to);
}
}
return result;
}
}
Prim
/**
* 准备queue用来遍历
* 准备set用来判断是否已经加入过
* 先将所有边从小到大加入到queue中
* 循环：从queue中取出边，判断该边的目的点是否已经在set中（k算法在此步是判断是否会成环）
*如果不在set中，则说明没有，加入到set中，并且将该点的edges加入到queue中，此时会产生重复，但set会判断
*如果在set中，弹出下一个，继续循环
*/
public static Set primMST(Graph graph) {
PriorityQueue priorityQueue = new PriorityQueue<>(Comparator.comparingInt(x -> x.weight));
//判断旧值是否添加过
HashSet set = new HashSet<>();
Set result = new HashSet<>();
//循环是防止图为森林，可以不加
for (Node node : graph.nodes.values()) {
if (!set.contains(node)) {
set.add(node);
//在队列中加入所有边，排序
priorityQueue.addAll(node.edges);
while (!priorityQueue.isEmpty()) {
//弹出最小权值的边
Edge edge = priorityQueue.poll();
Node toNode = edge.to;
//toNode没加入过set
if (!set.contains(toNode)) {
//加入set
set.add(toNode);
result.add(edge);
//结果集中再加入该node的边（会有重复边，但是set会将已经添加过的点忽略）
priorityQueue.addAll(toNode.edges);
}
}}
}
return result;
}
Dijkstra
public class Dijkstra {/***准备一个hashMap用来维持，源点到该node的最短路径,*准备一个set，用来表示已经锁住的node**步骤：*将源节点的对应路径加入map*从这些路径中找到最小权值的边，获取对应的node*获取node的edege对应的toNode*如果toNode不在map中，说明距离为无穷大，直接更新距离为 源到该node+node到toNode的距离*如果在map中，判断源到该node+node到toNode的距离和 原来源到该toNode的距离大小*如果原来大，则不更新，反之更新最小路径*遍历完该node的所有边后，就将该node加入到set中，代表已经扫描过，后续不在扫描**重新从这些路径中找到最小权值的边，获取对应的node**/public static HashMap dijkstra1(Node head) {//源点到该node的最短路径HashMap map = new HashMap<>();
//锁住的nodeHashSet set = new HashSet<>();
//加入第一个节点到map中，到自己的距离为零map.put(head,0);
//获取最小权值的nodeNode minNode = getMinDisUnSelect(map, set);
//能获取到没被锁定的权值最小边while (minNode != null){int distance = map.get(minNode);
for (Edge edge: minNode.edges){//获取node的edeges对应的toNodeNode toNode = edge.to;
//不在map中if (!map.containsKey(toNode)){map.put(toNode, distance+edge.weight);
}else {map.put( toNode,Math.min( distance+edge.weight,map.get(toNode) ) );
}}//当前节点完成遍历，加入到被锁set中set.add(minNode);
//再获取一个minNodeminNode = getMinDisUnSelect(map, set);
}return map;
}//从没有被锁定的点中，获取权值最小的边，并返回对应节点public static Node getMinDisUnSelect(HashMap map,HashSet set){int minDistance = Integer.MAX_VALUE;
Node minNode = null;
for (Entry entry: map.entrySet()){Node node = entry.getKey();
int distance = entry.getValue();
//没被锁住，并且较小if (! set.contains(node) && distance 推荐阅读
- 由浅入深理解AOP
- 继续努力，自主学习家庭Day135(20181015）
- python学习之|python学习之 实现QQ自动发送消息
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一起来学习C语言的字符串转换函数
- 定制一套英文学习方案
- 漫画初学者如何学习漫画背景的透视画法（这篇教程请收藏好了！）
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 如何更好的去学习