Graph

\(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] --