数据结构与算法之图的基本实现
2020-04-29 本文已影响0人
Peakmain
图
- 图由顶点(vertex)和边(edge)组成，通常表示为G=(V,E)
图的分类
有向图
有明确方向的图
image.png
- 有向无环图(DAG)
如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图
image.png
-
出度、入度
1、出度、入度适用于有向图
2、 度：某个顶点的度就是依附于该顶点的个数
3、 出度：表示该顶点为起点的边数量(其实看箭头就可以了，箭头出去就是出度)
4、入度：表示该顶点为终点的边的数量(箭头进来的)
image.png
比如上图：7的入度是3，出度是2
无向图
-
无向图的边是无向的
image.png
其实无向图类似与下面的有向图
image.png
混合图
可能是有向，也可能是无向
image.png
简单图和多重图
-
平行边：
1、无向图中，关联一对顶点的无向边如果多于1条，则称为平行边(如下图的三条线)
image.png
2、有向图中，关联一对顶点的有向边如果多于一条，并且它们的方向相同，则称为平行边
image.png
-
简单图
没有平行边也没有自环的图
image.png
-
多重图
有平行边或者有自环的图 -
无向完全图
性质1、任意两个顶点之间都存在边
性质2、n个顶点的无向完全图有n(n-1)/2个边
性质2推导:比如4个顶点
image.png
首先6连边的结果:一共3条边
image.png
然后8连边的结果：一共2条，最后3连边一共1条结果
image.png
所以边数一共是：3+2+1=4*3/2=n(n-1)/2
-
有向完全图
任意两个顶点之间都存在方向相反的两条边
image.png
-
有权图
有权图的边可以有权值
image.png
图的实现方案
图有两种常见的实现方案
1、领接矩阵
2、领接表
邻接矩阵的存储方式
一维数组存放顶点信息
二维数组存放边信息
image.png
v1->v0有边所以写1，v0->v1没有边，所有写0
弊端：我们会发现画的红色斜线，上下对称，所以领接矩阵比较浪费内存
-
领接矩阵有权图
image.png
领接表
-
无向图的领接表
image.png
-
有向图的领接表
image.png
图的基础接口定义
public interface Graph<V, E> {
/**
* 边得大小
*/
int edgesSize();
/**
* 顶点的大小
*/
int verticesSize();
/**
* 添加顶点
* @param v 顶点
*/
void addVertext(V v);
/**
* 添加边
* @param from 入度顶点
* @param to 出度顶点
*/
void addEdge(V from, V to);
/**
* 添加边
* @param from 入度顶点
* @param to 出度顶点
* @param weight 权重
*/
void addEdge(V from, V to, E weight);
/**
* 移除顶点
* @param v 顶点
*/
void removeVertex(V v);
/**
* 移除边
* @param from 入度顶点
* @param to 出度顶点
*/
void removeEdge(V from, V to);
}
图的基础实现
image.png
顶点的定义
- 每个顶点有三个元素：1、值value、2、该顶点出度的集合、3、该顶点的入度的集合
- 因为我们在添加顶点的时候，需要判断当前顶点是否已经被添加了，那么判断两个顶点是否相等，我们需要重新实现equals和hashCode
- 根据value来判断是否是同一个顶点
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 v) {
this.value = v;
}
@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 ? "" : value.toString();
}
}
边的定义
- 边是两个顶点连接而成的，那么顶点肯定需要两个(from 和to)，从哪个顶点到哪个顶点
- 边可能有权重
- 添加边的时候需要判断边是否相等，判断依旧需要重写hashCode和equals
- hashCode等于from顶点和to顶点的hash相加
- equals需要判断两个边的from是否一样，以及两个边的to是否一样
private static class Edge<V, E> {
Vertex<V, E> from;
Vertex<V, E> to;
E weight;
public Edge(Vertex<V, E> fromVertex, Vertex<V, E> toVertex) {
this.from = fromVertex;
this.to = toVertex;
}
@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);
}
@Override
public int hashCode() {
return 31 * from.hashCode() + to.hashCode();
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
添加顶点
- 首先需要有个Map集合，key是值，value是边
- 判断map是否有该值的边，有就直接返回，没有需要将值添加到map中
private Map<V, Vertex<V, E>> vertices = new HashMap<>();
@Override
public int verticesSize() {
return vertices.size();
}
/**
* 添加顶点
*/
@Override
public void addVertext(V v) {
if (vertices.containsKey(v)) return;
vertices.put(v, new Vertex<>(v));
}
添加边
- 需要一个set集合存放所有的边
- map中判断from是否有边，没有就创建，并添加到map中
- map中判断to是否有边，没有就创建，并添加到map中
-
根据from和to创建一个新的边edge
image.png
如上图的v1和v2,假设现在的from是v1,to是v2,
- 删除v1中的出度的边，如果成功，继续删除v2的入度，并将边的set集合也已要移除该边
- 然后我们再设置v1的出度等于新创建的边edge，v2的入度等于新创建的边edge
private Set<Edge<V, E>> edges = new HashSet<>();
@Override
public int edgesSize() {
return edges.size();
}
/**
* 添加边
* @param from 入度顶点
* @param to 出度顶点
*/
@Override
public void addEdge(V from, V to) {
addEdge(from, to, null);
}
/**
* 添加边
* @param from 入度顶点
* @param to 出度顶点
* @param weight 权重
*/
@Override
public void addEdge(V from, V to, E weight) {
Vertex<V, E> fromVertex = vertices.get(from);
if (fromVertex == null) {
fromVertex = new Vertex<>(from);
vertices.put(from, fromVertex);
}
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;
if (fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
fromVertex.outEdges.add(edge);
toVertex.inEdges.add(edge);
edges.add(edge);
}
删除某边
image.png
- 比如我们要删除v2->v0这条边，from是v2,to是v0
- 从map中根据from和to获取边，如果没有直接返回
- 根据from和to创建新边，v2的出度也就是from的出度要移除
- v0的入度删除
- 整个边的集合删除
@Override
public void removeEdge(V from, V to) {
Vertex<V, E> fromVertex = vertices.get(from);
if (fromVertex == null) return;
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);
}
}
删除某个顶点
image.png
- 比如删除v2这个顶点，需要删除所有的入度和出度
- 根据顶点获取边，如果没有则直接返回
- 遍历该边的所有出度，删除该边的to的入度，当前遍历的边删除，边的集合也删除该边。如上图，v2的出度有v0和v3，那该边的to边是v0和v3，删除v0和v3的入度，再删除遍历到边
- 该边的入度以上步相似
@Override
public void removeVertex(V v) {
Vertex<V, E> vertex = vertices.remove(v);
if (vertex == null) return;
//出度 1->2->3 移除2
Iterator<Edge<V, E>> outIterator = vertex.outEdges.iterator();
while (outIterator.hasNext()) {
Edge<V, E> edge = outIterator.next();
edge.to.inEdges.remove(edge);
//当前遍历的边删除
outIterator.remove();
edges.remove(edge);
}
Iterator<Edge<V, E>> inIterator = vertex.inEdges.iterator();
while (inIterator.hasNext()) {
Edge<V, E> edge = inIterator.next();
edge.from.outEdges.remove(edge);
// 当前遍历的边删除
inIterator.remove();
edges.remove(edge);
}
}
测试
打印工具类封装
public void print() {
vertices.forEach((V v, Vertex<V, E> vertex) -> {
System.out.print("\t\t\t|-----");
System.out.print("入度:");
System.out.print(vertex.inEdges);
System.out.println("\t\t\t|");
System.out.print("\t\t\t|");
System.out.print("\n[顶点]:");
System.out.println(v +"--->");
System.out.println("\t\t\t|");
System.out.println("\t\t\t|");
System.out.print("\t\t\t|-----");
System.out.print("出度:");
System.out.println(vertex.outEdges);
System.out.println("\n\n");
});
System.out.println("-----------[边]-----------");
edges.forEach((Edge<V, E> edge) -> {
System.out.println(edge);
});
}
main函数中有向图
ListGraph<String, Integer> graph = new ListGraph<>();
graph.addEdge("V1", "V0", 9);
graph.addEdge("V1", "V2", 3);
graph.addEdge("V2", "V0", 2);
graph.addEdge("V2", "V3", 5);
graph.addEdge("V3", "V4", 1);
graph.addEdge("V0", "V4", 6);
graph.addEdge("V1", "V0", 12);
graph.print();
部分截图.png
移除v2->v0这条边
graph.removeEdge("V2","V0");
image.png
移除顶点
graph.removeVertex("V2");
image.png
image.png
无向图
ListGraph<String, Integer> graph = new ListGraph<>();
graph.addEdge("V0", "V1");
graph.addEdge("V1", "V0");
graph.addEdge("V0", "V2");
graph.addEdge("V2", "V0");
graph.addEdge("V0", "V3");
graph.addEdge("V3", "V0");
graph.addEdge("V1", "V2");
graph.addEdge("V2", "V1");
graph.addEdge("V2", "V3");
graph.addEdge("V3", "V2");
graph.print();
