图的概念
什么是图
- 图是由点和边的集合构成
- 虽然有无向边，但可以看成有向边（双向边）
- 边上可能带有权值
图结构的表达
邻接法（示例）
| 邻接法 | | | —- | —- | | 1 | 3（1） | | 2 | 3（1） | | 1 | 7（9） | | 5 | 4（6） | | 4 | 7（2） | | 3 | 6（6） | | 5 | 6（2） | | 6 | 7（5） |
邻接矩阵法（示例）
{[1,1,3],[1,2,3],[9,1,7],[6,5,4],[2,4,7],6,3,6],[2,6,5],[5,6,7]}
数据第一个值表示权重，第二个值表示起点，第二个值表示终点。
其他方法——对象方法
点对象，边对象，图对象
/*** 点对象类** @author :Administrator* @date :2022/4/15 0015*/public class Point {/*** 该点的值*/protected int value;/*** 入度 指向该点的边的数量*/protected int in;/*** 出度，该点指向其他点，边的数量*/protected int out;/*** 该点指向的点*/protected List<Point> next;/*** 从该点出发的边*/protected List<Edge> edges;public Point(int value) {this.value = value;in = 0;out = 0;next = new ArrayList<>();edges = new ArrayList<>();}}
/*** 边对象类** @author :Administrator* @date :2022/4/15 0015*/public class Edge {/*** 边的起点*/protected Point from;/*** 边的终点*/protected Point to;/*** 边的权重*/protected int weight;public Edge(Point from, Point to, int weight) {this.from = from;this.to = to;this.weight = weight;}}
/**
* 图对象类
*
* @author :Administrator
* @date :2022/4/15 0015
*/
public class Graph {
/**
* 组成图的点集
*/
protected HashMap<Integer, Point> points;
/**
* 组成图的边集
*/
protected HashSet<Edge> edges;
public Graph() {
points = new HashMap<>();
edges = new HashSet<>();
}
}
图结构的转化
将不熟悉的图表达方式转换为熟悉的图表达方式，在此熟悉的图表达方式上写算法，出错概率会相对低一些。
/**
* 邻接矩阵表示法转换为对象标识符
*
* @param matrix 为n*3的矩阵，矩阵每一行为点到点的表示，第一个值为权重，第二个值为起点，第三个值为终点
* @return 图对象
*/
public Graph matrixToGraph(int[][] matrix) {
Graph graph = new Graph();
if (matrix == null || matrix.length == 0) {
return graph;
}
for (int[] arr : matrix) {
int weight = arr[0];
int from = arr[1];
int to = arr[2];
if (!graph.points.containsKey(arr[1])) {
graph.points.put(arr[1], new Point(arr[1]));
}
if (!graph.points.containsKey(arr[2])) {
graph.points.put(arr[2], new Point(arr[2]));
}
Point fromPoint = graph.points.get(from);
Point toPoint = graph.points.get(to);
Edge edge = new Edge(fromPoint, toPoint, weight);
fromPoint.next.add(toPoint);
fromPoint.out++;
fromPoint.edges.add(edge);
toPoint.in++;
graph.edges.add(edge);
}
return graph;
}
图的遍历
宽度优先遍历（BFS,Breadth First Search）——利用队列
- 利用队列实现
- 从源节点开始依次按照宽度进队列，然后弹出
- 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
直到队列变空
//图的宽度优先遍历 public static void bfs(Point start) { if (start == null) { return; } Queue<Point> queue = new LinkedList<>(); HashSet<Point> set = new HashSet<>(); queue.add(start); set.add(start); while (!queue.isEmpty()) { Point cur = queue.poll(); System.out.println(cur.value); for (Point point : cur.next) { if (!set.contains(point)) { queue.offer(point); set.add(point); } } } }深度优先遍历（DFS,Beep First Search）——利用栈
利用栈实现
- 从源节点开始把节点按照深度放入栈，然后弹出
- 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
- 直到栈变空 ```java // 图的深度遍历
public static void dfs(Point start) {
if (start == null) {
return;
}
Stack
stack.push(start);
set.add(start);
System.out.println(start.value);
while (!stack.empty()) {
Point cur = stack.pop();
for (Point next : cur.nexts) {
if (!set.contains(next)) {
stack.push(cur);
stack.push(next);
set.add(next);
System.out.println(next.value);
break;
}
}
}
}
<a name="lBIgW"></a>
## 图的拓扑排序
1）在图中找到所有入度为0的点输出<br />2）把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始<br />3）图的所有点都被删除后，依次输出的顺序就是拓扑排序<br />要求：有向图且其中没有环<br />应用：事件安排、编译顺序<br />Lintcode：[https://www.lintcode.com/problem/127/](https://www.lintcode.com/problem/127/)
<a name="uFmrA"></a>
### 算法1：通过BFS获取拓扑序
```java
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> ans = new ArrayList<>();
if (graph == null || graph.size() == 0) {
return ans;
}
// 将点放入表中，假设所有点入度为0
HashMap<DirectedGraphNode, Integer> integerHashMap = new HashMap<>();
for (DirectedGraphNode directedGraphNode : graph) {
integerHashMap.put(directedGraphNode, 0);
}
// 遍历每个点的neighbor，如果一个点是其他点的邻居，那么入度加1
for (DirectedGraphNode directedGraphNode : graph) {
for (DirectedGraphNode neighbor : directedGraphNode.neighbors) {
integerHashMap.put(neighbor, integerHashMap.get(neighbor) + 1);
}
}
// 将入度为0的点放入集合中
Queue<DirectedGraphNode> queue = new LinkedList<>();
for (DirectedGraphNode directedGraphNode : integerHashMap.keySet()) {
if (integerHashMap.get(directedGraphNode) == 0) {
queue.add(directedGraphNode);
}
}
while (!queue.isEmpty()) {
DirectedGraphNode cur = queue.poll();
ans.add(cur);
// 一个点遍历后，他的邻居的入度减1
for (DirectedGraphNode neighbor : cur.neighbors) {
integerHashMap.put(neighbor, integerHashMap.get(neighbor) - 1);
if (integerHashMap.get(neighbor) == 0) {
queue.add(neighbor);
}
}
}
return ans;
}
算法2：通过DFS获取拓扑序
// 给定一个有向图，图节点的拓扑排序定义如下:
//对于图中的每一条有向边 A -> B , 在拓扑排序中A一定在B之前.
//拓扑排序中的第一个节点可以是图中的任何一个没有其他节点指向它的节点.
//针对给定的有向图找到任意一种拓扑排序的顺序.
private static class DirectedGraphNode {
int label;
List<DirectedGraphNode> neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<DirectedGraphNode>();
}
}
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> ans = new ArrayList<>();
if (graph == null || graph.size() == 0) {
return ans;
}
HashMap<DirectedGraphNode, Info> map = new HashMap<>();
for (DirectedGraphNode directedGraphNode : graph) {
process(directedGraphNode, map);
}
ArrayList<Info> arrayList = new ArrayList<>();
map.forEach((k, v) -> arrayList.add(v));
arrayList.sort((a, b) -> b.deep - a.deep);
for (Info info : arrayList) {
ans.add(info.node);
}
return ans;
}
private static class Info {
DirectedGraphNode node;
int deep;
public Info(DirectedGraphNode node, int deep) {
this.node = node;
this.deep = deep;
}
}
private Info process(DirectedGraphNode cur, HashMap<DirectedGraphNode, Info> map) {
if (map.containsKey(cur)) {
return map.get(cur);
}
int deep = 0;
for (DirectedGraphNode neighbor : cur.neighbors) {
deep = Math.max(deep, process(neighbor, map).deep);
}
Info info = new Info(cur, deep + 1);
map.put(cur, info);
return info;
}
// 给定一个有向图，图节点的拓扑排序定义如下:
//对于图中的每一条有向边 A -> B , 在拓扑排序中A一定在B之前.
//拓扑排序中的第一个节点可以是图中的任何一个没有其他节点指向它的节点.
//针对给定的有向图找到任意一种拓扑排序的顺序.
private static class DirectedGraphNode {
int label;
List<DirectedGraphNode> neighbors;
DirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<DirectedGraphNode>();
}
}
// 点x后面的点次>y后面的点次，那么拓扑序x<y
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> ans = new ArrayList<>();
if (graph == null || graph.size() == 0) {
return ans;
}
HashMap<DirectedGraphNode, Info> map = new HashMap<>();
for (DirectedGraphNode directedGraphNode : graph) {
process(directedGraphNode, map);
}
ArrayList<Info> arr = new ArrayList<>();
map.forEach((k, v) -> arr.add(v));
arr.sort((a, b) -> {
return Long.compare(b.nodes, a.nodes);
});
arr.forEach(info -> ans.add(info.node));
return ans;
}
private static class Info {
DirectedGraphNode node;
long nodes;
public Info(DirectedGraphNode node, long nodes) {
this.node = node;
this.nodes = nodes;
}
}
private Info process(DirectedGraphNode cur, HashMap<DirectedGraphNode, Info> map) {
if (map.containsKey(cur)) {
return map.get(cur);
}
long nodes = 0;
for (DirectedGraphNode neighbor : cur.neighbors) {
nodes += process(neighbor, map).nodes;
}
Info info = new Info(cur, nodes + 1);
map.put(cur, info);
return info;
}
算法3：最小生成树算法——kruskal
1）总是从权值最小的边开始考虑，依次考察权值依次变大的边
2）当前的边要么进入最小生成树的集合，要么丢弃
3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边
4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边
5）考察完所有边之后，最小生成树的集合也得到了
public class Code06_Kruskal {
//1）总是从权值最小的边开始考虑，依次考察权值依次变大的边
//2）当前的边要么进入最小生成树的集合，要么丢弃
//3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边
//4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边
//5）考察完所有边之后，最小生成树的集合也得到了
public Set<Edge> generateTreeByKruskal(Graph graph) {
Set<Edge> ans = new HashSet<>();
if (graph == null) {
return ans;
}
HashSet<Edge> edges = graph.edges;
UnionSet unionSet = new UnionSet(graph.points.values());
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
edges.forEach(priorityQueue::offer);
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
if (!unionSet.isSameSet(edge.from, edge.to)) {
ans.add(edge);
unionSet.union(edge.from, edge.to);
}
}
return ans;
}
private static class UnionSet {
HashMap<Point, Point> parenets;
HashMap<Point, Integer> size;
List<Point> helpList;
public UnionSet(Collection<Point> points) {
parenets = new HashMap<>();
size = new HashMap<>();
helpList = new ArrayList<>();
makeSet(points);
}
private void makeSet(Collection<Point> points) {
for (Point point : points) {
parenets.put(point, point);
size.put(point, 1);
}
}
private Point find(Point point) {
while (point != parenets.get(point)) {
helpList.add(point);
point = parenets.get(point);
}
for (Point subPoint : helpList) {
parenets.put(subPoint, point);
}
helpList.clear();
return point;
}
public boolean isSameSet(Point point1, Point point2) {
Point f1 = find(point1);
Point f2 = find(point2);
return f1 == f2;
}
public void union(Point point1, Point point2) {
if (point1 == null || point2 == null) {
return;
}
Point f1 = find(point1);
Point f2 = find(point2);
if (f1 != f2) {
if (size.get(f1) > size.get(f2)) {
parenets.put(f2, f1);
size.put(f1, size.get(f1) + size.get(f2));
size.remove(f2);
} else {
parenets.put(f1, f2);
size.put(f2, size.get(f1) + size.get(f2));
size.remove(f1);
}
}
}
}
}
算法4：最小生成树算法——Prim
1）可以从任意节点出发来寻找最小生成树
2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边
3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环
4）如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）
5）如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）
6）当所有点都被选取，最小生成树就得到了
public class Code07_Prim {
//1）可以从任意节点出发来寻找最小生成树
//2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边
//3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环
//4）如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）
//5）如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）
//6）当所有点都被选取，最小生成树就得到了
public Set<Edge> generateTreeByPrim(Graph graph) {
Set<Edge> ans = new HashSet<>();
if (graph == null) {
return ans;
}
HashSet<Point> selected = new HashSet<>();
HashMap<Integer, Point> points = graph.points;
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
for (Point point : points.values()) {
if (!selected.contains(point)) {
selected.add(point);
while (!priorityQueue.isEmpty()) {
priorityQueue.addAll(point.edges);
Edge edge = priorityQueue.poll();
Point to = edge.to;
if (!selected.contains(to)) {
ans.add(edge);
selected.add(edge.to);
priorityQueue.addAll(to.edges);
}
}
}
}
return ans;
}
}
算法5：Prim算法应用——最小连通路径和
请保证graph是连通图，graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路，返回值是最小连通图的路径之和
// 请保证graph是连通图
// graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
// 返回值是最小连通图的路径之和
public static int leastPathByPrim(int[][] graph) {
if (graph == null || graph.length == 0) {
return 0;
}
int size = graph.length;
int[] distance = new int[size];
boolean[] visited = new boolean[size];
visited[0] = true;
for (int i = 0; i < size; i++) {
distance[i] = graph[0][i];
}
int sum = 0;
for (int i = 0; i < distance.length; i++) {
int minDistance = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < size; j++) {
if (!visited[j] && distance[j] < minDistance) {
minDistance = distance[j];
minIndex = j;
}
}
if (minIndex == -1) {
return sum;
}
visited[minIndex] = true;
sum += minDistance;
for (int j = 0; j < size; j++) {
if (!visited[j] && distance[j] > graph[minIndex][j]) {
distance[j] = graph[minIndex][j];
}
}
}
return sum;
}
算法6：Dijkstra
1）Dijkstra算法必须指定一个源点
2）生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步
4）源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
//1）Dijkstra算法必须指定一个源点
//2）生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
//3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步
//4）源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
public static HashMap<Point, Integer> dijkstra1(Point from) {
HashMap<Point, Integer> distanceMap = new HashMap<>();
if (from == null) {
return distanceMap;
}
HashSet<Point> set = new HashSet<>();
distanceMap.put(from, 0);
Point point = getMinDistanceUnselectedPoint(distanceMap, set);
while (point != null) {
int distance = distanceMap.get(point);
for (Edge edge : point.edges) {
Point to = edge.to;
if (!distanceMap.containsKey(to)) {
distanceMap.put(to, distance + edge.weight);
} else {
distanceMap.put(to, Math.min(distanceMap.get(to), distance + edge.weight));
}
}
set.add(point);
point = getMinDistanceUnselectedPoint(distanceMap, set);
}
return distanceMap;
}
private static Point getMinDistanceUnselectedPoint(HashMap<Point, Integer> distanceMap, HashSet<Point> selected) {
int minDistance = Integer.MAX_VALUE;
Point point = null;
for (Map.Entry<Point, Integer> entry : distanceMap.entrySet()) {
Point cur = entry.getKey();
int distance = entry.getValue();
if (!selected.contains(cur) && distance < minDistance) {
point = cur;
minDistance = distance;
}
}
return point;
}
}
public static HashMap<Point, Integer> dijkstra2(Point from, int size) {
HashMap<Point, Integer> ans = new HashMap<>();
if (from == null) {
return ans;
}
PointHeap pointHeap = new PointHeap(size);
pointHeap.addOrUpdateOrIgnore(from, 0);
while (!pointHeap.isEmpty()) {
PointInfo pointInfo = pointHeap.pop();
Point cur = pointInfo.point;
int dis = pointInfo.distance;
cur.edges.forEach(edge -> pointHeap.addOrUpdateOrIgnore(edge.to, edge.weight + dis));
ans.put(cur, dis);
}
return ans;
}
private static class PointInfo {
Point point;
int distance;
public PointInfo(Point point, int distance) {
this.point = point;
this.distance = distance;
}
}
private static class PointHeap {
private Point[] heap;
private HashMap<Point, Integer> indexMap;
private HashMap<Point, Integer> distanceMap;
int size;
public PointHeap(int size) {
heap = new Point[size];
indexMap = new HashMap<>(size);
distanceMap = new HashMap<>(size);
this.size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void addOrUpdateOrIgnore(Point point, int distance) {
if (!isEntered(point)) {
heap[size] = point;
indexMap.put(point, size);
distanceMap.put(point, distance);
heapInsert(point, size++);
} else if (inHeap(point)) {
distanceMap.put(point, Math.min(distanceMap.get(point), distance));
heapInsert(point, indexMap.get(point));
}
}
public PointInfo pop() {
PointInfo info = new PointInfo(heap[0], distanceMap.get(heap[0]));
swap(0, size - 1);
indexMap.put(heap[size - 1], -1);
distanceMap.remove(heap[size - 1]);
heap[size - 1] = null;
heapfy(0, --size);
return info;
}
private boolean inHeap(Point point) {
return isEntered(point) && indexMap.get(point) != -1;
}
private boolean isEntered(Point point) {
return indexMap.containsKey(point);
}
private void heapInsert(Point point, int index) {
while (distanceMap.get(heap[(index - 1) / 2]) > distanceMap.get(heap[index])) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private void heapfy(int index, int size) {
int left = 2 * index + 1;
while (left < size) {
int small = left + 1 < size && distanceMap.get(heap[left + 1]) < distanceMap.get(heap[left]) ? left + 1 : left;
small = distanceMap.get(heap[small]) < distanceMap.get(heap[index]) ? small : index;
if (small == index) {
break;
}
swap(small, index);
index = small;
left = 2 * index + 1;
}
}
private void swap(int i, int j) {
Point pointI = heap[i];
Point pointJ = heap[j];
heap[i] = pointJ;
heap[j] = pointI;
indexMap.put(pointI, j);
indexMap.put(pointJ, i);
}
}
若有收获，就点个赞吧
0 人点赞
