邻接、关联
G = (V; E)，vertex: n = |V|，edge | arc: e = |E|
同一边的两个顶点彼此邻接(adjacency)
同一顶点自我邻接，构成自环(self-loop)
不含自环为简单图(simple graph)
顶点与其所属边彼此关联(incidence)
与同一顶点关联的边数称作度(degree / valency)
无向、有向
若邻接顶点u与v次序无所谓，则(u, v)为无向边(undirected edge)
所有边均无方向的图为无向图(undigraph)
有向图(digraph)中均为有向边(directed edge)，u、v分别称作边(u, v)的尾(tail)、头(head)
无向边、有向边并存的图，称作混合图(mixed graph)
路径、环路
路径π = <v0, v1, ..., vk>
长度|π| = k
简单路径 若i ≠ j，则vi ≠ vj
环路 v0 = vk
有向无环图(DAG, Directed Acyclic Graph)
欧拉环路(Eulerian tour) |π| = |E|，各边恰好出现一次
哈密尔顿环路(Hamiltonian tour) |π| = |V|，各顶点恰好出现一次
Graph模板类
template <typename Tv, typename Te> class Graph { // 顶点类型、边类型
private:
void reset() { // 所有顶点、边的辅助信息复位
for (int i = 0; i < n; i++) { // 顶点
status(i) = UNDISCOVERED;
dTime(i) = -1;
fTime(i) = -1;
parent(i) = -1;
priority(i) = INT_MAX;
for (int j = 0; j < n; j++) // 边
if (exists(i, j))
status(i, j) = UNDETERMINED;
}
}
public:
/* ... 顶点操作、边操作、图算法 ... */
}
邻接矩阵(adjacency matrix)，以二维矩阵记录顶点之间的邻接关系
关联矩阵(incidence matrix)，以二维矩阵记录顶点与边之间的关联关系
顶点
typedef enum {UNDISCOVERED, DISCOVERED, VISITED} VStatus;
template <typename Tv> struct Vertex { // 顶点对象（未严格封装）
Tv data; // 数据
int inDegree; // 出度
int outDegree; // 入度
VStatus status; // 状态
int dTime;
int fTime; // 时间标签
int parent; // 在遍历树中的父节点
int priority; // 在遍历树中的优先级（最短通路、极短跨边等）
Vertex(Tv const & d): // 构造新顶点
data(d), inDegree(0), outDegree(0), status(UNDISCOVERED), dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {}
};
边
typedef enum {UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD} EStatus;
template <typename Te> struct Edge { // 边对象（未严格封装）
Te data; // 数据
int weight; // 权重
EStatus status; // 类型
Edge(Te const & d, int w): // 构造新边
data(d), weight(w), status(UNDETERMINED) {}
};
GraphMatrix
template<typename Tv, typename Te> class GraphMatrix: public Graph<Tv, Te> {
private:
Vector<Vertex<Tv>> V; // 顶点集
Vector<Vector<Edge<Te>*>> E; // 边集
public:
/* 操作接口：顶点相关、边相关… */
GraphMatrix() { // 构造
n = 0;
e = 0;
}
~GraphMatrix() {
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
delete E[j][k]; // 清除所有动态申请的边记录
}
};
顶点静态操作
Tv & vertex(int i) { // 数据
return V[i].data;
}
int inDegree(int i) { // 入度
return V[i].inDegree;
}
int outDegree(int i) { // 出度
return V[i].outDegree;
}
Vstatus & status(int i) { // 状态
return V[i].status;
}
int & dTime(int i) { // 时间标签dTime
return V[i].dTime;
}
int & fTime(int i) { // 时间标签fTime
return V[i].fTime;
}
int & parent(int i) { // 在遍历树中的父节点
return V[i].parent;
}
int & priority(int i) { // 优先级数
return V[i].priority;
}
int nextNbr(int i, int j) { // 若已枚举至相邻顶点j，则转向下一相邻顶点
while ((-1 < j) && !exists(i, --j)); // 逆向顺序查找
return j;
}
int firstNbr(int i) { // 首个相邻顶点
return nextNbr(i, n);
}
边操作
bool exists(int i, int j) { // 判断边(i, j)是否存在
return (0 <= i) && (i < n) && (0 <= j) && (j < n) && E[i][j] != NULL; // 短路求值
}
Te & edge(int i, int j) { // 边(i, j)的数据
return E[i][j] -> data;
}
Estatus & status(int i, int j) { // 边(i, j)的状态
return E[i][j] -> status;
}
int & weight(int i, int j) { // 边(i, j)的权重
return E[i][j] -> weight;
}
void insert(Te const& edge, int w, int i, int j) { // 插入(i, j, w)
if (exists(i, j)
return; // 忽略已有边
E[i][j] = new Edge<Te>(edge, w); // 创建新边
e++; // 更新边计数
V[i].outDegree++; // 更新关联顶点i的出度
V[j].inDegree++; // 更新关联顶点j的入度
}
Te remove(int i, int j) { // 删除顶点i与j之间的联边
Te eBak = edge(i, j) // 备份边(i, j)的信息
delete E[i][j];
E[i][j] = NULL; // 删除边(i, j)
e--; // 更新边计数
V[i].outDegree--; // 更新关联顶点i的出度
V[j].inDegree--; // 更新关联顶点j的入度
return eBak; // 返回被删除边的信息
}
顶点动态操作
int insert(Tv const & vertex) { // 插入顶点，返回编号
for (int j = 0; j < n; j++) {
E[j].insert(NULL);
n++;
}
E.insert(Vector<Edge<Te>*>(n, n, NULL));
return V.insert(Vertex<Tv>(vertex));
}
Tv remove(int i) { // 删除顶点及其关联边，返回该顶点信息
for (int j = 0; j < n; j++) {
if (exists(i, j)) { // 删除所有出边
delete E[i][j];
V[j].inDegree--;
}
}
E.remove(i);
n--; // 删除第i行
for (int j = 0; j < n; j++) {
if (exists(j, i)) { // 删除所有入边及第i列
delete E[j].remove(i);
V[j].outDegree--;
}
}
Tv vBak = vertex(i); // 备份顶点i的信息
V.remove(i); // 删除顶点i
return vBak; // 返回被删除顶点的信息
}
邻接矩阵
直观，易于理解与实现
适用范围广(digraph / network / cyclic / ...)，尤其适用于稠密图(dense graph)
判断两点之间是否存在联边O(1)
获取顶点出/入度数O(1)
添加、删除边后更新度数O(1)
扩展性(scalability)，得益于Vector良好的空间控制策略，空间溢出等情况可透明处理
空间Θ(n2)，与边数无关
平面图(planar graph)，可嵌入平面的图，不相邻的边不相交
// 欧拉公式(Euler's formula)
v - e + f - c = 1, for any PG
// v，顶点数
// e，边数
// f，区域面片数
// c，连通域数
平面图e ≤ 3n - 6 = O(n) << n2，此时空间利用率约1/n
网友评论