6.1 图

邻接、关联
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)

路径、环路
路径π = <v₀, v₁, ..., v_k>
长度|π| = k
简单路径 若i ≠ j，则v_i ≠ v_j
环路 v₀ = v_k
有向无环图(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良好的空间控制策略，空间溢出等情况可透明处理
空间Θ(n²)，与边数无关
平面图(planar graph)，可嵌入平面的图，不相邻的边不相交

// 欧拉公式(Euler's formula)
v - e + f - c = 1, for any PG
// v，顶点数
// e，边数
// f，区域面片数
// c，连通域数

平面图e ≤ 3n - 6 = O(n) << n²，此时空间利用率约1/n