图(graph) 是最底层的数据结构，其他所有数据结构的本质都是一张图，都是由节点和节点之间的位置关系决定的数据结构的性质。
节点也被称为顶点(Vertex) 是图的基本单位，通常会存储一个对象或者实体，图中的节点通过边连接起来构成一张图
class Node{
/*
*这里的obj对象可以是任意对象或者数据
*比如存储一个Student类，或者存储一个int型整数
*/
Object obj;
/*
*每个节点都通过边的关系与其他节点连接起来
*/
vector<Edge> edges;
}
边(Edge) 是用来表示图中的点直接的关系的对象，通常会存储 出发节点和目标节点以及边的权重 。
class Edge{
/*
*用来储存边的权重
*/
double weight;
/*
*表示边的出发节点
*/
Node start;
/*
*表示边的终点
*/
Node end;
}
图 可以根据边的属性分成不同种类的图，但本质上，边和节点的属性是相同的，只是由于不同的定义和使用场景而有所区分。
无权图 是指边没有权重或者所有边的权重被视为等同。无权图通常用于表示纯连接关系，而不涉及任何与边相关的数值信息。
如果图中每条边的权重都相同，那么这个图可以被看成是一个无权图
class Edge{
/*
*每条边的权重都相同
*/
static const double EDGE_WIGHT;
/*
*表示边的出发节点
*/
Node* start;
/*
*表示边的终点
*/
Node* end;
}
有权图 是指存在不同权重的边的图。有权图通常可以用于表示非纯连接关系 ，会涉及与边相关的数值信息
class Edge{
/*
*存在不同权重的边
*/
double weight;
/*
*表示边的出发节点
*/
Node* start;
/*
*表示边的终点
*/
Node* end;
}
无向图 是指图中每对有连接关系的节点都互为终点
数学表示
∀
E
d
g
e
(
u
,
v
,
w
)
∈
G
r
a
p
h
→
E
d
g
e
(
v
,
u
,
w
)
∈
G
r
a
p
h
\forall Edge_{(u,v,w)} \in Graph \to Edge_{(v,u,w)} \in Graph
∀Edge(u,v,w)∈Graph→Edge(v,u,w)∈Graph
无向图的示例
a<---->b<---->c (每个双向链表都可以看成一个无权无向图)
等效
a ----- b ----- c
有向图 是指图中不是每对有连接关系的节点都互为终点
数学表示
∃
E
d
g
e
(
u
,
v
,
w
)
∈
G
r
a
p
h
→
E
d
g
e
(
v
,
u
,
w
)
∉
G
r
a
p
h
\exists Edge_{(u,v,w)} \in Graph \to Edge_{(v,u,w)} \notin Graph
∃Edge(u,v,w)∈Graph→Edge(v,u,w)∈/Graph
有向图的示例
a---->b---->c (每个单向链表都可以看成一个无权有向图)
对于这个有向图
∃
(
a
,
b
)
∈
G
r
a
p
h
→
(
b
,
a
)
∉
G
r
a
p
h
\exists (a,b) \in Graph \to (b,a) \notin Graph
∃(a,b)∈Graph→(b,a)∈/Graph
度(Degree) 指的是某个节点直接相连的边数
示例
考虑一个 无向图 G
A B
| |
C —— D
这里A的度就是 1，C的度就是 2
出度 指的是有向图中的从某一个节点出发的边的个数
示例
考虑一个 无向图 G
A B
^ ^
| |
v |
C —— >D
这里C的出度是1
入度 指的是有向图中指向某个节点的边的个数
示例
考虑一个 无向图 G
A B
^ ^
| |
v |
C —— >D
这里C的入度是1
边数 指的是图中的边的个数和
对于无向图，所有顶点的度之和等于边数的两倍。
∑ v ∈ G d e g ( v ) = 2 ∣ E ∣ \sum_{v \in G}deg(v)=2 |E| v∈G∑deg(v)=2∣E∣
对于一个有向图，所有顶点的出度之和等于所有顶点的入度之和，且都等于边的数量。
∑ v ∈ G d e g + ( v ) = ∑ v ∈ G d e g − ( v ) = ∣ E ∣ \sum_{v \in G}deg^+(v)=\sum_{v \in G}deg^-(v)= |E| v∈G∑deg+(v)=v∈G∑deg−(v)=∣E∣