今天，我們講解一下圖論的概念，首先我們知道圖是一個什么東西。

圖你可以理解成一個網絡系統，兩個節點之間可能會有邊，邊鏈接兩個節點，可能是有向（就比如說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一般是沒有邊權而是點權。