边列表

图算法

边列表是表示图的一种简单方式,通过存储所有边的信息(起点、终点和权重)来表示图结构。适用于边数较少的稀疏图,特别适合需要频繁查询和操作边的应用场景。

空间复杂度:O(E)

算法讲解

边列表

介绍

边列表是图论中最基础的图表示方式之一,它通过存储图中的每条边来描述整个图的结构。对于无权图,每条边表示为一个顶点对(u, v);对于有权图,则表示为三元组(u, v, weight)。

基本概念

边列表(Edge List)是表示图的一种简单数据结构,在理解它之前,我们需要先了解一些基础图论概念:

图(Graph):由顶点(Vertex)和连接顶点的边(Edge)组成的数据结构。图可以用来表示现实世界中的各种关系,如社交网络、交通路线等。

顶点(Vertex):图中的节点,通常用数字或字母标识,如 0, 1, 2... 或 A, B, C...

边(Edge):连接两个顶点的线段,表示它们之间存在某种关系。

度(Degree):指与该顶点相连的边的总数。

图根据不同特性可以分为几种类型:

无向图 vs 有向图:

  • 无向图:边没有方向,如果顶点 A 和 B 之间有边,则可以从 A 到 B,也可以从 B 到 A。
  • 有向图:边有明确的方向,如果有一条从 A 到 B 的边,不代表一定有从 B 到 A 的边。比如社交系统中的"关注"。

在有向图中,度分为入度和出度:

入度(In-degree):指向该顶点的边的数量。

出度(Out-degree):从该顶点指出的边的数量。

无权图 vs 有权图:

  • 无权图:边没有权重值,只表示两个顶点之间是否连接。
  • 有权图:每条边带有一个权重值,表示两个顶点之间连接的某种度量(如距离、成本等)。例如城市间的公路网络,边的权重可以表示距离或行驶时间。

边列表的存储方式:

  • 对于无权图:边列表中的每个元素是一个二元组 (u, v),表示从顶点 u 到顶点 v 的一条边
  • 对于有权图:边列表中的每个元素是一个三元组 (u, v, w),其中 w 表示这条边的权重

示例:
假设有一个包含 4 个顶点 (0, 1, 2, 3) 的有权图,边的信息如下:

  • 0 连接到 1,权重为 5
  • 0 连接到 2,权重为 3
  • 1 连接到 2,权重为 2
  • 2 连接到 3,权重为 7

则其边列表表示为:[(0,1,5), (0,2,3), (1,2,2), (2,3,7)]

边列表虽然概念简单,但在某些算法(如 Kruskal 最小生成树算法)中具有明显优势,因为这些算法需要对所有边进行排序并逐一处理。

核心特性

  • 简单直观:直接存储边的信息,概念简单
  • 空间效率:对于稀疏图(边数远小于|V|²的图)较为节省空间
  • 添加边方便:只需在列表末尾添加新边
  • 查找特定边效率低:需要遍历整个列表

基本操作

  • 添加边:将新的边添加到列表中
  • 删除边:遍历列表找到对应边并删除
  • 查找边:遍历列表查找特定边
  • 遍历所有边:直接遍历列表

基础实现

代码实现

Java

▼
Java
复制代码
// 无权图的边列表表示 class Edge { int source; // 边的起点 int destination; // 边的终点 public Edge(int source, int destination) { this.source = source; this.destination = destination; } } // 有权图的边列表表示 class WeightedEdge { int source; // 边的起点 int destination; // 边的终点 int weight; // 边的权重 public WeightedEdge(int source, int destination, int weight) { this.source = source; this.destination = destination; this.weight = weight; } } // 使用边列表表示的图 class Graph { int V; // 顶点数 List<Edge> edges; // 边列表 public Graph(int V) { this.V = V; edges = new ArrayList<>(); } // 添加边 public void addEdge(int source, int destination) { edges.add(new Edge(source, destination)); } // 打印所有边 public void printEdges() { for (Edge edge : edges) { System.out.println(edge.source + " -> " + edge.destination); } } }

Python

