图论
图的概念
从数据结构的角度看,图可以看作一个多对多的数据存储结构。而结合图论算法,图就可以成为很多问题的载体。图论是数据结构与算法结合的产物。
OI Wiki 上给出的图相关概念比较全面,但是因为 OI 是民科各个地方的一些定义都不太一样,所以作大概了解即可。
图的存储
图的存储常用下面几种方式。
边目录。通常情况下,题目数据都是直接给出边的起点,终点和边权(如果有),则可以直接存储这些信息来存图。
int n, m; // 图的点数和边数
struct edge{
int u,v,l; // 一条从 u 到 v 权为 l 的边
} e[M];
cin >> n >> m;
for (int i=1;i<=m;i++) cin >> e[i].u >> e[i].v >> e[i].l;