圖的概念

完全圖

無向圖的完全圖可以這么想：如果有4個點，每個點都會連向3個點，每個點也都會有來回的邊，所以除以2

有向圖就不用除以2

連通分量

不多解釋

極大連通子圖的意思就是讓你把所有連起來的都圈出來?

強連通圖和強連通分量

這個是特指有向圖的，有向圖很強?

入度，出度

每個邊算2次，一條邊就是出度和入度

?并且等于邊數

?題目

1

bro，你是不是想 7-1 = 6？?

那你完了，這里有個狗屎關鍵詞? 任何情況下? ，要考慮最壞的

那你是不是想（7 * 6）/2 = 21

那你完了，因為題目還有個狗屎關鍵詞 最少

所以正確的思路就是，你其他6個頂點全部都拉滿了，最后再多一條連到第七個頂點，這樣你再怎么陰間操作，你都不可能孤立任何一個頂點

所以是（5*6）/2 + 1 = 16

c

2

這個性質記下，這里是至少?

a?

3

（4*5）/2 + 1 = 11

一樣，無論你怎么針對，都能連到一起去?

d

4

A ： 16條就一定連通了

B ： 22條就一定連通了

C：? 29條才連通?，又要至少，所以選C

5

均小于3，又要頂點最少，那可以把他們的度全變成2來保證頂點的個數最少

b

6

?其實從上面的題可以知道，連通的條件很苛刻的

所以舉例子就知道了

選D ， 6 > 4+1, 6個頂點5條就能連通，但這里最多才4條

圖的存儲

鄰接矩陣

看圖就行了

每個頂點的出度是看行的，入度是看列的?

無向圖的鄰接矩陣是對稱的（并且唯一）

對稱的不一定是無向圖，但不對稱的一定不是無向圖

無向圖每行和對應的每列 度是一樣的，也就是出度和入度一樣

因為存很多0沒有意義，誰是0

鄰接表

有向圖只看出度

其他的十字鏈表什么的最終季再說，各種代碼也是

題目

1

出度是看行的，入度是看列的

c

圖的遍歷

這小結只考過選擇題，沒有代碼題

這里廣度優先，從2開始的，第一層先是1和6，第二層對應著1的5和6的3，7，第三層對應著5沒有，3是4，7是8

當然是不唯一的，還可以這樣

然后是深度遍歷

深度遍歷就是愣頭青，一直沖

一開始是2，隨便走1還是6，這里走1，然后是5，然后回去回到1再回到2 ，此時已經記下了215

然后2還有方向走6，6這里走3還是7都行，我們走3，3這里走4還是7都行，我們走7，然后走8，然后走4，然后原路返回就行

題目

1

a應該是bhf?

d?

2

自己走，愣頭青?

d