▼
Python
复制代码
# 无权图的边列表表示 class Edge: def __init__(self, source, destination): self.source = source # 边的起点 self.destination = destination # 边的终点 # 有权图的边列表表示 class WeightedEdge: def __init__(self, source, destination, weight): self.source = source # 边的起点 self.destination = destination # 边的终点 self.weight = weight # 边的权重 # 使用边列表表示的图 class Graph: def __init__(self, V): self.V = V # 顶点数 self.edges = [] # 边列表 # 添加边 def add_edge(self, source, destination): self.edges.append(Edge(source, destination)) # 打印所有边 def print_edges(self): for edge in self.edges: print(f"{edge.source} -> {edge.destination}")

JavaScript

▼
Javascript
复制代码
// 无权图的边列表表示 class Edge { constructor(source, destination) { this.source = source; // 边的起点 this.destination = destination; // 边的终点 } } // 有权图的边列表表示 class WeightedEdge { constructor(source, destination, weight) { this.source = source; // 边的起点 this.destination = destination; // 边的终点 this.weight = weight; // 边的权重 } } // 使用边列表表示的图 class Graph { constructor(V) { this.V = V; // 顶点数 this.edges = []; // 边列表 } // 添加边 addEdge(source, destination) { this.edges.push(new Edge(source, destination)); } // 打印所有边 printEdges() { for (const edge of this.edges) { console.log(`${edge.source} -> ${edge.destination}`); } } }

Go

▼
Go
复制代码
package main import "fmt" // Edge 无权图的边列表表示 type Edge struct { Source int // 边的起点 Destination int // 边的终点 } // WeightedEdge 有权图的边列表表示 type WeightedEdge struct { Source int // 边的起点 Destination int // 边的终点 Weight int // 边的权重 } // Graph 使用边列表表示的图 type Graph struct { V int // 顶点数 Edges []Edge // 边列表 } // NewGraph 创建新图 func NewGraph(v int) *Graph { return &Graph{ V: v, Edges: make([]Edge, 0), } } // AddEdge 添加边 func (g *Graph) AddEdge(source, destination int) { g.Edges = append(g.Edges, Edge{Source: source, Destination: destination}) } // PrintEdges 打印所有边 func (g *Graph) PrintEdges() { for _, edge := range g.Edges { fmt.Printf("%d -> %d\n", edge.Source, edge.Destination) } }

C++

▼
C++
复制代码
#include <iostream> #include <vector> // 无权图的边列表表示 class Edge { public: int source; // 边的起点 int destination; // 边的终点 Edge(int source, int destination) { this->source = source; this->destination = destination; } }; // 有权图的边列表表示 class WeightedEdge { public: int source; // 边的起点 int destination; // 边的终点 int weight; // 边的权重 WeightedEdge(int source, int destination, int weight) { this->source = source; this->destination = destination; this->weight = weight; } }; // 使用边列表表示的图 class Graph { private: int V; // 顶点数 std::vector<Edge> edges; // 边列表 public: Graph(int V) { this->V = V; } // 添加边 void addEdge(int source, int destination) { edges.push_back(Edge(source, destination)); } // 打印所有边 void printEdges() { for (const Edge& edge : edges) { std::cout << edge.source << " -> " << edge.destination << std::endl; } } };

优缺点

优点:

  • 实现简单,容易理解
  • 对于稀疏图,空间占用较小
  • 非常适合某些算法(如Kruskal最小生成树算法)

缺点:

  • 查找从某个顶点出发的所有边效率较低
  • 判断两个顶点之间是否有边需要遍历整个列表
  • 对于密集图,不如邻接矩阵或邻接表高效

应用场景

  • 执行基于边的图算法,如Kruskal最小生成树算法
  • 需要频繁遍历所有边的场景
  • 存储稀疏图且不需要频繁查询特定边的情况
  • 图的序列化和反序列化

测验

  1. 对于一个有5个顶点,7条边的无向图,如果使用边列表表示,边列表的长度是多少?
  2. 使用边列表表示一个有权图时,每条边通常需要存储哪些信息?
  3. 在边列表中,要判断图中是否存在环(cycle),需要怎样的算法复杂度?

测验答案

  1. 7条边。边列表直接存储每条边,所以列表长度等于边数。
  2. 起点、终点和权重三个信息,通常表示为三元组(u, v, weight)。
  3. 至少需要O(V+E)的复杂度,因为需要遍历所有边并使用额外算法(如并查集或DFS)来检测环。

相关的 LeetCode 热门题目