图的存储与遍历 – Victor’s Blog

图的存储与一般有三种形式，邻接矩阵、邻接表、链式前向星（邻接表的一种）。本文全文使用这个图来进行演示。我们规定，一共有 $n$ 个点，$m$ 条边。输入数据的格式为 “起点”、“终点”、“边权”。则这个图的输入数据为:

邻接矩阵

由于邻接矩阵空间消耗巨大，一般不使用。邻接矩阵初始化时，我们使用无穷。 #define INF LLONG_MAX typedef long long ll; const int MAXN = 1000 + 1; ll adj_matrix[MAXN][MAXN]; // 邻接矩阵声明，若为不带权图，则可以将 long long 改为 bool. inline void addEdge(int prev, int next, ll w = 1) { // 加边，默认为有向图，边权默认为 1，便于使用不带权图 adj_matrix[prev][next] = w; } void init(int maxn, bool is_zero = false) { // 初始化 if (is_zero) return; // 若初始化为 0 则直接退出 for (int i = 1; i <= maxn; i++) // 外循环 for (int j = 1; j <= maxn; j++) { // 内循环 if (i == j) continue; // 若起点终点则初始化为 0 adj_matrix[i][j] = INF; // 否则初始化为无穷大 } } void read(int const m, bool directed = true, bool have_weight = true) { // m 为数据组数，即边数，directed 为是否有向，have_weight 为是否带权 int a = 0, b = 0, w = 1; // 声明变量 for (int i = 1; i <= m; i++) { // 开始读入数据 scanf( if (have_weight) scanf( addEdge(a, b, w); // 加边 if (!directed) addEdge(b, a, w); // 若不带方向，即为无向图，添加反向边 } } void traversal(int amount_of_vertexes) { // 遍历，传入参数为点数 for (int i = 1; i <= amount_of_vertexes; i++) for (int j = 1; j <= amount_of_vertexes; j++) { if (i == j) continue; if (adj_matrix[i][j] != INF) ; //操作一下 } }

下面我们将介绍一种更加优越的存储方式。

邻接表

邻接表，是一种十分神奇的东西，它的基本组成是节点数组和边链表。像之前那个图，邻接表如下：根据输入可以发现，邻接表是一种动态存储方式。邻接表的边是倒序存储的，也就是说，邻接表的构建和输入顺序是有关联的，但并不影响。邻接表可以存储重边和自环。事实上，边链表相对输入顺序，是倒序存储的。显然，动态建图存储的时间、空间复杂度为 $\text{O}(m)$。遍历的时间复杂度为 $\text{O}(m)$。可以看出，因为邻接表使用了链表，因此内存管理是一个大问题，而且写起来也略微麻烦。模板如下：

typedef long long ll;
const int MAXN = 1000 + 1;

struct Node {
    struct Edge *firstEdge;     // 第一条边 (事实上是最后一条边，因为倒序)
    Node() {
        firstEdge = NULL;       // 设置指针初值为空
    }
} Graph[MAXN];
struct Edge {
    Node *prev, *next;          // 前驱点、后继点
    ll w;                       // 权值
    Edge *nextEdge;             // 下一条边 (事实上是上一条边，因为倒序)

    Edge(Node *const &prev, Node *const &next, const ll &w) : prev(prev), next(next), w(w), nextEdge(prev->firstEdge) {}    // 构造函数，利用 initializer list，自动设置 nextEdge 为下(事实上为上)一条边。
};

inline void addEdge(int prev, int next, ll w = 1) {   // 添加边，默认有向，边权 w 默认为 1，便于使用不带权图
    Graph[prev].firstEdge = new Edge (&Graph[prev], &Graph[next], w);
}

