- 樹(shù)沒(méi)有環(huán)
- 樹(shù)上所有點(diǎn)都互相連通
- 沒(méi)有環(huán)的圖,就是tree或forest
- 沒(méi)有環(huán)的圖食磕,連通的圖,就是樹(shù)
- 任意兩點(diǎn)之間只有唯一一條路徑
- 在樹(shù)上任加一條邊,就會(huì)產(chǎn)生環(huán)
- 在樹(shù)上任刪一條邊且改,一棵樹(shù)就會(huì)裂成兩棵樹(shù)
-
邊數(shù)等于點(diǎn)數(shù)減一
樹(shù)是一種圖。圖的資料結(jié)構(gòu)adjacency matrix, adjacency lists可以儲(chǔ)存一棵樹(shù)板驳。 一棵樹(shù)剛好V個(gè)點(diǎn)又跛,V-1條邊。 Adjacency list的空間復(fù)雜度是O(V+E) - O(V)