图论：图的相关定义
图
图(graph) 是最底层的数据结构，其他所有数据结构的本质都是一张图，都是由节点和节点之间的位置关系决定的数据结构的性质。
1. 定义
1.1 节点
节点也被称为顶点(Vertex) 是图的基本单位，通常会存储一个对象或者实体，图中的节点通过边连接起来构成一张图
class Node{
/*
*这里的obj对象可以是任意对象或者数据
*比如存储一个Student类，或者存储一个int型整数
*/
Object obj;
/*
*每个节点都通过边的关系与其他节点连接起来
*/
vector edges;
}
1.2 边
边(Edge) 是用来表示图中的点直接的关系的对象，通常会存储 出发节点和目标节点以及边的权重 。
class Edge{
/*
*用来储存边的权重
*/
double weight;
/*
*表示边的出发节点
*/
Node start;
/*
*表示边的终点
*/
Node end;
}
1.3 图的分类
图 可以根据边的属性分成不同种类的图，但本质上，边和节点的属性是相同的，只是由于不同的定义和使用场景而有所区分。
1.3.1 无权图
无权图 是指边没有权重或者所有边的权重被视为等同。无权图通常用于表示纯连接关系，而不涉及任何与边相关的数值信息。
如果图中每条边的权重都相同，那么这个图可以被看成是一个无权图
class Edge{
/*
*每条边的权重都相同
*/
static const double EDGE_WIGHT;
/*
*表示边的出发节点
*/
Node* start;
/*
*表示边的终点
*/
Node* end;
}
1.3.2 有权图
有权图 是指存在不同权重的边的图。有权图通常可以用于表示非纯连接关系 ，会涉及与边相关的数值信息
class Edge{
/*
*存在不同权重的边
*/
double weight;
/*
*表示边的出发节点
*/
Node* start;
/*
*表示边的终点
*/
Node* end;
}
1.3.3 无向图
无向图 是指图中每对有连接关系的节点都互为终点
数学表示
∀ 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
无向图的示例
abc (每个双向链表都可以看成一个无权无向图)
等效
a ----- b ----- c
1.3.4 有向图
有向图 是指图中不是每对有连接关系的节点都互为终点
数学表示
∃ 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
1.4 度(Degree)
度(Degree) 指的是某个节点直接相连的边数
示例
考虑一个 无向图 G
A B | | C —— D
这里A的度就是 1，C的度就是 2
1.4.1 出度(Out-Degree)
出度 指的是有向图中的从某一个节点出发的边的个数
示例
考虑一个 无向图 G
A B ^ ^ | | v | C —— >D
这里C的出度是1
1.4.2 入度(In-Degree)
入度 指的是有向图中指向某个节点的边的个数
示例
考虑一个 无向图 G
A B ^ ^ | | v | C —— >D
这里C的入度是1
1.5 边数
边数 指的是图中的边的个数和
对于无向图，所有顶点的度之和等于边数的两倍。
∑ 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∣
