【数据结构】---图

前言

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

学习基本路线:

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

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

引入

图是由顶点和连接顶点的边构成的离散结构。
根据图中的边是否有方向? 相同顶点对之间是否有多条边相连以及是否允许存在自环
图的定义
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 EdgeV×V:描述了是边的顶点的二元集.
∣ E ∣ |E| E:边的条数.
∣ V ∣ |V| V:顶点个数.
考虑有限图:顶点集和边集为有限集的图称为有限图。

重点-简单图:

  1. "No self loops": 图中的顶点不能有连接到自身的边,不能有自环的情况.
  2. "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
简单有向图:简单图的基础上赋予方向就是简单有向图。

其它图的讨论

混合图:既包含有向边和无向边的图称为无向图。
实际写代码时,混合图和无向图均可以当作有向图,无向边当作两条对立的有向边。

多重图:即允许两顶点之间存在多条边的图。
自环:自环是指一条边的起点和终点是同一个节点。

图的术语和特殊类型的图

图的基本术语

  1. 图 (Graph): 由顶点 (Vertices) 和边 (Edges) 组成的数学结构,用于表示对象之间的关系。
  2. 顶点 (Vertex): 图中的基本单位,通常表示一个对象。
  3. 边 (Edge): 连接两个顶点的线,表示它们之间的关系。
  4. 邻接 (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。
  5. 路径 (Path): 从一个顶点到另一个顶点的边的序列,且没有重复的顶点。
  6. 圈 (Cycle): 从一个顶点出发,经过若干边后回到该顶点的路径,且路径中的其他顶点都不重复。
  7. 度:
    顶点的度(degree):跟顶点相连接的边的条数。
    入度与出度:对于有向图,一个顶点的入度是指以其为终点的边数;
    出度指以该顶点为起点的边数。 反应了度和边数的关系。
    图的度:
    对于无向图 ∀ v ∈ V , ∑ d e g r e e ( v ) = 2 ∣ E ∣ \forall v\in V, \sum degree(v) = 2|E| vV,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| vV,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的点是悬挂点
特殊类型的图汇总
  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 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
  2. 邻居: G = ( V , E ) G=(V,E) G=(V,E),顶点 v v v的所有相邻顶点的集合, 记作 N ( v ) N(v) N(v)。其称为顶点的邻居。
  3. 度:
    顶点的度(degree):跟顶点相连接的边的条数。
    入度与出度:对于有向图,一个顶点的入度是指以其为终点的边数;
    出度指以该顶点为起点的边数。 反应了度和边数的关系。
    图的度:
    对于无向图 ∀ v ∈ V , ∑ d e g r e e ( v ) = 2 ∣ E ∣ \forall v\in V, \sum degree(v) = 2|E| vV,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| vV,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的点是悬挂点
两个定理
  1. 握手定理:描述度与边数的关系。定义m图 G G G 2 m = ∑ v ϵ V d e g ( V ) 2m = \sum_{v\epsilon V}deg(V) 2m=vϵVdeg(V)
  2. 无向图的有偶数个奇度顶点

讨论简单图中无向图与有向图的边个数
无向图: ∣ E ∣ ≤ ( ∣ V ∣ 2 ) |E|\leq \begin{pmatrix} |V|\\ 2\\ \end{pmatrix} E(V2)
有向图: ∣ E ∣ ≤ 2 ( ∣ V ∣ 2 ) |E|\leq2 \begin{pmatrix} |V|\\ 2\\ \end{pmatrix} E2(V2)
解释:任取两顶点 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×(n1)
这是最大值,因为可能并非所有两顶点都有边.
用大 O O O表示法: ( ∣ V ∣ 2 ) = O ( ∣ V ∣ 2 ) \begin{pmatrix} |V|\\ 2\\ \end{pmatrix}=O(|V|^2) (V2)=O(V2)

图的表示

关于图, 标准的两种标准表示方法, 一种表示将图作为邻接链表的组合, 另一种将图作为邻接矩阵表示。
两种方法均可以表示无向图和有向图, 更准确地可以表示混合图。

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

图的个人通用实现

由前面图的定义, 我们可以给出图的代码实现。
个人习惯用哈希表存储顶点和边, 因为更符合数学上集合的概念。
其次, 哈希表可以快速查询边或者顶点是否属于该图, 且Java中的HashMap,HashSet存储的是不重复的元素,十分便利。

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

前置准备

编程语言:Java
创建一个package graph,
创建三个.java文件, 每个文件各有一个公共类, 分别是Graph,Node,Edge

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();  
}

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

Node类,单个结点自带的值value, 入度和出度,邻接顶点, 关联边数。
![[Pasted image 20240928194111.png]]

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

