面试中最好将题目的图结构转化成自己习惯使用的图结构，然后使用下面的算法模板
public class Graph {public HashMap<Integer,Node> nodes; // Integer点的编号 Node点的数据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];Integer to = matrix[i][2];if (!graph.nodes.containsKey(from)) {graph.nodes.put(from, new Node(from));}if (!graph.nodes.containsKey(to)) {graph.nodes.put(to, new Node(to));}Node fromNode = graph.nodes.get(from);Node toNode = graph.nodes.get(to);Edge newEdge = new Edge(weight, fromNode, toNode);fromNode.nexts.add(toNode);fromNode.out++;toNode.in++;fromNode.edges.add(newEdge);graph.edges.add(newEdge);}return graph;}}
图的宽度优先遍历
- 利用队列实现
- 从源节点开始依次按照宽度进队列，然后弹出
- 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
直到队列变空
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)) { map.add(next); queue.add(next); } } } }广度优先遍历
利用栈实现
- 从源节点开始把节点按照深度放入栈，然后弹出
- 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
- 直到栈变空
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的节点，且没有环
public static List<Node> sortedTopology(Graph graph) {
HashMap<Node, Integer> inMap = new HashMap<>();
Queue<Node> zeroInQueue = new LinkedList<>();
for (Node node : graph.nodes.values()) {
inMap.put(node, node.in);
if (node.in == 0) {
zeroInQueue.add(node);
}
}
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;
}
最小生成树
由生成树定义可知，无向连通图的生成树不是唯一 的，于是最小生成树的定义诞生，即：无向连通图是一个带权图，她的所有生成树中必有一棵边的权值总和最小的生成树（称为：最小代价生成树，即：最小生成树）
综合来说：
- Prim算法时间复杂度（O(n^n)）当顶点较少时选择；
- Kruskal算法时间复杂度（O(e*loge)）主要耗费在边的排序上，故当边较少时适合选择
首先将每一个点放到一个集合里，然后找到与它连接的另一个点，看看是否是相同的集合如果是，则不要，不是则将两个集合合并成一个，要这两个点连接成的边。
下面这种方式利用了并差集，需要研究
可以用MySet代替UnionFind
public static class MySet {
public HashMap<Node, List<Node>> setMap = new HashMap<>();
public MySet (List<Node> nodes) {
for (Node node : nodes) {
ArrayList<Node> arrayList = new ArrayList<Node>();
arrayList.add(node);
setMap.put(node, arrayList);
}
}
public boolean isSameSet (Node from,Node 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 node : toSet) {
fromSet.add(to);
setMap.put(node, fromSet);
}
}
}
// 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算法
目的：求最小生成树 适用范围：要求无向图
先找到一个点，然后找该点与其它点连接权值最小的，且被连接点没有走过的。
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;
}
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);
}
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;
}
一定要会自定义重写堆，下面有例子
// no negative weight
public class Dijkstra {
public static HashMap<Node, Integer> dijkstra1(Node head) {
HashMap<Node, Integer> distanceMap = new HashMap<>();
distanceMap.put(head, 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;
}
}
// 改进后的算法
// 从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;
}
}
若有收获，就点个赞吧
0 人点赞
