有的圖中，任二點之間都可沿連線通達，這樣的圖稱為連通圖。一個不連通的圖，可分成若干個連通的子圖。

有的圖中含有圈，即存在某些連線組成了圈，從某個點出發，沿著這些連線又能回到該點。

凡連通且不含有圈的圖，稱為樹。例如，A，B，C三個點之間有連線(A，B)和(B，C)時就成為樹。樹中的線數必然等于其點數與1的差。

對于一個連通圖，可以選擇其中的一些連線形成樹。最直觀、簡單的方法是用逐步生成法來形成樹。從任何一點出發，選擇連線將未連接的點逐點連上，只要注意在選擇連線時不要形成圈。當選擇的連線將所有的點都接通時，就生成了樹。

對于同樣的一些點，用不同的連線可以形成不同的樹，但這些樹中的線數都是一樣的，都等于點數減1。例如，A，B，C三個點之間有連線(A，B)和(A，C)時也成為樹，但線數還是2。

在任一樹中，如果再增加任何一條連線，則一定會變得不連通，它不再是樹了。

在任一樹中，任何兩個結點之間一定有而且只有一條通路。

在N個點的連通圖中，樹是連線數目最少的。反之亦然。用最少的連線數目將N個點連通，則它一定形成樹。

數據結構中的樹也符合圖論中樹的定義。

本節考核點

樹和樹的逐步生成法，達到簡單應用層次。