【数据结构】—图

大家好，欢迎来到IT知识分享网。

图

前言

本篇作为图的基础概念篇， 了解图的离散数学定义， 图的分类， 图模型解决的问题（图的应用）， 图的相关算法（仅仅介绍，具体不在此篇展开）。

学习基本路线：

1. 学习离散数学的图章节。对图有宏观的把握。
2. 从代码上， 完成图的表示。 学习深度优先搜索和广度优先搜索。
3. 进一步学习图的其它算法， 比如单源最短路径， 求解图的连通分量， 最小生成树算法等等， 还可以求解离散数学的其它问题（如二分图， 欧拉图， 哈密顿图等等）。学习图的算法可以加深对离散数学在计算机科学的理解。

离散数学这门学科本身就广泛应用于各大学科， 并非只是对计算机科学如此。

引入

重点-简单图:

1. "No self loops": 图中的顶点不能有连接到自身的边,不能有自环的情况.
2. "Every edge is distinct": 不能存在相同的边.
   针对无向图:每对顶点只有一条边.
   针对有向图:每对顶点同方向的边唯一.
   不重点考虑多重图，即存在不同边连接一对相同的顶点。
   不考虑自环现象：即，边关联的两个顶点是同一个顶点。
   图的分类
   有向图与无向图.
   
   对$v,u$
   无向图:边被描述为顶点的无序二元集:{v,u},说明了$v$,$u$两顶点之间有一条边.无序性:含义是 {u,v}$=${v,u} .
   有向图:边被表示为顶点的有序二元集:(v,u),说明了$v$,$u$有一条顶点v到u的边.有序性:含义是 (u,v) 和 (v,u) 是两条不同的边
   无向图的边是无序的二元对，而有向图的边是有序的二元对。
   
   
   
   
   
   
   
   
   
   
   

有向图

定义: 有向图$G=(V,E)$，由一个非空顶点集$V$和一个有向边（称为弧）集$E$组成。 每条有向边与一个有序点对相关联。有序对$(u,v)$相关联的有向边开始于$u$、结束于$v$。
简单有向图：简单图的基础上赋予方向就是简单有向图。

其它图的讨论

图的术语和特殊类型的图

图的基本术语

1. 图 (Graph): 由顶点 (Vertices) 和边 (Edges) 组成的数学结构，用于表示对象之间的关系。
2. 顶点 (Vertex): 图中的基本单位，通常表示一个对象。
3. 边 (Edge): 连接两个顶点的线，表示它们之间的关系。
4. 邻接 (Adjacent): 如果两个顶点之间有边相连，则称它们是邻接的。若两顶点$u$和$v$是无向图$G$中的一条边$e$的端点， 则称两个顶点$u$和$v$$G$里邻接（相邻）。称边$e$为关联顶点$u,v$。或者叫做边$e$连接$u$$,v$。对于有向图，假设是$u$到$v$的有向边，那么称边e把$u$邻接到$v$，或者称$v$从$u$邻接。简而言之， 对于这条有向边，只能说u邻接v,而v不邻接u。
5. 路径 (Path): 从一个顶点到另一个顶点的边的序列，且没有重复的顶点。
6. 圈 (Cycle): 从一个顶点出发，经过若干边后回到该顶点的路径，且路径中的其他顶点都不重复。
7. 度：
   顶点的度(degree):跟顶点相连接的边的条数。
   入度与出度:对于有向图，一个顶点的入度是指以其为终点的边数；
   出度指以该顶点为起点的边数。 反应了度和边数的关系。
   图的度:
   对于无向图$\forall v\in V,\sum degree(v)=2|E|$
   对于有向图$\forall v\in V,\sum degre{e}^{+}(v)=\sum degre{e}^{-}(v)=|E|$
   $degre{e}^{+}(v):有向图顶点的出度.$ $degre{e}^{-}(v)：$有向图顶点的入度。
   顶点度为0的点是孤立点
   顶点度为1的点是悬挂点
   
   
   
   
   
   
   
   
   

特殊类型的图汇总

