数据结构图代码实现、BFS、DFS、拓扑排序
图的基础代码
图的基础接口
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