Graphs
由vertice與edge的集合所組成 --> a pair (V, E)
Edge type
1.Directed edge
2.Undirected edge
3.Directed graph
4.Undirected graphTerminology
1.Endpoint
一條edge的兩端點
2.incident
與某個vertice相鄰的點
3.Adjacent vertice
兩個點相鄰
4.Degree
某個vertice與幾個點相鄰
5.Parallel edge
兩個邊在同樣的兩端上
6.Self-loop
邊的兩端在同一個點上
7.Cycle
起點和終點一樣
simple cycle : 中間沒有經過重複的點Property
1.每個端點加起來，為edge的兩倍
2.若一個undirected graph沒有self-loop與multiple edge，則
m <= n(n-1)/2Data Structure of Graph
1.Edge-list structure
由edge找node很容易，但由node找edge很難
2.Adjacency-list structure
中間多一層incident list，對應到adjacency list
3.Adjacency-matrix structure
一個矩陣，若有相連則此格為1
-->浪費空間Performance
| Edge List | Adjacency List | Adjacency Matrix | |
|---|---|---|---|
| Space | n + m | n + m | n^2 |
| v.incidentsEdge() | m | deg(v) | n |
| u.isAdjacencyTo(v) | m | min(deg(u), deg(v)) | 1 |
| insertVertex(o) | 1 | 1 | n^2 |
| insertEdge(v, w, o) | 1 | 1 | 1 |
| eraseVertex(v) | m | deg(v) | n^2 |
| eraseEdge(e) | 1 | 1 | 1 |