1. 无向图 (Undirected Graph): 边没有方向，连接的两个顶点是对称的。
2. 有向图 (Directed Graph): 边有方向，表示从一个顶点到另一个顶点的单向关系。
3. 加权图 (Weighted Graph): 每条边都有一个权重，表示边的成本、距离等。
4. 简单图 (Simple Graph): 不允许有自环（从一个顶点到自身的边）和多重边（相同的两个顶点之间有多条边）。
5. 完全图 (Complete Graph): 图中每一对顶点之间都有边相连。
6. 树 (Tree): 一种特殊的无向图，具有无圈的特性，且任何两个顶点之间都有唯一的路径。
7. 森林 (Forest): 由多个树组成的图。
8. 连通图 (Connected Graph): 在无向图中，任意两个顶点之间都存在路径；在有向图中，存在从一个顶点到另一个顶点的有向路径。
9. 强连通图 (Strongly Connected Graph): 在有向图中，任意两个顶点之间都有有向路径。
10. 平面图 (Planar Graph): 可以在平面上绘制的图，使得边的交叉最小。

关于连通图，可达性，路径等概念， 结合后续算法题说明。

图的基本术语

1. 顶点相邻：若两顶点$u$和$v$是无向图$G$中的一条边$e$的端点， 则称两个顶点$u$和$v$$G$里邻接（相邻）。称边$e$为关联顶点$u,v$。或者叫做边$e$连接$u$$,v$。
2. 邻居:$G=(V,E)$,顶点$v$的所有相邻顶点的集合， 记作$N(v)$。其称为顶点的邻居。
3. 度：
   顶点的度(degree):跟顶点相连接的边的条数。
   入度与出度:对于有向图，一个顶点的入度是指以其为终点的边数；
   出度指以该顶点为起点的边数。 反应了度和边数的关系。
   图的度:
   对于无向图$\forall v\in V,\sum degree(v)=2|E|$
   对于有向图$\forall v\in V,\sum degre{e}^{+}(v)=\sum degre{e}^{-}(v)=|E|$
   $degre{e}^{+}(v):有向图顶点的出度.$ $degre{e}^{-}(v)：$有向图顶点的入度。
   顶点度为0的点是孤立点
   顶点度为1的点是悬挂点
   
   
   
   
   
   
   
   
   

两个定理

1. 握手定理：描述度与边数的关系。定义m图$G$—$2m={\sum }_{vϵV}deg(V)$
2. 无向图的有偶数个奇度顶点。

讨论简单图中无向图与有向图的边个数
无向图:$|E|\le \left(\begin{array}{c}|V|\\ 2\end{array}\right)$
有向图:$|E|\le 2\left(\begin{array}{c}|V|\\ 2\end{array}\right)$
解释:任取两顶点$v,u$的排列数排列数 $p(n,2)=\frac{n\times (n-1)}{2}$。
这是最大值,因为可能并非所有两顶点都有边.
用大$O$表示法:$\left(\begin{array}{c}|V|\\ 2\end{array}\right)=O(|V{|}^2)$

图的表示

本篇实现偏向于邻接表，是图比较通用的写法。

图的个人通用实现

以下图适用于纯无向图，纯有向图，混合图， 混合图， 多重图， 存在自环的图。
不过其仍旧是有限图， 实际工程上也不存在无限图的情况。

前置准备

Graph类

Graph,包含点集和边集。 很符合数学中的定义， 以下是基础版本的描述。

package Graph; import java.util.HashMap; import java.util.HashSet; public class Graph<V> { 
    /*将顶点按顺序编号 点集*/ public HashMap<Integer, Node<V>> nodes; //存储边集  public HashSet<Edge<V>> edges; //构造函数  public Graph() { 
    nodes = new HashMap<Integer, Node<V>>(); edges = new HashSet<Edge<V>>(); } } 

public HashMap<Integer, Node<V>> nodes; 将顶点用整数编号， 结合现实每座城市都有唯一标识的编号处理。

//判断图是否为空集  public boolean isEmpty() { 
     return nodes.isEmpty(); } //获取顶点数量  public int size() { 
     return nodes.size(); } //获取边的数量  public int sizeOfEdges(){ 
     return edges.size(); } 

