n-e

45

線性結構中,數據元素之間存在一對一的關系
樹形結構中,數據元素之間存在一對多的關系
圖形結構中,數據結構之間存在多對多的關系

9

n-1

有向圖中的極大強連通子圖稱為連通分量

有向圖中,如果從A到B之間都有路徑,則稱這兩個頂點是強連通的
任意頂點之間都是強連通的,則成為強連通圖
有向圖中的極大強連通子圖稱為有向圖的強連通分量

n

1

n
圖可以沒有邊,但是不能沒有頂點

n-1

n
連通圖的生成樹:包含圖中全部頂點的一個極小連通子圖(既要包含全部的頂點,又要使得邊最少,n個頂點,n-1條邊)
所以,為一個環,依次斷開所有的邊,共有n種生成樹

N-1

若無向圖滿足n個頂點,n-1條邊的無向連通圖,則這個無向連通圖是一棵樹

n
對答案有疑問

0 N

2(N-1)
無向圖的鄰接矩陣是對稱的,如果有n條邊,那么就對應鄰接矩陣中的2n個非零點

4

將第i行的非零元素全部置零

n-1

m/2

O(n+e)

查找頂點的鄰接點的過程
O(n+e) 采用的是(鄰接表)
O(n+e)
BFS和DFS的時間復雜度,在鄰接表和鄰接矩陣中是相同的
不同之處在于,訪問頂點的順序不同
數據結構上的區別是,一個是使用隊列,另一個是使用棧

深度優先
當一個頂點的周圍沒有任何一條出路的時候,就需要進行回溯

廣度優先

隊列

Prim算法,Kruskal算法

克魯斯卡爾算法

轉載于:https://juejin.im/post/5ba1050c5188255c713c7ad8

總結

以上是生活随笔為你收集整理的算法与数据结构1800题 图的全部內容，希望文章能夠幫你解決所遇到的問題。

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