Definition
| A | B |
|---|---|
| Graph | G = (V, E), v,w V, (v,w) E |
| directed | (v, w) is ordered |
| ajacent | (v, w) |
| weight/cost | edge |
| path | w1, w2, …, wn, length n-1 |
| loop | (v, v) |
| simple path | all vertices are distince, except first and last |
| cycle | directed, w1 = wn |
| DAG | directed acyclic graph |
| connected | path from every vertex to other |
| strongly connected | directed |
| weakly connected | directed is not strongly connected, underlying graph is connected |
| complete graph | edge between every vertices pair |
Representation
| A | B | space | C |
|---|---|---|---|
| adjacency matricx | A[u][v] = true/false/weight/Infinite | O(|V| ^2) | dense: | E| = O( | V | ^2) |
| adjacency list | vertex -> a list of all adjacent vertices | O(|E| + |V|) | sparse: not dense |
- adjacency lists are the standard way to represent graphs
近期评论