尽管从数学角度上， 图不为空集， 但这里还是补上判空方法。

1. 顶点存储自己的编号：后续对图的深拷贝有必要。
2. 顶点可以存储附加值value。 根据自己实际需求
3. 顶点存储入度和出度的值：

4. 顶点存储它直接可达的其它顶点（直接邻居）。

package Graph; import java.util.ArrayList; import java.util.Collections; import java.util.List; / * @author AutumnWhisper * 回顾离散数学 */ public class Node<V> { 
     int id;//编号  //顶点存储的值  V value; //入度  int in; //出度  int out; //直接可达结点表:顶点V的所有相邻顶点的集合.====直接邻居  ArrayList<Node<V>> nexts; //存储以该节点为起点的有向边。  ArrayList<Edge<V>> 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 List<Node<V>> getNexts(){ 
     return Collections.unmodifiableList(nexts); } //提供以当前结点为顶点的关联边数。(不可修改)  public List<Edge<V>> getEdges(){ 
     return Collections.unmodifiableList(edges); } } 

Node类提供两个辅助方法来新增邻居和边， 这只是辅助其它方法实现的。

 / * 当前节点新增邻居 * @param neighbor 邻居 */ void addNeighbor(Node<V> neighbor){ 
     nexts.add(neighbor); this.out++;//当前节点出度+1  neighbor.in++;//邻居入度+1  } / * 当前节点新增边 * @param edge 边 */ void addEdge(Edge<V> edge){ 
     edges.add(edge); } 

package Graph; //顶点不依赖边， 边依赖顶点  public class Edge<V> { 
     //权重  int weight; Node<V> from;//起点  Node<V> to;//终点  public Edge(int weight, Node<V> from, Node<V> to) { 
     this.weight = weight; this.from = from; this.to = to; } //----给包外提供的接口。  //获取权重  public int getWeight() { 
     return weight; } //重新设置权重  public void setWeight(int weight) { 
     this.weight = weight; } //获取边的起点  public Node<V> getFrom() { 
     return from; } //设置边的起点  public void setFrom(Node<V> from) { 
     this.from = from; } //获取边的终点  public Node<V> getTo() { 
     return to; } //设置边的终点  public void setTo(Node<V> to) { 
     this.to = to; } } 

基本操作

增加图中的边

假设我们增加一条边$e$, 使得原图中两个原本不相关联的两个顶点被连接起来。
新图： G + e = ( V , E ∪ { e } ) G + e = (V,E\cup \{e\}) G+e=(V,E∪{
e})

