边列表是表示图的一种简单方式,通过存储所有边的信息(起点、终点和权重)来表示图结构。适用于边数较少的稀疏图,特别适合需要频繁查询和操作边的应用场景。
边列表是图论中最基础的图表示方式之一,它通过存储图中的每条边来描述整个图的结构。对于无权图,每条边表示为一个顶点对(u, v);对于有权图,则表示为三元组(u, v, weight)。
边列表(Edge List)是表示图的一种简单数据结构,在理解它之前,我们需要先了解一些基础图论概念:
图(Graph):由顶点(Vertex)和连接顶点的边(Edge)组成的数据结构。图可以用来表示现实世界中的各种关系,如社交网络、交通路线等。
顶点(Vertex):图中的节点,通常用数字或字母标识,如 0, 1, 2... 或 A, B, C...
边(Edge):连接两个顶点的线段,表示它们之间存在某种关系。
度(Degree):指与该顶点相连的边的总数。
图根据不同特性可以分为几种类型:
无向图 vs 有向图:
在有向图中,度分为入度和出度:
入度(In-degree):指向该顶点的边的数量。
出度(Out-degree):从该顶点指出的边的数量。
无权图 vs 有权图:
边列表的存储方式:
示例:
假设有一个包含 4 个顶点 (0, 1, 2, 3) 的有权图,边的信息如下:
则其边列表表示为:[(0,1,5), (0,2,3), (1,2,2), (2,3,7)]
边列表虽然概念简单,但在某些算法(如 Kruskal 最小生成树算法)中具有明显优势,因为这些算法需要对所有边进行排序并逐一处理。
▼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复制代码# 无权图的边列表表示 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复制代码// 无权图的边列表表示 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复制代码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++复制代码#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; } } };
优点:
缺点:
测验答案
- 7条边。边列表直接存储每条边,所以列表长度等于边数。
- 起点、终点和权重三个信息,通常表示为三元组(u, v, weight)。
- 至少需要O(V+E)的复杂度,因为需要遍历所有边并使用额外算法(如并查集或DFS)来检测环。