若無向圖G =（V，E）中含7個頂點，要保證圖G在任何情況下都是連通的，則需要的邊數最少是：
A.6
B.15
C.16
D.21

(n-1)*(n-2)/2+1

6 * 5/2+1=16

設無向圖的頂點個數為N，則該圖最多有多少條邊？
A.N?1
B.N(N?1)/2
C.N(N+1)/2
D.N?2
?

用鄰接表法存儲圖，占用的存儲空間數只與圖中結點個數有關，而與邊數無關。（F） (1分)

解析：使用鄰接表占用空間與這個圖是有向圖還是無向圖有關。

如果是無向圖，那么空間就是n+2e;如果是有向圖就是n+e。（n為節點數，e為邊數）。

用鄰接矩陣法存儲圖，占用的存儲空間數只與圖中結點個數有關，而與邊數無關==（T）==。 (1分)

解析：鄰接矩陣G[x][y]表示x->y這條邊的權重，因此n各節點需要兩兩組合，空間大小為n^2。

如果無向圖G必須進行兩次廣度優先搜索才能訪問其所有頂點，則G中一定有回路。==（F） ==(2分)

解析：因為不論是bfs還是dfs我們在遍歷的時候都進行了標記也就是當一個節點被標記了的時候這個節點就不會重復訪問。

因此兩次bfs才訪問完所有的節點不是因為有回路而是因為這個圖有兩個連通分量。

如果無向圖G必須進行兩次廣度優先搜索才能訪問其所有頂點，則G一定有2個連通分量。（T）

設N個頂點E條邊的圖用鄰接表存儲，則求每個頂點入度的時間復雜度為： (2分)
O(N)
O(N?2??)
O(N+E)
O(N×E)

解析：鄰接表求入度需要遍歷整個鄰接表也就是n+e，而求出度是n。

在N個頂點的無向圖中，所有頂點的度之和不會超過頂點數的多少倍？ (2分)
1
2
(N?1)/2
N?1

解析：形成一棵樹。

對于一個具有N個頂點的無向圖，要連通所有頂點至少需要多少條邊？ (2分)
N?1
N
N+1
N/2

具有N（N>0）個頂點的無向圖至多有多少個連通分量？ (2分)
0
1
N?1
N

解析：無邊

一個有N個頂點的強連通圖至少有多少條邊？ (2分)
N?1
N
N+1
N(N?1)

解析：無向圖有n-1個即可，有向圖需要加一個形成環。

對于有向圖，其鄰接矩陣表示比鄰接表表示更易于： (2分)
求一個頂點的入度
求一個頂點的出邊鄰接點
進行圖的深度優先遍歷
進行圖的廣度優先遍歷

https://blog.csdn.net/qq_43446165/article/details/102841019

總結

以上是生活随笔為你收集整理的图 无向图 有向图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。