/ * * @param from 起点 * @param to 终点 * @param weight 权重 * @return 返回是否添加成功，一个布尔值 */ public boolean addEdge(Integer from, Integer to, int weight) { 
     Node<V> fromNode = nodes.get(from); Node<V> toNode = nodes.get(to); //保证节点的有效性即可。  if(fromNode != null && toNode != null){ 
     Edge<V> 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) { 
     Node<V> fromNode = nodes.get(from); Node<V> toNode = nodes.get(to); //保证节点的有效性即可。  if(fromNode != null && toNode != null){ 
     Edge<V> 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) { 
     Node<V> fromNode = nodes.get(fromId); Node<V> toNode = nodes.get(toId); if (fromNode != null && toNode != null) { 
     Iterator<Edge<V>> iterator = edges.iterator(); while (iterator.hasNext()) { 
     Edge<V> 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) { 
     Node<V> fromNode = nodes.get(fromId); Node<V> toNode = nodes.get(toId); if (fromNode != null && toNode != null) { 
     Iterator<Edge<V>> iterator = edges.iterator(); while (iterator.hasNext()) { 
     Edge<V> 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 Edge<V> search(Integer fromId, Integer toId, int weight) { 
     Node<V> fromNode = nodes.get(fromId); Node<V> toNode = nodes.get(toId); if (fromNode != null && toNode != null) { 
     Iterator<Edge<V>> iterator = edges.iterator(); while (iterator.hasNext()) { 
     Edge<V> 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){ 
     Edge<V> 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 Node<V>(id,value)); return true;//删除成功  } return false;//删除结点不存在  } 

删除图中的顶点

/ * 删除节点 */ public void removeNode(Integer id) { 
     // 移除点集的结点，并获取该节点以待后续处理。  Node<V> nodeToRemove = nodes.remove(id); // 删除节点存在，则执行删除  if (nodeToRemove != null) { 
     // 删除与该节点相关的所有边  for (Node<V> 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 Graph<V> { 
     /*将顶点按顺序编号 */ //构造点集--实际编号和具体的数据关联起来。  HashMap<Integer, Node<V>> nodes; //存储边集  HashSet<Edge<V>> edges; //构造函数  public Graph() { 
     //初始化点集和边集/  nodes = new HashMap<Integer, Node<V>>(); edges = new HashSet<Edge<V>>(); } //判断图是否为空集  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 Node<V>(id,value)); return true;//删除成功  } return false;//删除结点不存在  } / * 删除节点 */ public void removeNode(Integer id) { 
     //移除点集的结点， 并且获取该值以待后续处理。  Node<V> nodeToRemove = nodes.remove(id); //删除结点是存在的， 则执行删除  if (nodeToRemove != null) { 
     // 边集:删除与该节点相关的所有边---for each循环实现  for(Node<V> neighbor: nodeToRemove.nexts){ 
     //删除邻居之间可能的关联  removeEdgeDirect(neighbor.id,nodeToRemove.id); //所有邻居的入度-1，因为有序关联nodeToReove都要执行删除。  neighbor.in--; } for (Edge<V> edge : new HashSet<>(edges)) { 
     if (edge.getFrom() == nodeToRemove || edge.getTo() == nodeToRemove) { 
     edges.remove(edge); } } // 更新移除结点所有邻居的入度。 移除的nodeToRemove不需要处理。  for (Node<V> neighbor : nodeToRemove.getNexts()) { 
     } } } / * * @param from 起点 * @param to 终点 * @param weight 权重 * @return 返回是否添加成功，一个布尔值 */ public boolean addEdge(Integer from, Integer to, int weight) { 
     Node<V> fromNode = nodes.get(from); Node<V> toNode = nodes.get(to); //保证节点的有效性即可。  if(fromNode != null && toNode != null){ 
     Edge<V> 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) { 
     Node<V> fromNode = nodes.get(fromId); Node<V> toNode = nodes.get(toId); if (fromNode != null && toNode != null) { 
     Iterator<Edge<V>> iterator = edges.iterator(); while (iterator.hasNext()) { 
     Edge<V> 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) { 
     Node<V> fromNode = nodes.get(fromId); Node<V> toNode = nodes.get(toId); if (fromNode != null && toNode != null) { 
     Iterator<Edge<V>> iterator = edges.iterator(); while (iterator.hasNext()) { 
     Edge<V> 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 Edge<V> search(Integer fromId, Integer toId, int weight) { 
     Node<V> fromNode = nodes.get(fromId); Node<V> toNode = nodes.get(toId); if (fromNode != null && toNode != null) { 
     Iterator<Edge<V>> iterator = edges.iterator(); while (iterator.hasNext()) { 
     Edge<V> 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){ 
     Edge<V> 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(Graph<V> other) { 
     if (nodes.size() != other.nodes.size() || edges.size() != other.edges.size()) { 
     return false; // 如果节点或边的数量不同，直接返回 false }  //检查点集  for (Map.Entry<Integer, Node<V>> entry : nodes.entrySet()) { 
     Node<V> otherNode = other.nodes.get(entry.getKey()); if (otherNode == null || !entry.getValue().value.equals(otherNode.value)) { 
     return false; // 检查节点的值  } } // 检查边  for (Edge<V> edge : edges) { 
     Edge<V> 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(Graph<V> other) { 
     if(!isSameGraph(other)){ 
     return ;//相同图不用合并。  } Graph<V> newGraph = other.deepCopy(); //合并点集  for(Map.Entry<Integer, Node<V>> entry : newGraph.nodes.entrySet()){ 
     Integer id = entry.getKey(); if(!nodes.containsKey(id)){ 
     Node<V> node = entry.getValue(); nodes.put(id,node); } } // 合并边集，避免重复边  for (Edge<V> edge : newGraph.edges) { 
     if (!edges.contains(edge)) { 
     edges.add(edge); edge.from.addEdge(edge); // 更新起点的边  edge.from.addNeighbor(edge.to); // 更新邻接关系  } } } public void contractNodes(Node<V> u, Node<V> v) { 
     if (u == null || v == null || u == v) { 
     return; // 空引用或自环的情况无法进行边收缩。  } // 合并两个顶点的值  V newValue = mergeValues(u.getValue(), v.getValue()); // 创建新节点，使用其中一个顶点的ID  Node<V> newNode = new Node<>(u.getId(), newValue); // 更新边的起点和终点  for (Edge<V> 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 Graph<V> deepCopy() { 
     Graph<V> newGraph = new Graph<>(); // 先深拷贝点集:复制节点  for (Map.Entry<Integer, Node<V>> entry : nodes.entrySet()) { 
     Node<V> originalNode = entry.getValue(); Node<V> newNode = new Node<>(originalNode.id, originalNode.value); newGraph.nodes.put(entry.getKey(), newNode); } // 然后复制边并建立关联  //遍历原图的边， 获取权重， 根据id来建立新节点的联系。 保证新节点关联边与原图逻辑上是一致的。  for (Edge<V> edge : edges) { 
     //根据编号id操作新图  //操作新图， 根据id获取起点终点，两个图建立联系是通过id。  Node<V> fromNode = newGraph.nodes.get(edge.from.id); Node<V> toNode = newGraph.nodes.get(edge.to.id); Edge<V> newEdge = new Edge<>(fromNode, toNode, edge.weight); newGraph.edges.add(newEdge); fromNode.addEdge(newEdge); // 更新起点的边  fromNode.addNeighbor(toNode); // 更新邻接关系  } return newGraph; } /*查找*/ Edge<V> searchEdge(Node<V> from, Node<V> to){ 
     for (Edge<V> edge : edges) { 
     if (edge.getFrom() == from && edge.getTo() == to) { 
     return edge; } } return null; } /*查找带权边 */ Edge<V> searchEdgeWithWeight(Node<V> from, Node<V> to, int weight){ 
     for (Edge<V> 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 Node<V> { 
     int id;//编号  //顶点存储的值  V value; //入度  int in; //出度  int out; //直接可达结点表:顶点V的所有相邻顶点的集合.====直接邻居  ArrayList<Node<V>> nexts; //存储以该节点为起点的有向边。  ArrayList<Edge<V>> 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 List<Node<V>> getNexts(){ 
     return Collections.unmodifiableList(nexts); } //提供以当前结点为顶点的关联边数。(不可修改)  public List<Edge<V>> 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(Node<V> neighbor){ 
     nexts.add(neighbor); this.out++;//当前节点出度+1  neighbor.in++;//邻居入度+1  } / * 当前节点删除邻居 * 不对边关系有任何处理 * 处理度数 */ void removeNeighbor(Node<V> neighbor){ 
     nexts.remove(neighbor); this.in--; neighbor.out--; } / * 当前节点新增边 * @param edge 边 */ void addEdge(Edge<V> edge){ 
     edges.add(edge); } / * */ void removeEdge(Edge<V> edge){ 
     edges.remove(edge); } } 

Edge类

package graph; import java.util.Objects; //顶点不依赖边， 边依赖顶点  public class Edge<V> { 
     //权重  int weight; Node<V> from;//起点  Node<V> to;//终点  //边依赖顶点的条数。  public Edge(int weight, Node<V> from, Node<V> to) { 
     this.weight = weight; this.from = from; this.to = to; } public Edge(Node<V> from, Node<V> 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 Node<V> getFrom() { 
     return from; } //设置边的起点  public void setFrom(Node<V> from) { 
     this.from = from; } //获取边的终点  public Node<V> getTo() { 
     return to; } //设置边的终点  public void setTo(Node<V> 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); } }