C++U7-06-图的进阶存储

上节课作业讲解：

链接：https://pan.baidu.com/s/1A3Y5_12IgwYbmuep0Q2w6Q?pwd=0000
提取码：0000

邻接表和链式前向星都是图论中用于表示图的常用数据结构，它们各自有特定的特点和用途。以下是对这两种数据结构的详细解释：

邻接表

定义与特点：

• 邻接表是用来表示有限图的无序列表的集合，每个列表描述了图中相邻顶点的集合。
• 邻接表是计算机程序中几种常用图的表示法之一，特别是在需要存储大型图时。
• 邻接表是一种顺序分配和链式分配相结合的存储结构。如果某个顶点存在相邻顶点，则把相邻顶点依次存放于该顶点所指向的单向链表中。
• 对于无向图，使用邻接表进行存储会出现数据冗余，因为无向图中的边是双向的，所以每个边会在两个顶点的邻接表中各出现一次。
• 邻接表通常用于表示稀疏图，因为它可以节省存储空间。

实现细节：

• 在邻接表中，图的每个顶点都与一个链表相关联，链表中的每个节点表示与该顶点相邻的一个顶点。
• 邻接表可以用数组和链表来实现，其中数组用于存储顶点，链表用于存储与每个顶点相邻的顶点。
• 邻接表的一个变体是使用散列表（哈希表）将图中的每个顶点与相邻顶点的数组做关联，这种实现方法中没有将边明确表示为对象。

数字信息：

• 对于一个具有n个顶点和e条边的无向图，邻接表表示中会有n个顶点表结点和2e个边表结点（因为每条边在邻接表中会出现两次）。
• 对于有向图，邻接表表示中会有n个顶点表结点和e个边表结点（因为有向图是单向的）。

链式前向星

定义与特点：

• 链式前向星是一种特殊的边集数组，与邻接表的思想相似，但实现方式略有不同。
• 链式前向星使用结构体数组来实现，是静态的，需要在一开始就知道数据范围并开好数组大小。
• 链式前向星避免了邻接表在添加边时可能需要的动态内存分配，因此在某些情况下可能更加高效。

实现细节：

• 链式前向星中，边被存储在一个结构体数组中，每个结构体包含边的终点、下一条同起点边的索引以及边的权值（如果有的话）。
• 通过一个额外的数组（通常称为head数组）来记录每个顶点作为起点时的第一条边的索引。
• 添加边时，只需要在结构体数组中分配一个新的位置，并更新head数组和相应边的next指针。

与邻接表的比较：

• 邻接表更加灵活，可以动态地增加边，而链式前向星则需要在一开始就知道数据范围。
• 链式前向星在内存使用上可能更加紧凑，因为它避免了邻接表中可能出现的链表指针的空间开销。
• 在实现上，链式前向星通常比邻接表更加直观和易于理解，因为它直接使用数组来存储边和顶点信息。

总结来说，邻接表和链式前向星都是用于表示图的有效数据结构，它们各有优缺点，适用于不同的场景和需求。在选择使用哪种数据结构时，需要根据具体的应用场景和性能要求来进行权衡。

 复习图

 邻接表存图

 链式前向星的存图方式

 过程如果忘了就问问老师

链式前向星存图构建代码

[【图的存储】有向图的权重]

 邻接表和链式前向星两种方式代码

【算法分析】
用邻接表将图存储，然后以枚举每个点，将从每个点开始的边的权值进行相加。

【参考代码】
//vector数组
#include<bits/stdc++.h>
using namespace std;

struct node {
    int v, w;
};
vector<node> ve[109];
int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        ve[u].push_back({ v,w });
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < ve[i].size(); j++) {
            ans += ve[i][j].w;
        }
    }
    cout << ans;
    return 0;
}

//链式前向星
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct node {
    int to; // 终点
    int next; // 下一个位置
    int w; // 权重
} edge[N]; // 边结构体数组
int head[N]; // 链表数组，顶点链表起始位置
int cnt; // 当前的已加入的边数
// 插入一条新边，起点为 u
void add(int u, int v, int w) {
    // 表示新边的结点
    edge[++cnt].to = v;
    edge[cnt].w = w;
    // 新结点指向 u 的链表的链头
    edge[cnt].next = head[u];
    // 新结点作为新的链头
    head[u] = cnt;
}
int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w); // 添加边
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j; j = edge[j].next) {
            ans += edge[j].w;
        }
    }
    cout << ans;
    return 0;
}

[【图的存储】公路查询]

【算法分析】
用邻接表将图存储。如果采用 vector 数组存图，由于题目要求后记录的边先输出，因此需要逆序遍历。链式前向星本身就是后记录的边再前面。

【参考代码】
//vector数组
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
struct node {
    int v, w;
};
vector<node> ve[maxn];
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        ve[u].push_back({ v,w });
    }
    while (q--) {
        int x;
        cin >> x;
        for (int i = (int)ve[x].size() - 1; i >= 0; i--) {
            cout << ve[x][i].v << " " << ve[x][i].w << '\n';
        }
    }
    return 0;
}

//链式前向星
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct node {
    int to; // 终点
    int next; // 下一个位置
    int w; // 权重
} edge[N]; // 边结构体数组
int head[N]; // 链表数组，顶点链表起始位置
int cnt; // 当前的已加入的边数
// 插入一条新边，起点为 u
void add(int u, int v, int w) {
    // 表示新边的结点
    edge[++cnt].to = v;
    edge[cnt].w = w;
    // 新结点指向 u 的链表的链头
    edge[cnt].next = head[u];
    // 新结点作为新的链头
    head[u] = cnt;
}
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w); // 添加边
    }
    while (q--) {
        int x;
        cin >> x;
        for (int j = head[x]; j; j = edge[j].next) {
            cout << edge[j].to << " " << edge[j].w << '\n';
        }
    }
    return 0;
}

作业讲解：

链接：https://pan.baidu.com/s/1eVLnEcN3HOAK4tL_iIZiGQ?pwd=0000
提取码：0000