图的存储与遍历

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

1 2 2
1 4 3
2 3 1
2 5 3
3 1 2
5 3 2
5 4 4

邻接矩阵

由于邻接矩阵空间消耗巨大,一般不使用。
邻接矩阵初始化时,我们使用无穷。
#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.
        }
    }
}

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

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注