图Graph

基本认知Basic

是什么

巨大的 ADT

概念

边 Edge

点 Vertex

有向 Directed / 无向 Undirected

有重量 Weighted / 无重量 Unweighted

平行边 Parrallel / 自环 Self loop

用途

路径名词

路径 / Path

路径长度

简单路径 / Path

环 / Cycle

密度名词

紧密 / Dense

松散 / Sparse

联通性名词

连通 / Connected

不连通 / Not connected

连通组件 / Connected Components

完全连通 / Fully Connected / Complete Graph / Clique

强连通 / strongly connected

数据结构Data Structure

邻接矩阵

用二维数组表达

    A   B   C   D   E
A       2   6
B   2           3
C   6           8
D       3   8       2
E               2

自测

1. 能否表达 平行边 / 自环

2. 能否表达 有向图 / 无向图

3. 能否表达 有重量图 / 无重量图

4. 一个点 是否 直接连接另外一个点，T(n)

邻接列表

用 array + List

A [ -]->    <C, B>
B [ -]->    <A, D>
C [ -]->    <A, D>
D [ -]->    <B, C, E>
E [ -]->    <D>

自测

1. 能否表达 平行边 / 自环

2. 能否表达 有向图 / 无向图

3. 能否表达 有重量图 / 无重量图

4. 一个点 是否 直接连接另外一个点，T(n)

纯二维数组

纯 Link

构建

手动构建