入度: 指向某个节点的边的数量。它反映了有多少个其他节点指向该节点,揭示该节点在图中的“吸引力”或“重要性”。
出度:从某个节点发出的边的数量。它表明该节点能够连接多少其他节点,显示该节点的“影响力”或“传播能力”。
存储两者的信息可以反应该顶点的重要性, 然后入度与出度这两个属性可以优化算法(比方说后续的最短路径,拓朴排序等等), 它还可以反应图的结构特性,识别某个特定节点(孤立点,集群等等)。

  1. 顶点存储它直接可达的其它顶点(直接邻居)。

必要性:方便动态操作,比如我们要删去或者添加边时,只需要对相关顶点的邻接列表操作即可, 避免了整体上所有邻接关系的修改。
快速访问邻居的信息。 邻接列表相当于存储了直接邻居的地址, 在后续处理遍历操作时异常便捷(深度优先遍历和广度优先遍历)。
很多算法依赖邻居关系, 如最短路径,求解连通分量问题。
5. 存储以该节点为起点的有向边。 高效访问节点附近的所有边; 动态操作, 操作边的增删查改时只需要局部性调整即可,非常便捷。维护信息,可以高效地维护其它属性。算法角度:对依赖边的图算法有较大的便利实现。

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);  
}

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 e 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 方法添加两条有向边(fromtotofrom),实现无向边的效果。
  • 返回值:如果两个有向边都成功添加,则返回 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);  }  
}

白雪尽皑皑, 天地我独行。
独行无牵挂, 孤影任去来。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/436908.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Azkaban:大数据任务调度与编排工具的安装与使用

在当今大数据时代&#xff0c;数据处理和分析任务变得越来越复杂。一个完整的大数据分析系统通常由大量任务单元组成&#xff0c;如 shell 脚本程序、mapreduce 程序、hive 脚本、spark 程序等。这些任务单元之间存在时间先后及前后依赖关系&#xff0c;为了高效地组织和执行这…

NAL 网络提取层(Network Abstraction Layer)

1.NAL全称Network Abstract Layer, 即网络抽象层。 在H.264/AVC视频编码标准中&#xff0c;无论是存储还是网络传输&#xff0c;H264 原始码流是由一个接一个 NALU&#xff08;NAL Unit&#xff09; 组成&#xff0c;整个系统框架被分为两个层面&#xff1a;视频编码层面&#…

Linux 实用工具Axel安装及使用教程(支持多线程下载)

一、Axel 简介 Axel 是一个轻量级的命令行下载加速器&#xff0c;旨在提高文件下载速度。 多线程下载: Axel 可以同时使用多个连接来下载文件&#xff0c;从而加快下载速度。断点续传: 支持中断后继续下载&#xff0c;避免重新开始下载整个文件。轻量级: 资源占用少&#xff0c…

YOLOv1–v11: 版本演进及其关键技术解析

最新消息&#xff1a;Yolo11发布最新版本2024.10 YOLO (You Only Look Once) 是一种高效的目标检测算法&#xff0c;自其初代发布以来&#xff0c;经过多次迭代&#xff0c;逐步提升了检测速度和精度。本文将详细介绍 YOLO 从 v1 到 v11 的各个版本&#xff0c;涵盖每个版本的发…

谨防火灾!电瓶车检测算法助力城市/小区/园区多场景安全管理精细化、智能化

随着人工智能技术的快速发展&#xff0c;AI智能分析网关V4在电瓶车检测领域的应用日益广泛。这一技术通过深度学习、计算机视觉等先进算法&#xff0c;实现了对电瓶车及其相关行为的智能识别和分析&#xff0c;为电瓶车的管理和应用提供了强大的技术支持。 一、电瓶车检测算法…

测试用例的进阶二

1. 按开发阶段划分 1.1 测试金字塔 从上到下&#xff0c;对于测试人员代码就是要求越来越低&#xff1b; 从下到上&#xff0c;越来越靠近用户&#xff1b; 从下到上&#xff0c;定位问题的成本越来越高&#xff1b; 1.2 单元测试(Unit Testing) 单元测试是对软件组成单元进…

1.8 物理层下的传输媒体

欢迎大家订阅【计算机网络】学习专栏&#xff0c;开启你的计算机网络学习之旅&#xff01; 文章目录 1 导引型传输媒体1.1 双绞线1.2 同轴电缆1.3 光缆 2 非导引型传输媒体2.1 无线电微波通信2.2 多径效应2.3 卫星通信2.4 无线局域网 在数据通信系统中&#xff0c;传输媒体是发…

在线PDF怎么转换成JPG图片?分享14种转换操作!

作为一名社畜&#xff0c;俺也经常要将PDF转换为图片格式&#xff01; 如何进行快速转换&#xff0c;包括电脑端、在线端和手机端&#xff0c;今天俺就测评了50款工具&#xff0c;给你得出了下面这些渠道&#xff0c;不少也是免费的&#xff0c;相信对你有帮助哦&#xff01; …

25考研咨询周开启,西安电子科技大学是否改考408??

