Tree and Graph

在开始今天的主题之前，要先来浅谈Tree跟Graph。什麽是Tree？

Tree

1. Tree 是一种特定的Graph，没有Loop
2. Tree 只有唯一的Root

Graph

1. Graph是一种抽象资料类型
2. Graph是一个有限集合
3. 点跟点相连的线称为「edges」，edges分为有方向性(Directed Graph)或无方向性(Undirected Graph)

有向图(Directed Graph)

有向图顾名思义是在图形中表示某个边的单边通行，有时候会在边上加上权重。实际应用於网页连结等等。

无向图(Undirected Graph)

无向图跟有向图差别在没有方向，但也可以设定权重。

广度优先搜寻(breadth-first search(BFS))

最初假设自己在某个顶点（称为起点）。目的是从起点经由边搜寻顶点，直到找到目标顶点。抵达顶点时，可以判定这个顶点是否为目标顶点，广度优先搜寻在搜寻顶点时，优先搜寻离起点较近的顶点

顶点选项：「先进先出」(FIFO)，所以可以用「伫列」的资料结构

有可能是封闭回圈（closed circuit)，也就是回圈上起点和终点在同一个路径的状态，若非封闭回圈形式，则称为「树」(tree)