边列表
介绍
边列表是图论中最基础的图表示方式之一,它通过存储图中的每条边来描述整个图的结构。对于无权图,每条边表示为一个顶点对(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。
...