图论:图的概念、存储和遍历 学习笔记

发布时间 2023-07-01 13:59:23作者: 蒟蒻OIer-zaochen

图论

图的概念

从数据结构的角度看,图可以看作一个多对多的数据存储结构。而结合图论算法,图就可以成为很多问题的载体。图论是数据结构与算法结合的产物。

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;

拓展阅读 && 参考资料 && 推荐题目

  1. 图论部分简介 - OI Wiki