\(G=(V,E)\)

- Two standard ways to represent a graph, adjacency
`list`

or`matrix`

. - Adjacency list is more compact to represent
`sparse`

graphs, whose \(|V|^2\) is much more than \(|E|\). But when \(|V|^2\) is close to \(|E|\), like`dense`

graphs, or you need to check edges quickly, adjacency matrix is prefered. - Graphs could be
`directed`

or`undirected`

. If edge (u,v) exists in u's adjacency list of an undirected graph, edge (v,u) must also exist in v's adjacency list. - \(A=A^T\) for adjacency matrix representation. Memory could be cut to half.
`DAG`

: Directed Acyclic Graph.`BFS`

: Breadth-First Search (queue).`DFS`

: Depth-First Search.- An undirected graph is
`connected`

if there is a path from every vertex to every other vertex. A directed graph with this property is called`strongly connected`

. If a directed graph is not strongly connected, but the underlying graph (without direction to the arcs) is connected, then the graph is said to be`weakly connected`

. A`complete graph`

is a graph in which there is an edge between every pair of vertices.

-- 目录[0] --

-- 文章[1] --