图论基础概念（详细讲解)

今天，我们讲解一下图论的概念，首先我们知道图是一个什么东西。

图你可以理解成一个网络系统，两个节点之间可能会有边，边链接两个节点，可能是有向（就比如说a只能往b,或者b只能往c)，可能是无向（就是相当于没有方向，如果a和b有一条无向边的话，a可以往b，b可以往a)，一条边可能有长度，我写一些图论题目常见的用词：
1.有向边：上面说了，他是有方向的，比如说a到b的有向边不能由b到a

2.无向边：上面说了，就是只要连上了两个都能到达

3.边权：代表边的长度，有些图可能不需要考虑边长，比如说判断两点是否可达这种问题是没有边权的。

4.反向边：只对有向边有效，比如说a->b,他的反向边就是b->a

5.重边:出现了两条一模一样的边，可能会影响后面的算法，所以说要注意（不过一般来讲，基础题是保证了没有重边，不过仍然需要注意）

6.自环：自己向自己连一条边，这种情况和重边一样的，也会影响算法，甚至可能让一些算法卡住。

7.链：对于任意一个节点，他们当中没有分叉，比如说这种：1->2,2->3这种，就有点像一条直线。这种数据可能需要小心，因为有些算法会在链上退化（比如说像BST(二叉搜索树）)，不过有时候骗分的时候也可以特判链的情况。

8 .环：相当于把链的首尾相接，有时候环也会卡住。

9.树：这种数据比较友好，一些图的算法不会在上面退化，反倒还容易骗分一些，定义是：由n个节点和n-1条组成的无向无环图。

10.菊花图：就是所有点都连到了一个点，形成了一朵"菊花"，有些算法会在上面退化，比如说spfa算法的O(km)会在菊花图的情况下变成O(nm)（这里一定要注意这种情况，以前NOI曾经有人写了spfa被菊花图卡了）

11.蒲公英图：菊花图和链组成起来，也会让一些算法退化。

12.负权/负权边：意思说一条边的权值为负数，这回让一些算法出问题（例如dijkstra最短路)，这种时候必须要spfa算法了（当然不止这些，还有一些其他的算法也会在负权边上出问题）。

13.负权回路/负环：相当于一个环里所有数为负数，为让最短路算法卡进去（包括spfa)，遇到负环可能需要用spfa判断负环.

14.正权回路/正环：根负环一样的，只不过是正数，这也会让求最长路时出问题

15.连通图：图是联通的，对于任意两点，他们都有一条路径。

16.点权：有一些题目，他不是边有长度，而是经过一个点有点权（比如说我经过一个点需要支付多少钱啊这种的），一般来讲，树形dp一般是没有边权而是点权。