wap网站生成,旅游去过的地方可做标识网站,网络公司举报找哪个部门,网站域名备案和icp备案一样么图
前言
本篇作为图的基础概念篇#xff0c; 了解图的离散数学定义#xff0c; 图的分类#xff0c; 图模型解决的问题#xff08;图的应用#xff09;#xff0c; 图的相关算法#xff08;仅仅介绍#xff0c;具体不在此篇展开#xff09;。 学习基本路线#xff…图
前言
本篇作为图的基础概念篇 了解图的离散数学定义 图的分类 图模型解决的问题图的应用 图的相关算法仅仅介绍具体不在此篇展开。 学习基本路线 学习离散数学的图章节。对图有宏观的把握。从代码上 完成图的表示。 学习深度优先搜索和广度优先搜索。进一步学习图的其它算法 比如单源最短路径 求解图的连通分量 最小生成树算法等等 还可以求解离散数学的其它问题如二分图 欧拉图 哈密顿图等等。学习图的算法可以加深对离散数学在计算机科学的理解。 离散数学这门学科本身就广泛应用于各大学科 并非只是对计算机科学如此。
引入
图是由顶点和连接顶点的边构成的离散结构。 根据图中的边是否有方向 相同顶点对之间是否有多条边相连以及是否允许存在自环 图的定义 G ( V , E ) G(V,E) G(V,E) 由顶点或结点的非空集 V V V和边集 E E E构成 每条边有一个或两个顶点与它相连 这样的顶点与它相连 该顶点称为边的端点 。边连接它的端点。 V − v e r t e x V-vertex V−vertex图中的元素,顶点或者结点。 E − e d g e E-edge E−edge连接一个或者两个端点。 E d g e ⊆ V × V Edge\subseteq V\times V Edge⊆V×V:描述了是边的顶点的二元集. ∣ E ∣ |E| ∣E∣:边的条数. ∣ V ∣ |V| ∣V∣:顶点个数. 考虑有限图:顶点集和边集为有限集的图称为有限图。
重点-简单图:
No self loops: 图中的顶点不能有连接到自身的边,不能有自环的情况.Every edge is distinct: 不能存在相同的边. 针对无向图:每对顶点只有一条边. 针对有向图:每对顶点同方向的边唯一. 不重点考虑多重图即存在不同边连接一对相同的顶点。 不考虑自环现象即边关联的两个顶点是同一个顶点。 图的分类 有向图与无向图. 对 v , u v,u v,u 无向图:边被描述为顶点的无序二元集:{v,u},说明了 v v v, u u u两顶点之间有一条边.无序性:含义是 {u,v} {v,u} . 有向图:边被表示为顶点的有序二元集:(v,u),说明了 v v v, u u u有一条顶点v到u的边.有序性:含义是 (u,v) 和 (v,u) 是两条不同的边 无向图的边是无序的二元对而有向图的边是有序的二元对。
有向图
定义: 有向图 G ( V , E ) G(V,E) G(V,E)由一个非空顶点集 V V V和一个有向边称为弧集 E E E组成。 每条有向边与一个有序点对相关联。有序对 ( u , v ) (u, v) (u,v)相关联的有向边开始于 u u u、结束于 v v v。 简单有向图简单图的基础上赋予方向就是简单有向图。
其它图的讨论
混合图既包含有向边和无向边的图称为无向图。 实际写代码时混合图和无向图均可以当作有向图无向边当作两条对立的有向边。
多重图即允许两顶点之间存在多条边的图。 自环自环是指一条边的起点和终点是同一个节点。
图的术语和特殊类型的图
图的基本术语
图 (Graph): 由顶点 (Vertices) 和边 (Edges) 组成的数学结构用于表示对象之间的关系。顶点 (Vertex): 图中的基本单位通常表示一个对象。边 (Edge): 连接两个顶点的线表示它们之间的关系。邻接 (Adjacent): 如果两个顶点之间有边相连则称它们是邻接的。若两顶点 u u u和 v v v是无向图 G G G中的一条边 e e e的端点 则称两个顶点 u u u和 v v v G G G里邻接相邻。称边 e e e为关联顶点 u , v u,v u,v。或者叫做边 e e e连接 u u u , v ,v ,v。对于有向图假设是 u u u到 v v v的有向边那么称边e把 u u u邻接到 v v v或者称 v v v从 u u u邻接。简而言之 对于这条有向边只能说u邻接v,而v不邻接u。路径 (Path): 从一个顶点到另一个顶点的边的序列且没有重复的顶点。圈 (Cycle): 从一个顶点出发经过若干边后回到该顶点的路径且路径中的其他顶点都不重复。度 顶点的度(degree):跟顶点相连接的边的条数。 入度与出度:对于有向图一个顶点的入度是指以其为终点的边数 出度指以该顶点为起点的边数。 反应了度和边数的关系。 图的度: 对于无向图 ∀ v ∈ V , ∑ d e g r e e ( v ) 2 ∣ E ∣ \forall v\in V, \sum degree(v) 2|E| ∀v∈V,∑degree(v)2∣E∣ 对于有向图 ∀ v ∈ V , ∑ d e g r e e ( v ) ∑ d e g r e e − ( v ) ∣ E ∣ \forall v\in V, \sum degree^(v) \sum degree^-(v) |E| ∀v∈V,∑degree(v)∑degree−(v)∣E∣ d e g r e e ( v ) : 有向图顶点的出度 . degree^(v):有向图顶点的出度. degree(v):有向图顶点的出度. d e g r e e − ( v ) degree^-(v) degree−(v)有向图顶点的入度。 顶点度为0的点是孤立点 顶点度为1的点是悬挂点
特殊类型的图汇总
无向图 (Undirected Graph): 边没有方向连接的两个顶点是对称的。有向图 (Directed Graph): 边有方向表示从一个顶点到另一个顶点的单向关系。加权图 (Weighted Graph): 每条边都有一个权重表示边的成本、距离等。简单图 (Simple Graph): 不允许有自环从一个顶点到自身的边和多重边相同的两个顶点之间有多条边。完全图 (Complete Graph): 图中每一对顶点之间都有边相连。树 (Tree): 一种特殊的无向图具有无圈的特性且任何两个顶点之间都有唯一的路径。森林 (Forest): 由多个树组成的图。连通图 (Connected Graph): 在无向图中任意两个顶点之间都存在路径在有向图中存在从一个顶点到另一个顶点的有向路径。强连通图 (Strongly Connected Graph): 在有向图中任意两个顶点之间都有有向路径。平面图 (Planar Graph): 可以在平面上绘制的图使得边的交叉最小。
关于连通图可达性路径等概念 结合后续算法题说明。
图的基本术语
顶点相邻若两顶点 u u u和 v v v是无向图 G G G中的一条边 e e e的端点 则称两个顶点 u u u和 v v v G G G里邻接相邻。称边 e e e为关联顶点 u , v u,v u,v。或者叫做边 e e e连接 u u u , v ,v ,v。邻居: G ( V , E ) G(V,E) G(V,E),顶点 v v v的所有相邻顶点的集合 记作 N ( v ) N(v) N(v)。其称为顶点的邻居。度 顶点的度(degree):跟顶点相连接的边的条数。 入度与出度:对于有向图一个顶点的入度是指以其为终点的边数 出度指以该顶点为起点的边数。 反应了度和边数的关系。 图的度: 对于无向图 ∀ v ∈ V , ∑ d e g r e e ( v ) 2 ∣ E ∣ \forall v\in V, \sum degree(v) 2|E| ∀v∈V,∑degree(v)2∣E∣ 对于有向图 ∀ v ∈ V , ∑ d e g r e e ( v ) ∑ d e g r e e − ( v ) ∣ E ∣ \forall v\in V, \sum degree^(v) \sum degree^-(v) |E| ∀v∈V,∑degree(v)∑degree−(v)∣E∣ d e g r e e ( v ) : 有向图顶点的出度 . degree^(v):有向图顶点的出度. degree(v):有向图顶点的出度. d e g r e e − ( v ) degree^-(v) degree−(v)有向图顶点的入度。 顶点度为0的点是孤立点 顶点度为1的点是悬挂点
两个定理
握手定理描述度与边数的关系。定义m图 G G G— 2 m ∑ v ϵ V d e g ( V ) 2m \sum_{v\epsilon V}deg(V) 2m∑vϵVdeg(V)无向图的有偶数个奇度顶点。
讨论简单图中无向图与有向图的边个数 无向图: ∣ E ∣ ≤ ( ∣ V ∣ 2 ) |E|\leq \begin{pmatrix} |V|\\ 2\\ \end{pmatrix} ∣E∣≤(∣V∣2) 有向图: ∣ E ∣ ≤ 2 ( ∣ V ∣ 2 ) |E|\leq2 \begin{pmatrix} |V|\\ 2\\ \end{pmatrix} ∣E∣≤2(∣V∣2) 解释:任取两顶点 v , u v,u v,u的排列数排列数 p ( n , 2 ) n × ( n − 1 ) 2 p(n, 2)\frac{n\times(n-1)}{2} p(n,2)2n×(n−1)。 这是最大值,因为可能并非所有两顶点都有边. 用大 O O O表示法: ( ∣ V ∣ 2 ) O ( ∣ V ∣ 2 ) \begin{pmatrix} |V|\\ 2\\ \end{pmatrix}O(|V|^2) (∣V∣2)O(∣V∣2)
图的表示
关于图 标准的两种标准表示方法 一种表示将图作为邻接链表的组合 另一种将图作为邻接矩阵表示。 两种方法均可以表示无向图和有向图 更准确地可以表示混合图。
本篇实现偏向于邻接表是图比较通用的写法。
图的个人通用实现
由前面图的定义 我们可以给出图的代码实现。 个人习惯用哈希表存储顶点和边 因为更符合数学上集合的概念。 其次 哈希表可以快速查询边或者顶点是否属于该图 且Java中的HashMap,HashSet存储的是不重复的元素十分便利。
以下图适用于纯无向图纯有向图混合图 混合图 多重图 存在自环的图。 不过其仍旧是有限图 实际工程上也不存在无限图的情况。
前置准备
编程语言Java 创建一个package graph, 创建三个.java文件 每个文件各有一个公共类 分别是Graph,Node,Edge。
Graph类
Graph,包含点集和边集。 很符合数学中的定义 以下是基础版本的描述。
package Graph; import java.util.HashMap;
import java.util.HashSet; public class GraphV { /*将顶点按顺序编号 点集*/ public HashMapInteger, NodeV nodes; //存储边集 public HashSetEdgeV edges; //构造函数 public Graph() { nodes new HashMapInteger, NodeV(); edges new HashSetEdgeV(); }
}public HashMapInteger, NodeV nodes; 将顶点用整数编号 结合现实每座城市都有唯一标识的编号处理。 //判断图是否为空集
public boolean isEmpty() { return nodes.isEmpty();
}
//获取顶点数量
public int size() { return nodes.size();
}
//获取边的数量
public int sizeOfEdges(){ return edges.size();
}尽管从数学角度上 图不为空集 但这里还是补上判空方法。
Node类单个结点自带的值value, 入度和出度邻接顶点 关联边数。 ![[Pasted image 20240928194111.png]]
顶点存储自己的编号后续对图的深拷贝有必要。顶点可以存储附加值value。 根据自己实际需求顶点存储入度和出度的值 入度: 指向某个节点的边的数量。它反映了有多少个其他节点指向该节点揭示该节点在图中的“吸引力”或“重要性”。 出度:从某个节点发出的边的数量。它表明该节点能够连接多少其他节点显示该节点的“影响力”或“传播能力”。 存储两者的信息可以反应该顶点的重要性 然后入度与出度这两个属性可以优化算法比方说后续的最短路径拓朴排序等等 它还可以反应图的结构特性识别某个特定节点孤立点集群等等。 顶点存储它直接可达的其它顶点直接邻居。 必要性方便动态操作比如我们要删去或者添加边时只需要对相关顶点的邻接列表操作即可 避免了整体上所有邻接关系的修改。 快速访问邻居的信息。 邻接列表相当于存储了直接邻居的地址 在后续处理遍历操作时异常便捷深度优先遍历和广度优先遍历。 很多算法依赖邻居关系 如最短路径求解连通分量问题。 5. 存储以该节点为起点的有向边。 高效访问节点附近的所有边 动态操作 操作边的增删查改时只需要局部性调整即可非常便捷。维护信息可以高效地维护其它属性。算法角度对依赖边的图算法有较大的便利实现。 package Graph; import java.util.ArrayList;
import java.util.Collections;
import java.util.List; /** * author AutumnWhisper * 回顾离散数学
*/
public class NodeV { int id;//编号 //顶点存储的值 V value; //入度 int in; //出度 int out; //直接可达结点表:顶点V的所有相邻顶点的集合.直接邻居 ArrayListNodeV nexts; //存储以该节点为起点的有向边。 ArrayListEdgeV edges; //初始化默认顶点为孤立点 public Node(int id,V value) { this.id id; this.value value; this.in 0; this.out 0; this.nexts new ArrayList(); this.edges new ArrayList(); } //获取当前顶点的编号 public int getId() { return id; } //获取当前节点存储的有效值 public V getValue() { return value; } //设置当前节点存储的值 public V setValue(V value) { V oldVal this.value; this.value value; return oldVal; } //获取入度 public int getIn(){ return in; } //获取出度 public int getOut(){ return out; }//提供当前顶点的邻接顶点列表不可修改 public ListNodeV getNexts(){ return Collections.unmodifiableList(nexts); } //提供以当前结点为顶点的关联边数。(不可修改) public ListEdgeV getEdges(){ return Collections.unmodifiableList(edges); } }Node类提供两个辅助方法来新增邻居和边 这只是辅助其它方法实现的。 /** * 当前节点新增邻居 * param neighbor 邻居 */
void addNeighbor(NodeV neighbor){ nexts.add(neighbor); this.out;//当前节点出度1 neighbor.in;//邻居入度1
} /** * 当前节点新增边 * param edge 边 */
void addEdge(EdgeV edge){ edges.add(edge);
}Edge类 边附带的权重有权图边的方向起点和终点。
package Graph; //顶点不依赖边 边依赖顶点
public class EdgeV { //权重 int weight; NodeV from;//起点 NodeV to;//终点 public Edge(int weight, NodeV from, NodeV to) { this.weight weight; this.from from; this.to to; } //----给包外提供的接口。 //获取权重 public int getWeight() { return weight; } //重新设置权重 public void setWeight(int weight) { this.weight weight; } //获取边的起点 public NodeV getFrom() { return from; } //设置边的起点 public void setFrom(NodeV from) { this.from from; } //获取边的终点 public NodeV getTo() { return to; } //设置边的终点 public void setTo(NodeV to) { this.to to; }
}基本操作
增加图中的边
通过图中增加一条边关联两个已有的顶点。 提取关键字已有顶点 这意味着我们不能无中生有造边 而是依赖与图中现有的一对顶点。
假设我们增加一条边 e e e, 使得原图中两个原本不相关联的两个顶点被连接起来。 新图 G e ( V , E ∪ { e } ) G e (V,E\cup \{e\}) Ge(V,E∪{e})
/** * * param from 起点 * param to 终点 * param weight 权重 * return 返回是否添加成功一个布尔值 */
public boolean addEdge(Integer from, Integer to, int weight) { NodeV fromNode nodes.get(from); NodeV toNode nodes.get(to); //保证节点的有效性即可。 if(fromNode ! null toNode ! null){ EdgeV edge new Edge(fromNode, toNode, weight); edges.add(edge);//边集新添一条边 //更新fromNode顶点的信息 fromNode.addNeighbor(toNode);//直接邻居加1 fromNode.addEdge(edge);//fromNode关联作起点的边数1 return true;//删除成功 } return false;//删除结点不存在
}你会发现该函数添加的是有向边。无向边怎么添加呢调转from 和 to调用两次addEdge函数。
/** * * param from 起点 * param to 终点 * param weight 权重 * return 返回是否添加成功一个布尔值 */
public boolean addEdge(Integer from, Integer to, int weight) { NodeV fromNode nodes.get(from); NodeV toNode nodes.get(to); //保证节点的有效性即可。 if(fromNode ! null toNode ! null){ EdgeV edge new Edge(fromNode, toNode, weight); edges.add(edge);//边集新添一条边 //更新fromNode顶点的信息 fromNode.addNeighbor(toNode);//直接邻居加1 fromNode.addEdge(edge);//fromNode关联作起点的边数1 return true;//删除成功 } return false;//删除结点不存在
} /** * * param from 起点 * param to 终点 * param weight 权重 * return 返回是否添加成功 返回一个布尔值 */
public boolean addEdgeDirect(Integer from, Integer to, int weight) { return addEdge(from, to, weight);//增加一条有向边。
}
/** * 添加一条无向边 实际等效两条有向边。 * param from 起点 * param to 终点 * param weight 权重 * return 返回是否添加成功 返回一个布尔值 */
public boolean addEdgeUnDirect(Integer from, Integer to,int weight) { return addEdge(from, to,weight) addEdge(to,from,weight);
}1. addEdge 方法
功能添加一条有向边。参数 from起点节点的ID。to终点节点的ID。weight边的权重。 返回值布尔值指示添加是否成功。逻辑 首先通过节点ID获取起点和终点节点。检查两个节点是否有效不为 null。创建新边并将其添加到边集中。更新起点节点的邻接关系和边信息。
2. addEdgeDirect 方法
功能直接调用 addEdge添加一条有向边。作用提供更直观的命名方便调用。
3. addEdgeUnDirect 方法
功能添加一条无向边。逻辑 通过调用 addEdge 方法添加两条有向边from 到 to 和 to 到 from实现无向边的效果。 返回值如果两个有向边都成功添加则返回 true否则返回 false。 。
可以自环吗 当然可以只需要传参时from to即可代码上允许这种情况发生。 多重图呢可以添加多重权重不同的边例如多次调用addEdge可以创造多条权值不同但方向起点终点相同的边。注意权值相同的边合并为1条。 你可能想吐槽一句edges不是HashSet吗它应该要去重啊 实际上这与hashcode方法和equal方法有关。HashSet会先调用hashcode方法如果哈希值相同然后调用equals方法只需要重写Edge类的equals方法即可。
//Edge.java
Override
public boolean equals(Object o){ if(this o) return true; if(o null || getClass() ! o.getClass()) return false; Edge? edge (Edge?) o; if(weight ! edge.weight) return false; if(!Objects.equals(from, edge.from)) return false; return Objects.equals(to, edge.to);
}只允许权值相同的多重边。
删除图中的边
/** * 适用 无权有向图;无权无向图需要调换参数调用两次。 * 默认删除fromId-toId这条有向边。 * removeDirect删除有向边 removeUnDirect删除无向边也适用单向边不过要耗时一些 * param fromId 起点编号 * param toId 终点编号 */
public void removeEdge(Integer fromId, Integer toId) { NodeV fromNode nodes.get(fromId); NodeV toNode nodes.get(toId); if (fromNode ! null toNode ! null) { IteratorEdgeV iterator edges.iterator(); while (iterator.hasNext()) { EdgeV edge iterator.next(); if (edge.from fromNode edge.to toNode) { iterator.remove(); // 安全地删除边 fromNode.edges.remove(edge); fromNode.out--; toNode.in--; break; // 找到并删除后可以退出循环 } } }
} /** * 该方法会删除所有指定起点与终点相同的边无视权重 * 适用带权有向图。无向图需要调换参数多调用一次 * param fromId * param toId */
public void removeEdgeAll(Integer fromId, Integer toId) { NodeV fromNode nodes.get(fromId); NodeV toNode nodes.get(toId); if (fromNode ! null toNode ! null) { IteratorEdgeV iterator edges.iterator(); while (iterator.hasNext()) { EdgeV edge iterator.next(); if (edge.from fromNode edge.to toNode) { iterator.remove(); // 安全地删除边 fromNode.edges.remove(edge); fromNode.out--; toNode.in--; } } }
} /** * 适用无权有向图。带权图允许多重边会随机干掉一条有向边。不带权的边唯一。 * 删除有向边 * param fromId 起点编号 * param toId 终点编号 */
public void removeEdgeDirect(Integer fromId, Integer toId){ removeEdge(fromId, toId);
}
/** * 适用无权无向图。带权图允许多重边会随机干掉一对无向边无视权重。不带权的边唯一。 * 删除无向边 内部会调用两次removeDirect函数。 * param fromId 起点编号 * param toId 终点编号 */
public void removeEdgeUnDirect(Integer fromId, Integer toId){ removeEdge(fromId, toId); removeEdge(toId, fromId);
} /** * * param fromId 起点编号 * param toId 终点编号 * param weight 权重 * return 返回满足的有向边 */
private EdgeV search(Integer fromId, Integer toId, int weight) { NodeV fromNode nodes.get(fromId); NodeV toNode nodes.get(toId); if (fromNode ! null toNode ! null) { IteratorEdgeV iterator edges.iterator(); while (iterator.hasNext()) { EdgeV edge iterator.next(); if (edge.from fromNode edge.to toNode edge.weight weight) { return edge; } } } return null;
}
/** * 适用带权有向图。 * 删除指定带权有向边如果存在。 * param fromId 起点编号 * param toId 终点编号 * param weight 权重 */
public void removeEdgeWithWeight(Integer fromId, Integer toId, int weight){ EdgeV edge search(fromId, toId, weight); if (edge ! null) { edges.remove(edge); nodes.get(fromId).out--; nodes.get(toId).in--; }
} /** * 适用带权无向图。 * 删除指定带权的无向边。 * param fromId 起点编号 * param toId 终点编号 * param weight 权重 */
public void removeEdgeWithWeightUnDirect(Integer fromId, Integer toId, int weight) { removeEdgeWithWeight(fromId, toId, weight); // 删除有向边 removeEdgeWithWeight(toId, fromId, weight); // 删除反向边
}增加图中的顶点
增加一个孤立点 后续要跟其它顶点邻接就用增加边的方法。
/* * 给定编号和值创建一个新顶点并加入到图中。 * 若编号重复 则添加失败。 * param id 编号 * param value 值 * return 返回一个布尔值添加成功了返回true。 */public boolean addNode(Integer id, V value) { if (!nodes.containsKey(id)) { nodes.put(id,new NodeV(id,value)); return true;//删除成功 } return false;//删除结点不存在
}删除图中的顶点
/** * 删除节点 */
public void removeNode(Integer id) { // 移除点集的结点并获取该节点以待后续处理。 NodeV nodeToRemove nodes.remove(id); // 删除节点存在则执行删除 if (nodeToRemove ! null) { // 删除与该节点相关的所有边 for (NodeV neighbor : nodeToRemove.nexts) { // 从邻居中移除与nodeToRemove的关联 neighbor.removeNeighbor(nodeToRemove); // 安全地移除边 neighbor.edges.removeIf(edge - edge.to nodeToRemove); } // 移除与nodeToRemove相关的所有边 edges.removeIf(edge - edge.from nodeToRemove || edge.to nodeToRemove); }
}源码
Graph类
package graph; import java.util.*; /** * author Autumn Whispser * param V */
public class GraphV { /*将顶点按顺序编号 */ //构造点集--实际编号和具体的数据关联起来。 HashMapInteger, NodeV nodes; //存储边集 HashSetEdgeV edges; //构造函数 public Graph() { //初始化点集和边集/ nodes new HashMapInteger, NodeV(); edges new HashSetEdgeV(); } //判断图是否为空集 public boolean isEmpty() { return nodes.isEmpty(); } //获取顶点数量 public int size() { return nodes.size(); } //获取边的数量 public int sizeOfEdges(){ return edges.size(); } /* * 给定编号和值创建一个新顶点并加入到图中。 * 若编号重复 则添加失败。 * param id 编号 * param value 值 * return 返回一个布尔值添加成功了返回true。 */ public boolean addNode(Integer id, V value) { if (!nodes.containsKey(id)) { nodes.put(id,new NodeV(id,value)); return true;//删除成功 } return false;//删除结点不存在 } /** * 删除节点 */ public void removeNode(Integer id) { //移除点集的结点 并且获取该值以待后续处理。 NodeV nodeToRemove nodes.remove(id); //删除结点是存在的 则执行删除 if (nodeToRemove ! null) { // 边集:删除与该节点相关的所有边---for each循环实现 for(NodeV neighbor: nodeToRemove.nexts){ //删除邻居之间可能的关联 removeEdgeDirect(neighbor.id,nodeToRemove.id); //所有邻居的入度-1因为有序关联nodeToReove都要执行删除。 neighbor.in--; } for (EdgeV edge : new HashSet(edges)) { if (edge.getFrom() nodeToRemove || edge.getTo() nodeToRemove) { edges.remove(edge); } } // 更新移除结点所有邻居的入度。 移除的nodeToRemove不需要处理。 for (NodeV neighbor : nodeToRemove.getNexts()) { } } } /** * * param from 起点 * param to 终点 * param weight 权重 * return 返回是否添加成功一个布尔值 */ public boolean addEdge(Integer from, Integer to, int weight) { NodeV fromNode nodes.get(from); NodeV toNode nodes.get(to); //保证节点的有效性即可。 if(fromNode ! null toNode ! null){ EdgeV edge new Edge(fromNode, toNode, weight); edges.add(edge);//边集新添一条边 //更新fromNode顶点的信息 fromNode.addNeighbor(toNode);//直接邻居加1 fromNode.addEdge(edge);//fromNode关联作起点的边数1 return true;//删除成功 } return false;//删除结点不存在 } /** * * param from 起点 * param to 终点 * param weight 权重 * return 返回是否添加成功 返回一个布尔值 */ public boolean addEdgeDirect(Integer from, Integer to, int weight) { return addEdge(from, to, weight);//增加一条有向边。 } /** * 添加一条无向边 实际等效两条有向边。 * param from 起点 * param to 终点 * param weight 权重 * return 返回是否添加成功 返回一个布尔值 */ public boolean addEdgeUnDirect(Integer from, Integer to,int weight) { return addEdge(from, to,weight) addEdge(to,from,weight); } /** * 适用 无权有向图;无权无向图需要调换参数调用两次。 * 默认删除fromId-toId这条有向边。 * removeDirect删除有向边 removeUnDirect删除无向边也适用单向边不过要耗时一些 * param fromId 起点编号 * param toId 终点编号 */ public void removeEdge(Integer fromId, Integer toId) { NodeV fromNode nodes.get(fromId); NodeV toNode nodes.get(toId); if (fromNode ! null toNode ! null) { IteratorEdgeV iterator edges.iterator(); while (iterator.hasNext()) { EdgeV edge iterator.next(); if (edge.from fromNode edge.to toNode) { iterator.remove(); // 安全地删除边 fromNode.edges.remove(edge); fromNode.out--; toNode.in--; break; // 找到并删除后可以退出循环 } } } } /** * 该方法会删除所有指定起点与终点相同的边无视权重 * 适用带权有向图。无向图需要调换参数多调用一次 * param fromId * param toId */ public void removeEdgeAll(Integer fromId, Integer toId) { NodeV fromNode nodes.get(fromId); NodeV toNode nodes.get(toId); if (fromNode ! null toNode ! null) { IteratorEdgeV iterator edges.iterator(); while (iterator.hasNext()) { EdgeV edge iterator.next(); if (edge.from fromNode edge.to toNode) { iterator.remove(); // 安全地删除边 fromNode.edges.remove(edge); fromNode.out--; toNode.in--; } } } } /** * 适用无权有向图。带权图允许多重边会随机干掉一条有向边。不带权的边唯一。 * 删除有向边 * param fromId 起点编号 * param toId 终点编号 */ public void removeEdgeDirect(Integer fromId, Integer toId){ removeEdge(fromId, toId); } /** * 适用无权无向图。带权图允许多重边会随机干掉一对无向边无视权重。不带权的边唯一。 * 删除无向边 内部会调用两次removeDirect函数。 * param fromId 起点编号 * param toId 终点编号 */ public void removeEdgeUnDirect(Integer fromId, Integer toId){ removeEdge(fromId, toId); removeEdge(toId, fromId); } /** * * param fromId 起点编号 * param toId 终点编号 * param weight 权重 * return 返回满足的有向边 */ private EdgeV search(Integer fromId, Integer toId, int weight) { NodeV fromNode nodes.get(fromId); NodeV toNode nodes.get(toId); if (fromNode ! null toNode ! null) { IteratorEdgeV iterator edges.iterator(); while (iterator.hasNext()) { EdgeV edge iterator.next(); if (edge.from fromNode edge.to toNode edge.weight weight) { return edge; } } } return null; } /** * 适用带权有向图。 * 删除指定带权有向边如果存在。 * param fromId 起点编号 * param toId 终点编号 * param weight 权重 */ public void removeEdgeWithWeight(Integer fromId, Integer toId, int weight){ EdgeV edge search(fromId, toId, weight); if (edge ! null) { edges.remove(edge); nodes.get(fromId).out--; nodes.get(toId).in--; } } /** * 适用带权无向图。 * 删除指定带权的无向边。 * param fromId 起点编号 * param toId 终点编号 * param weight 权重 */ public void removeEdgeWithWeightUnDirect(Integer fromId, Integer toId, int weight) { removeEdgeWithWeight(fromId, toId, weight); // 删除有向边 removeEdgeWithWeight(toId, fromId, weight); // 删除反向边 } // Override
// public boolean equals(Object o) {
// if (this o) return true;
// if (o null || getClass() ! o.getClass()) return false;
// Graph? graph (Graph?) o;
//
// } public boolean isSameGraph(GraphV other) { if (nodes.size() ! other.nodes.size() || edges.size() ! other.edges.size()) { return false; // 如果节点或边的数量不同直接返回 false } //检查点集 for (Map.EntryInteger, NodeV entry : nodes.entrySet()) { NodeV otherNode other.nodes.get(entry.getKey()); if (otherNode null || !entry.getValue().value.equals(otherNode.value)) { return false; // 检查节点的值 } } // 检查边 for (EdgeV edge : edges) { EdgeV otherEdge other.edges.stream() .filter(e - e.from.id edge.from.id e.to.id edge.to.id) .findFirst().orElse(null); if (otherEdge null || edge.weight ! otherEdge.weight) { return false; // 检查边的权重 } } return true; } /** * 该方法会合并另一个图. 进行深拷贝。 * 这里假定编码唯一。重复了的id则不添加。 * param other 另一个图 */ public void union(GraphV other) { if(!isSameGraph(other)){ return ;//相同图不用合并。 } GraphV newGraph other.deepCopy(); //合并点集 for(Map.EntryInteger, NodeV entry : newGraph.nodes.entrySet()){ Integer id entry.getKey(); if(!nodes.containsKey(id)){ NodeV node entry.getValue(); nodes.put(id,node); } } // 合并边集避免重复边 for (EdgeV edge : newGraph.edges) { if (!edges.contains(edge)) { edges.add(edge); edge.from.addEdge(edge); // 更新起点的边 edge.from.addNeighbor(edge.to); // 更新邻接关系 } } } public void contractNodes(NodeV u, NodeV v) { if (u null || v null || u v) { return; // 空引用或自环的情况无法进行边收缩。 } // 合并两个顶点的值 V newValue mergeValues(u.getValue(), v.getValue()); // 创建新节点使用其中一个顶点的ID NodeV newNode new Node(u.getId(), newValue); // 更新边的起点和终点 for (EdgeV edge : edges) { if (edge.from u || edge.from v) { edge.from newNode; } if (edge.to u || edge.to v) { edge.to newNode; } } // 删除原有的节点 nodes.remove(u.id); nodes.remove(v.id); // 添加新节点到图中 nodes.put(newNode.id, newNode); } private V mergeValues(V value1, V value2) { // 自定义合并逻辑 // 例如可以选择返回一个合并后的值或根据特定规则进行选择 return value1; // 示例简单返回第一个值 } public GraphV deepCopy() { GraphV newGraph new Graph(); // 先深拷贝点集:复制节点 for (Map.EntryInteger, NodeV entry : nodes.entrySet()) { NodeV originalNode entry.getValue(); NodeV newNode new Node(originalNode.id, originalNode.value); newGraph.nodes.put(entry.getKey(), newNode); } // 然后复制边并建立关联 //遍历原图的边 获取权重 根据id来建立新节点的联系。 保证新节点关联边与原图逻辑上是一致的。 for (EdgeV edge : edges) { //根据编号id操作新图 //操作新图 根据id获取起点终点两个图建立联系是通过id。 NodeV fromNode newGraph.nodes.get(edge.from.id); NodeV toNode newGraph.nodes.get(edge.to.id); EdgeV newEdge new Edge(fromNode, toNode, edge.weight); newGraph.edges.add(newEdge); fromNode.addEdge(newEdge); // 更新起点的边 fromNode.addNeighbor(toNode); // 更新邻接关系 } return newGraph; } /*查找*/ EdgeV searchEdge(NodeV from, NodeV to){ for (EdgeV edge : edges) { if (edge.getFrom() from edge.getTo() to) { return edge; } } return null; } /*查找带权边 */ EdgeV searchEdgeWithWeight(NodeV from, NodeV to, int weight){ for (EdgeV edge : edges) { if (edge.getFrom() from edge.getTo() to edge.getWeight() weight) { return edge; } } return null; }
}Node类
package graph; import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects; /** * author AutumnWhisper * 回顾离散数学 */
public class NodeV { int id;//编号 //顶点存储的值 V value; //入度 int in; //出度 int out; //直接可达结点表:顶点V的所有相邻顶点的集合.直接邻居 ArrayListNodeV nexts; //存储以该节点为起点的有向边。 ArrayListEdgeV edges; //初始化默认顶点为孤立点 public Node(int id,V value) { this.id id; this.value value; this.in 0; this.out 0; this.nexts new ArrayList(); this.edges new ArrayList(); } //获取当前顶点的编号 public int getId() { return id; } //获取当前节点存储的有效值 public V getValue() { return value; } //设置当前节点存储的值 public V setValue(V value) { V oldVal this.value; this.value value; return oldVal; } //获取入度 public int getIn(){ return in; } //获取出度 public int getOut(){ return out; } //提供当前顶点的邻接顶点列表不可修改 public ListNodeV getNexts(){ return Collections.unmodifiableList(nexts); } //提供以当前结点为顶点的关联边数。(不可修改) public ListEdgeV getEdges(){ return Collections.unmodifiableList(edges); } Override public boolean equals(Object obj) { if (this obj) return true; if (obj null || getClass() ! obj.getClass()) return false; Node? node (Node?) obj; return id node.id in node.in out node.out (Objects.equals(value, node.value)) nexts.equals(node.nexts) edges.equals(node.edges); } Override public int hashCode() { int result Integer.hashCode(id); result 31 * result (value ! null ? value.hashCode() : 0); result 31 * result Integer.hashCode(in); result 31 * result Integer.hashCode(out); result 31 * result nexts.hashCode(); result 31 * result edges.hashCode(); return result; } /** * 当前节点新增邻居 * param neighbor 邻居 */ void addNeighbor(NodeV neighbor){ nexts.add(neighbor); this.out;//当前节点出度1 neighbor.in;//邻居入度1 } /** * 当前节点删除邻居 * 不对边关系有任何处理 * 处理度数 */ void removeNeighbor(NodeV neighbor){ nexts.remove(neighbor); this.in--; neighbor.out--; } /** * 当前节点新增边 * param edge 边 */ void addEdge(EdgeV edge){ edges.add(edge); } /** * */ void removeEdge(EdgeV edge){ edges.remove(edge); }
}Edge类
package graph; import java.util.Objects; //顶点不依赖边 边依赖顶点
public class EdgeV { //权重 int weight; NodeV from;//起点 NodeV to;//终点 //边依赖顶点的条数。 public Edge(int weight, NodeV from, NodeV to) { this.weight weight; this.from from; this.to to; } public Edge(NodeV from, NodeV to, int weight) { this.weight weight; this.from from; this.to to; } //用户提供的接口。 //获取权重 public int getWeight() { return weight; } //重新设置权重 public void setWeight(int weight) { this.weight weight; } //获取边的起点 public NodeV getFrom() { return from; } //设置边的起点 public void setFrom(NodeV from) { this.from from; } //获取边的终点 public NodeV getTo() { return to; } //设置边的终点 public void setTo(NodeV to) { this.to to; } Override public boolean equals(Object o){ if(this o) return true; if(o null || getClass() ! o.getClass()) return false; Edge? edge (Edge?) o; if(weight ! edge.weight) return false; if(!Objects.equals(from, edge.from)) return false; return Objects.equals(to, edge.to); }
}白雪尽皑皑 天地我独行。 独行无牵挂 孤影任去来。