学长这几天帮大家问了西安电子科技大学是否会从833、834、953改考为408&#xff1f; 西电老师回复&#xff1a;根据上级文件要求&#xff0c;招生简章以及专业目录会在网上报名开始前公布&#xff0c;专业课不会又大变动&#xff01; 因为大家安心复习即可&#xff0c;保证今…

Python 基于 flask 的前程无忧招聘可视化系统,Python大数据招聘爬虫可视化分析

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

谷歌网站收录查询,帮助您快速准确地查询网站在谷歌的收录情况的3个方法

谷歌网站收录查询&#xff0c;帮助您快速准确地查询网站在谷歌的收录情况的3个方法。 一、使用GoogleSearchConsole&#xff08;谷歌搜索控制台&#xff09; 1.注册并验证网站 -首先&#xff0c;确保您的网站已注册并验证在GoogleSearchConsole中。这是一个免费的工具&…

2-109 基于matlab-GUI的BP神经网络

基于matlab-GUI的BP神经网络&#xff0c;10种不同分布的数据样本&#xff0c;9种不同的激活函数&#xff0c;可更改升级网络结构参数&#xff0c;对比各种方法参数下的训练测试效果&#xff0c;实时显示预测过程。程序已调通&#xff0c;可直接运行。 下载源程序请点链接&…

C++ 游戏开发

C游戏开发 C 是一种高效、灵活且功能强大的编程语言&#xff0c;因其性能和控制能力而在游戏开发中被广泛应用。许多著名的游戏引擎&#xff0c;如 Unreal Engine、CryEngine 和 Godot 等&#xff0c;都依赖于 C 进行核心开发。本文将详细介绍 C 在游戏开发中的应用&#xff0…

ireport 5.1 中文生辟字显示不出来,生成PDF报字体找不到

ireport生成pdf里文字不显示。本文以宋体中文字不显示为例。 问题&#xff1a;由浅入深一步一步分析 问题1、预览正常&#xff0c;但生成pdf中文不显示 报告模板编辑后&#xff0c;预览正常&#xff0c;但生成pdf中文不显示。以下是试验过程&#xff1a; 先编辑好一个报告单模…

苹果荔枝柠檬梨柿子数据集 水果数据集 树上1500张 带标注 voc yolo 5类

苹果荔枝柠檬梨柿子数据集 水果数据集 树上1500张 带标注 voc yolo 5类 苹果荔枝柠檬梨柿子数据集 名称 苹果荔枝柠檬梨柿子数据集 (Apple, Litchi, Lemon, Pear, Persimmon Dataset) 规模 图像数量&#xff1a;1498张图像。类别&#xff1a;5种水果类别。标注个数&#xff…

成都网安周暨CCS2024 | 大模型安全与产业应用创新研讨活动成功举办

9月11日-12日&#xff0c;作为2024年国家网络安全宣传周成都系列活动的重磅活动之一&#xff0c;CCS 2024成都网络安全系列活动在成都举行。“大模型安全与产业应用创新研讨活动”同期举办&#xff0c;本场活动由百度安全、成都无糖信息联合承办&#xff0c;特邀云安全联盟CSA大…

数据权限的设计与实现系列11——前端筛选器组件Everright-filter集成功能完善2

‍ 筛选条件数据类型完善 文本类 筛选器组件给了一个文本类操作的范例&#xff0c;如下&#xff1a; Text: [{label: 等于,en_label: Equal,style: noop},{label: 等于其中之一,en_label: Equal to one of,value: one_of,style: tags},{label: 不等于,en_label: Not equal,v…

Gin框架简易搭建(3)--Grom与数据库

写在前面 项目地址 个人认为GORM 指南这个网站是相比较之下最为清晰的框架介绍 但是它在环境搭建阶段对于初学者而言不是很友好&#xff0c;尤其是使用mysql指令稍有不同&#xff0c;以及更新的方法和依赖问题都是很让人头疼的&#xff0c;而且这些报错并非逻辑上的&#xf…

【Redis】如何在 Ubuntu 上安装 Redis 5

&#x1f970;&#x1f970;&#x1f970;来都来了&#xff0c;不妨点个关注叭&#xff01; &#x1f449;博客主页&#xff1a;欢迎各位大佬!&#x1f448; 本期内容主要介绍如何在 Ubuntu 上安装 Redis5 一些碎碎念&#xff1a; 本来这期内容介绍如何在 Centos 安装 Redis …

TypeScript 设计模式之【状态模式】

文章目录 状态模式&#xff1a;优雅切换的交通信号灯状态模式的奥秘状态模式有什么利与弊?如何使用状态模式来优化你的系统代码实现案例状态模式的主要优点状态模式的主要缺点状态模式的适用场景总结 状态模式&#xff1a;优雅切换的交通信号灯 当你站在繁忙的十字路口&#…