数据结构图代码实现、BFS、DFS、拓扑排序
一个写湿的程序猿
帮助1人
图的基础代码
图的基础接口
public interface Graph<V, E> {
int edgesSize(); // 边的数量
int verticesSize(); // 顶点数量
void addVertex(V v); // 添加顶点
void addEdge(V from, V to); // 添加边
void addEdge(V from, V to, E weight);// 添加边
void removeVertex(V v); // 删除顶点
void removeEdge(V from, V to); // 删除边
interface vertexVisitor<V>{
boolean visit(V v);
}
}
顶点 Vertex
/**
* 顶点
*/
private static class Vertex<V, E> {
V value;
Set<Edge<V, E>> inEdges = new HashSet<>(); // 进来的边
Set<Edge<V, E>> outEdges = new HashSet<>(); // 出去的边
public Vertex(V value){
this.value = value;
}
// 两个顶点如何判断相等？
// 只要顶点的值相等，就认为两个顶点相等
@Override
public boolean equals(Object obj) {
return Objects.equals(value, ((Vertex<V, E>)obj).value);
}
@Override
public int hashCode() {
return value == null ? 0 : value.hashCode();
}
@Override
public String toString() {
return value == null ? "null" : value.toString();
}
}
边 Edge
/*
* 边
*/
private static class Edge<V, E> {
Vertex<V, E> from; // 出发点
Vertex<V, E> to; // 到达点
E weight; // 权值
public Edge(Vertex<V, E> from, Vertex<V, E> to) {
this.from = from;
this.to = to;
}
// 两条边如何判断相等？（有向图）
// 起点from和终点to顶点相等的边，就认为两条边相等
// 实际比较的是该边的from和to顶点
@Override
public boolean equals(Object obj) {
Edge<V, E> edge = (Edge<V, E>) obj;
return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
}
// 当对象要最作为hash表的key或者需要比较时，需要重写equals和hashCode
// equals相等的，hashCode一定要相等
@Override
public int hashCode() {
return from.hashCode() * 31 to.hashCode();
}
@Override
public String toString() {
return "Edge [from=" from ", to=" to ", weight=" weight "]";
}
}
一些稍微复杂的操作单独列出来，简单地操作直接从完整源码中查看即可。
添加边 addEdge
/**
* 添加无权值的边
*/
@Override
public void addEdge(V from, V to) {
addEdge(from, to, null);
}
/*
* 添加有权值的边
*/
@Override
public void addEdge(V from, V to, E weight) {
// 根据传入的参数from找到出发点，如果不存在则创建，并添加到顶点集合里
Vertex<V, E> fromVertex = vertices.get(from);
if(fromVertex == null){
fromVertex = new Vertex<>(from);
vertices.put(from, fromVertex);
}
// 根据传入的参数to找到终点,如果不存在则创建，并添加到顶点集合里
Vertex<V, E> toVertex = vertices.get(to);
if(toVertex == null){
toVertex = new Vertex<>(to);
vertices.put(to, toVertex);
}
// 根据出发点与终点,创建边
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
edge.weight = weight; // 有权值则加上权值,无权值则为null
// 不管原来是否存在对应的边,都先删除此边,再添加进去
if(fromVertex.outEdges.remove(edge)){
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
fromVertex.outEdges.add(edge);
toVertex.inEdges.add(edge);
edges.add(edge);
}
删除边 removeEdge
/*
* 删除边
*/
@Override
public void removeEdge(V from, V to) {
// 根据传入的from获得起点,不存在则不需要删除
Vertex<V, E> fromVertex = vertices.get(from);
if(fromVertex == null) return;
// 根据传入的to找到终点,不存在则不需要删除
Vertex<V, E> toVertex = vertices.get(to);
if(toVertex == null) return;
// 根据起点和终点获得边,然后删除
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
if(fromVertex.outEdges.remove(edge)){
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
}
添加点 addVertex
/*
* 添加顶点
*/
@Override
public void addVertex(V v) {
// 如果对应的顶点存在，直接return，
// 若不存在则创建对应的顶点，并添加到顶点集合里
if(vertices.containsKey(v)) return;
vertices.put(v, new Vertex<>(v));
}
删除点 removeVertex
/*
* 删除点
*/
@Override
public void removeVertex(V v) {
// 根据传入的值找到点并删除,不存在则不做操作
Vertex<V, E> vertex = vertices.remove(v);
if(vertex == null) return;
// 迭代器遍历集合vertex.outEdges, 删除所有从该顶点出度的边
Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator();
for (iterator; iterator.hasNext(); ) {
Edge<V, E> edge = iterator.next(); // 遍历到的该点出去的边
edge.to.inEdges.remove(edge);// 获取终点进入的边,并从中删除遍历到的边
iterator.remove(); // 将当前遍历到的元素edge从集合vertex.outEdges中删掉
edges.remove(edge);
}
// 迭代器遍历集合vertex.inEdges, 删除所有进入该点的边
Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator();
for (iterator; iterator.hasNext(); ) {
Edge<V, E> edge = iterator.next(); // 遍历到的进入该点的边
edge.from.outEdges.remove(edge); // 获取起点出去的边,并从中删除遍历到的边
iterator.remove(); // 将当前遍历到的元素edge从集合vertex.inEdges中删掉
edges.remove(edge);
}
}
完整源码
/**
* 邻接表实现图
*/
@SuppressWarnings("unchecked")
public class ListGraph<V, E> implements Graph<V, E> {
// 传入的V与顶点类Vertex的映射
private Map<V, Vertex<V, E>> vertices = new HashMap<>();
// 边的Set集合
private Set<Edge<V, E>> edges = new HashSet<>();
/**
* 顶点（内部类，不对外开放）
*/
private static class Vertex<V, E> {
V value;
Set<Edge<V, E>> inEdges = new HashSet<>(); // 入度的边
Set<Edge<V, E>> outEdges = new HashSet<>(); // 出度的边
public Vertex(V value){
this.value = value;
}
// 两个顶点如何判断相等？
// 只要顶点的值相等，就认为两个顶点相等
@Override
public boolean equals(Object obj) {
return Objects.equals(value, ((Vertex<V, E>)obj).value);
}
@Override
public int hashCode() {
return value == null ? 0 : value.hashCode();
}
@Override
public String toString() {
return value == null ? "null" : value.toString();
}
}
/*
* 边（内部类，不对外开放）
*/
private static class Edge<V, E> {
Vertex<V, E> from; // 出发点
Vertex<V, E> to; // 到达点
E weight; // 权值
public Edge(Vertex<V, E> from, Vertex<V, E> to) {
this.from = from;
this.to = to;
}
// 两条边如何判断相等？（有向图）
// 起点from和终点to顶点相等的边，就认为两条边相等
// 实际比较的是该边的from和to顶点
@Override
public boolean equals(Object obj) {
Edge<V, E> edge = (Edge<V, E>) obj;
return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
}
// 当对象要最作为hash表的key或者需要比较时，需要重写equals和hashCode
// equals相等的，hashCode一定要相等
@Override
public int hashCode() {
return from.hashCode() * 31 to.hashCode();
}
@Override
public String toString() {
return "Edge [from=" from ", to=" to ", weight=" weight "]";
}
}
public void print(){
System.out.println("[顶点]-------------------");
vertices.forEach((V v, Vertex<V, E> vertex) -> {
System.out.println(v);
System.out.println("out-----------");
System.out.println(vertex.outEdges);
System.out.println("int-----------");
System.out.println(vertex.inEdges);
});
System.out.println("[边]-------------------");
edges.forEach((Edge<V, E> edge) -> {
System.out.println(edge);
});
}
/*
* 该图对应的总边数
*/
@Override
public int edgesSize() {
return edges.size();
}
/*
* 该图对应的总顶点数
*/
@Override
public int verticesSize() {
return vertices.size();
}
/*
* 添加顶点
*/
@Override
public void addVertex(V v) {
// 如果对应的顶点存在，直接return，
// 若不存在则创建对应的顶点，并添加到顶点集合里
if(vertices.containsKey(v)) return;
vertices.put(v, new Vertex<>(v));
}
/**
* 添加无权值的边
*/
@Override
public void addEdge(V from, V to) {
addEdge(from, to, null);
}
/**
* 添加有权值的边
*/
@Override
public void addEdge(V from, V to, E weight) {
// 根据传入的参数from找到起点,如果不存在则创建，并添加到顶点集合里
Vertex<V, E> fromVertex = vertices.get(from);
if(fromVertex == null){
fromVertex = new Vertex<>(from);
vertices.put(from, fromVertex);
}
// 根据传入的参数to找到终点,如果不存在则创建，并添加到顶点集合里
Vertex<V, E> toVertex = vertices.get(to);
if(toVertex == null){
toVertex = new Vertex<>(to);
vertices.put(to, toVertex);
}
// 根据出发点与终点,创建边
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
edge.weight = weight; // 有权值则加上权值,无权值则为null
// 不管原来是否存在,都先删除此边,再添加进去
if(fromVertex.outEdges.remove(edge)){
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
fromVertex.outEdges.add(edge);
toVertex.inEdges.add(edge);
edges.add(edge);
}
/*
* 删除顶点
*/
@Override
public void removeVertex(V v) {
// 根据传入的值找到点并删除,不存在则不做操作
Vertex<V, E> vertex = vertices.remove(v);
if(vertex == null) return;
// 迭代器遍历集合vertex.outEdges, 删除所有从该点出去的边
Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator();
for (iterator; iterator.hasNext();) {
Edge<V, E> edge = iterator.next(); // 遍历到的该点出去的边
edge.to.inEdges.remove(edge);// 获取终点进入的边,并从中删除遍历到的边
iterator.remove(); // 将当前遍历到的元素edge从集合vertex.outEdges中删掉
edges.remove(edge);
}
// 迭代器遍历集合vertex.inEdges, 删除所有进入该点的边
Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator();
for (iterator; iterator.hasNext(); ) {
Edge<V, E> edge = iterator.next(); // 遍历到的进入该点的边
edge.from.outEdges.remove(edge); // 获取起点出去的边,并从中删除遍历到的边
iterator.remove(); // 将当前遍历到的元素edge从集合vertex.inEdges中删掉
edges.remove(edge);
}
}
/*
* 删除边
*/
@Override
public void removeEdge(V from, V to) {
// 根据传入的from获得起点,不存在则不需要删除
Vertex<V, E> fromVertex = vertices.get(from);
if(fromVertex == null) return;
// 根据传入的to找到终点,不存在则不需要删除
Vertex<V, E> toVertex = vertices.get(to);
if(toVertex == null) return;
// 根据起点和终点获得边,然后删除
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
if(fromVertex.outEdges.remove(edge)){
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
}
}
图的遍历
图的遍历
从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次
图有2种常见的遍历方式（有向图、无向图都适用）
-
广度优先搜索（
Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索。 -
深度优先搜索（
Depth First Search，DFS）
发明“深度优先搜索”算法的2位科学家在1986年共同获得计算机领域的最高奖：图灵奖。
在接口中增加 bfs 与 dfs 方法。
广度优先搜索（Breadth First Search）
之前所学的二叉树层序遍历就是一种广度优先搜索
注：BFS结果不唯一，因为顶点之间没有顺序。
可以类比二叉树的层序遍历，
-
从某个顶点出发，可以认为这个顶点是在第一层，
-
然后往下找，与这个顶点一条线相连的其它顶点，就可以认为在第二次，
-
以此类推，与第二层一条线相连的其它顶点，可以认为在第三次
举个栗子：
-
例如从
A顶点出发，那么可以认为A顶点在第一次， -
与第一层顶点一条线相连的
B、F顶点，在第二次， -
继续找，与B、F顶点一条线相连的，
C、I、G、E顶点，在第三次， -
与第三次顶点一条线相连的，
D、H顶点，就在第四层
思路：
从某个顶点开始，将它可以到达的点放入队列，如果已经访问过则跳过，然后从队列中取出点重复该过程。
-
第一层：假设从顶点A开始，它可以到达B、F，则将
A弹出，将B、F入队。
此时队列中元素 [B、F]，B、F为第二层，弹出A为第一层 -
第二层：队头B出队，B可以到达C、I、G，则将
B弹出，将C、I、G入队。
此时队列中元素 [F、C、I、G]，C、I、G为第三层，弹出B为第二层 -
第二层：队头F出队，F可以到达G、E，则将
F弹出，但G已访问过，将E入队。
此时队列中元素 [C、I、G、E]，C、I、G、E为第三层，弹出F为第二层 -
第三层：队头C出队，C可以到达I、D，弹出
C，但I已访问过，将D入队。
此时队列中元素 [I、G、E、D]，D为第四层，弹出C为第三层 -
第三层：队头I出队，I可以到达D，弹出
I，但D已访问过，不执行操作。
此时队列中元素 [G、E、D]，D为第四层，弹出I为第三层 -
第三层：队头G出队，G可以到达D、H，弹出
G，但D已访问过，将H入队。
此时队列中元素 [E、D、H]，D，H为第四层，弹出G为第三层 -
第三层：队头E出队，E可以到达D、H、F，弹出
E，都访问过，不执行操作。
此时队列中元素 [D、H]，D，H为第四层，弹出E为第三层 -
第四层：队头D出队，D可以到达C、H、E，弹出
D，都访问过，不执行操作。
此时队列中元素 [H]，弹出D为第四层 -
第四层：队头H出队，H可以到达D、G、E，弹出
H，都访问过，不执行操作。
此时队列中元素 []，弹出H为第四层 -
队列为空，广度优先搜索结束。
所以遍历结果：
-
第一次：A
-
第二次：B、F
-
第三次：C、I、G、E
-
第四次：D、H
/**
* 广度优先搜索BFS
*/
public void bfs(V begin) {
// 根据传入的值begin找到顶点
Vertex<V, E> beginVertex = vertices.get(begin);
if(beginVertex == null) return; // 该顶点不存在,不做操作
// 存放已经访问过的节点
Set<Vertex<V, E>> visitedVertices = new HashSet<>();
Queue<Vertex<V, E>> queue = new LinkedList<>();
queue.offer(beginVertex); // 元素入队
visitedVertices.add(beginVertex);
// 思路参考二叉树层次遍历,队列存放每一层的顶点,用集合记录已经访问过的点
while(!queue.isEmpty()){
Vertex<V, E> vertex = queue.poll(); // 队列中取出一个顶点
System.out.println(vertex.value)
// 遍历[队列中取出的顶点]的出度的边,将[这些边的终点]入队,并且标记为已经访问过
for(Edge<V, E> edge : vertex.outEdges){
// 如果集合中已经记录该顶点,说明已经访问过,跳过进行下一轮
if(visitedVertices.contains(edge.to)) continue;
queue.offer(edge.to);
visitedVertices.add(edge.to);
}
}
}
深度优先搜索（Depth First Search）
之前所学的二叉树前序遍历就是一种深度优先搜索。
注：DFS结果不唯一，因为顶点之间没有顺序。
递归实现
/**
* 递归实现深度优先搜索DFS
*/
public void dfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin); // 根据传入的值获取顶点
if (beginVertex == null) return; // 顶点不存在则不执行操作
dfs(beginVertex, new HashSet<>()); // 传入的集合,用来记录访问过的顶点
}
private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> vistedVertices){
System.out.println(vertex.value);
vistedVertices.add(vertex);
for(Edge<V, E> edge : vertex.outEdges){
if(vistedVertices.contains(edge.to)) continue;
dfs(edge.to, vistedVertices);
}
}
非递归实现
弹出一个顶点的时候
- 从outEdges中选择一条边
- 将该边的from、to顶点按照顺序入栈（先from再to）
- 打印该边的to
- 将to加到已经访问的集合中
/**
* 非递归实现深度优先搜索DFS
*/
public void dfs(V begin){
Vertex<V, E> beginVertex = vertices.get(begin);
if(begin == null) return;
// 访问过的顶点集合set
Set<Vertex<V, E>> visitedVertices = new HashSet<>();
Stack<Vertex<V, E>> stack = new Stack<>();
stack.push(beginVertex); // 先访问起点
visitedVertices.add(beginVertex); // 将访问过的顶点加入集合
System.out.println(beginVertex.value);
while(!stack.isEmpty()){
Vertex<V, E> vertex = stack.pop();
// 找出该顶点的出度边，选择一条边一直走到低
for(Edge<V, E> edge : vertex.outEdges){
// 判断to顶点是否访问过
if(visitedVertices.contains(edge.to)) continue;
// 将该边的form、to顶点入栈
stack.push(edge.from);
stack.push(edge.to);
visitedVertices.add(edge.to);
System.out.println(edge.to.value);
break;
}
}
}
AOV网（Activity On Vertex Network）
一项大的工程常被分为多个小的子工
- 子工程之间可能存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始。
在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，子工程被称为活动（Activity）
- 以顶点表示活动、有向边表示活动之间的先后关系，这样的图简称为 AOV 网。
标准的AOV网必须是一个有向无环图（Directed Acyclic Graph，简称 DAG）
拓扑排序（Topological Sort）
前驱活动：有向边起点的活动称为终点的前驱活动（C、B、D就是E的前驱活动）
- 只有当一个活动的前驱全部都完成后，这个活动才能进行
后继活动：有向边终点的活动称为起点的后继活动（E就是C、B、D的后继活动）
什么是拓扑排序？
将AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面
比如上图的拓扑排序结果是：A、B、C、D、E、F 或者A、B、D、C、E、F （结果并不一定是唯一的）
拓扑排序 - 思路和实现
可以使用卡恩算法（Kahn于1962年提出）完成拓扑排序。
假设 L 是存放拓扑排序结果的列表：
-
把所有入度为 0 的顶点放入 L 中，然后把这些顶点从图中去掉
-
重复操作 ①，直到找不到入度为 0 的顶点
如果此时 L 中的元素个数和顶点总数相同，说明拓扑排序完成
如果此时 L 中的元素个数少于顶点总数，说明原图中存在环，无法进行拓扑排序
注：这样做会破坏原本图的结构，所以为了保留原有的图结构，可以对算法进行改造
采用Map来记录，每个顶点的入度数，
/**
* 拓扑排序
*/
public List<V> topologicalSort() {
// 存放结果的列表
List<V> list = new ArrayList<>();
// 存放入度为0的节点（过度）
Queue<Vertex<V, E>> queue = new LinkedList<>();
// 记录每个顶点的入度数
Map<Vertex<V, E>, Integer> ins = new HashMap<>();
// 初始化（将入度为0的节点放入队列）
vertices.forEach(
(V v, Vertex<V, E> vertex) -> {
int indegree = vertex.inEdges.size(); // 入度数
if(indegree == 0) { // 入度为0，放入队列
queue.offer(vertex);
} else { // 入度不为0，用map记录它的入度数
ins.put(vertex, indegree);
}
}
);
while(!queue.isEmpty()){ // 从队列中取节点
Vertex<V, E> vertex = queue.poll();
list.add(vertex.value); // 放入返回结果列表中
// 遍历该节点的出度边，找到对应的to节点
for (Edge<V, E> edge : vertex.outEdges){
// 队列中取出该节点对应的to节点，的入度数
// 并且入度数-1，因为from节点已经入结果集，相当于从图中删除
int toIndegree = ins.get(edge.to) - 1;
if(toIndegree == 0) { // 入度为0，放入队列
queue.offer(edge.to);
} else { // 入度不为0，用map记录，更新它的入度数
ins.put(edge.to, toIndegree);
}
}
}
return list;
}
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhgfckkc
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01