void read(int const m, bool directed = true, bool have_weight = true) { // m 为数据组数，即边数，directed 为是否有向，have_weight 为是否带权
    int a = 0, b = 0, w = 1;                // 声明变量
    for (int i = 1; i <= m; i++) {          // 开始读入数据
        scanf(
        if (have_weight) scanf(
        addEdge(a, b, w);                   // 加边
        if (!directed) addEdge(b, a, w);    // 若不带方向，即为无向图，添加反向边
    }
}

void traversal(int amount_of_vertexes) {    // 遍历，传入参数为点数
    for (int i = 1; i <= amount_of_vertexes; i++) {
        for (Edge* e = Graph[i].firstEdge; e != NULL; e = e->nextEdge) {
            /*e->next ...;
            e->prev ...;
            ...*/ // 此处可以操作
        }
    }
}

前方高能预警。

链式前向星

链式前向星是一种更加神奇优越的存储方式。链式前向星的结构为一个点信息数组，一个边信息结构体数组，一个当前处理边的编号计数器。其核心思想是给边编号，这样就能方便地用数组存储了。链式前向星也可以存储重边和自环。链式前向星使用了数组来模拟链表，这样就避免了复杂的内存管理。而它是一种类似邻接表的存储方式，因此，也具有空间复杂度低，时间复杂度低的特性。显然，由于读入完成则建图完成，建图的时间复杂度为 $\text{O}(m)$，存储的空间复杂度为 $\text{O}(n+m)$。遍历的时间复杂度应该为 $\text{O}(m)$ (个人分析，如有误请指正)。根据我们的输入，点信息数组 head 的值为：

下标：1 2 3 4 5
数据：2 4 5 0 7

边信息数组中的信息如下：

edges[1].next = 2 ; edges[1].w = 2 ; edges[1].nextEdge = 0
edges[2].next = 4 ; edges[2].w = 3 ; edges[2].nextEdge = 1
edges[3].next = 3 ; edges[3].w = 1 ; edges[3].nextEdge = 0
edges[4].next = 5 ; edges[4].w = 3 ; edges[4].nextEdge = 3
edges[5].next = 1 ; edges[5].w = 2 ; edges[5].nextEdge = 0
edges[6].next = 3 ; edges[6].w = 2 ; edges[6].nextEdge = 0
edges[7].next = 4 ; edges[7].w = 4 ; edges[7].nextEdge = 6

模板如下：

const int MAXN = 1000, MAXM = 2000;
int head[MAXN];     // 存储点的信息
int edge_count;     // 当前处理的边的编号

struct Edge {
    int prev, next, nextEdge;   // 前驱、后继、下一条边
    long long w;                // 边权值
} edges[MAXM];

void addEdge(int const a, int const b, int w = 1) {
    edges[++edge_count].prev = a;   // 设置前驱点为起点 a，++edge_count 令当前处理的边的编号 +1
    edges[edge_count].next = b;     // 设置后继点为终点 b
    edges[edge_count].w = w;        // 设置边权
    edges[edge_count].nextEdge = head[a];   // 从点信息数组 head 中取出下一条边的编号，若当前为第一条边则取出初值 0
    head[a] = edge_count;           // 记录当前的边编号到点信息数组 head 中，为下一条边的增添做准备
}

void read(int const m, bool directed = true, bool have_weight = true) { // m 为数据组数，即边数，directed 为是否有向，have_weight 为是否带权
    int a = 0, b = 0, w = 1;                // 声明变量
    for (int i = 1; i <= m; i++) {          // 开始读入数据
        scanf(
        if (have_weight) scanf(
        addEdge(a, b, w);                   // 加边
        if (!directed) addEdge(b, a, w);    // 若不带方向，即为无向图，添加反向边
    }
}

void traversal(int const n) {               // n 为点数
    for (int i = 1; i <= n; i++) {          // 从第 1 个点开始遍历
        for (int k = head[i]; k; k = edges[k].nextEdge) { // 令 k 为第 1 条边，直到最后一条边，当 k 到达最后一条边时为 0，结束遍历。
            // do something.
        }
    }
}

事实上，除了不能像邻接矩阵那样直接判断两个点之间是否连通，链式前向星几乎是完美的。在实际应用中，也可以根据题目读入的数据，通过动态数组来做，能够进一步优化空间开销。

邻接矩阵

邻接表

链式前向星

发表回复 取消回复

发表回复取消回复