学好图论第一步，要先明确各个概念

有向图：

弧：<vi，vj> 表示一条从 vi 到 vj 的弧。 顶点集： V={V1,V2,V3,V4} 顶点关系集合： VR=<V2,V1>,<V1,V3>,<V2,V3>,<V3,V4> 顶点的度：出度 + 入度（如 V3 的入度为 2 ， 出度为 1 ，则它的度是 3） 完全有向图：n个顶点 ----- n(n-1) 条边

无向图：

边：(vi，vj) 表示一条从 vi 与 vj 之间的边。 顶点集： V=V1,V2,V3,V4 顶点关系集合： VR=（V1,V2）,（V1,V3）,（V2,V3）,（V3,V4） 顶点的度：与该顶点相连的边 完全无向图：n个顶点 ----- n(n-1)/2 条边

权值：

顶点和边都有一定属性，而量化的属性叫权值，顶点的权值和边的权值分别叫做点权和边权。

重边和自环

重边：两条边有相同的两端点。 自环：一条边的两端点相同。

简单图

简单图：没有自环和重边的图

连通图：

连通：两个顶点之间存在通路，则称这两个点是连通的。 环：从起点出发经过一条路径又回到起点。 强连通图：从所有顶点都存在路径到达其他顶点。

注意：一般情况下，如果说一个图是连通图，基本上就等同于说它是一个强连通图。

n 个顶点的无向图，构成强连通图，最少需要 n-1 条边。 n 个顶点的有向图，构成强连通图，最少需要 n 条有向边。

欧拉路（一笔画）：

定理1：存在欧拉路的条件：图是连通的，有且只有 2 个奇点（度数为奇数的点）。 定理2：存在欧拉回路的条件：图是连通的，有 0 个奇点。

遍历：

深度优先遍历：0-1-3-7-4-2-5-6 （用到的数据结构：栈） 广度优先遍历：0-1-2-3-4-5-6-7（用到的数据结构：队列）

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com