C++处理图存储的方式分享

目录

• 一、邻接矩阵
• 二、邻接表
• 三、链式前向星
• 1、AcWing方式（纯数组）
• 三、Acwing图的存储方式
• 2、复杂度
• 2、应用
• 3、邻接表
• 4、代码实现
• 5、插入边
• 四、遍历
• 1、深度优先遍历
• 2、广度优先遍历
• 3、复杂度
• 4、应用
• 5、实现案例
• 6、 结构体+数组
• 7、 结构体+数组(2)

一、邻接矩阵

适用：

稠密图，就是说点数的平方与边数接近的情况，换句话说就是边特别多。

不适用：

稀疏图，就是点数的平方与边数差的特别多，边数少，但点数多，就不行了，因为空间占用太大了。

实现代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; //图的最大点数量
int n;
int v[N][N];        //邻接矩阵
/**
 * 测试数据
 4
 0 5 2 3
 5 0 0 1
 2 0 0 4
 3 1 4 0
 */
int main() {
    cin >> n;
    //读入到邻接矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> v[i][j];

    //下面的代码将找到与点i有直接连接的每一个点以及那条边的长度
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (v[i][j]) cout << "edge from point " 
                << i << " to point " << j << " with length " << v[i][j] << endl;
    return 0;
}

二、邻接表

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; //图的最大点数量
struct Edge {       //记录边的终点，边权的结构体
    int to;         //终点
    int value;      //边权
};
int n, m; //表示图中有n个点，m条边
vector<Edge> p[N];  //使用vector的邻接表

/**
 * 测试数据
 4 6
 2 1 1
 1 3 2
 4 1 4
 2 4 6
 4 2 3
 3 4 5
 */
int main() {
    cin >> n >> m;
    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v, l;                //点u到点v有一条权值为l的边
        cin >> u >> v >> l;
        p[u].push_back({v, l});
    }

    //输出
    for (int i = 1; i <= n; i++) {
        printf("出发点：%d ", i);
        for (int j = 0; j < p[i].size(); j++)
            printf(" 目标点：%d,权值：%d;", p[i][j].to, p[i][j].value);
        puts("");
    }

    return 0;
}

三、链式前向星

链式前向星是邻接表存图的第二种方法，它自己还有两种写法，比 用向量存图的那种邻接表要快 。

它是一种以边为主的存图方式，idxidx表示最后一条边的预存入的房间号,$head[i$]表示以$i$为起点第一条边的房间号。

每条边有三个属性：

• 从$head[i]$出发到哪个结点的边？
• 这条边的边权是多少？
• 这条边的下一条边是谁？（下一条边的房间号）

链式前向星有三种变形，需要同学们都掌握，找一种自己最喜欢的背下来，其它两种要求能看懂，因为其它人写题解，可能使用了其它方式。

1、AcWing方式（纯数组）

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;     //点数最大值
int n, m;               //n个点，m条边

//idx是新结点加入的数据内索引号
//h[N]表示有N条单链表的头,e[M]代表每个节点的值,ne[M]代表每个节点的下一个节点号
int h[N], e[N << 1], ne[N << 1], w[N << 1], idx;

//链式前向星
void add(int a, int b, int l) {
    e[idx] = b, ne[idx] = h[a], w[idx] = l, h[a] = idx++;
}

/**
 * 测试数据
 4 6
 2 1 1
 1 3 2
 4 1 4
 2 4 6
 4 2 3
 3 4 5
 */
int main() {
    cin >> n >> m;
    //初始化为-1,每个头节点写成-1
    memset(h, -1, sizeof h);

    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v, l;                //点u到点v有一条权值为l的边
        cin >> u >> v >> l;
        //加入到链式前向星
        add(u, v, l);
    }

    //遍历每个结点
    for (int i = 1; i <= n; i++) {
        printf("出发点：%d ", i);
        for (int j = h[i]; j != -1; j = ne[j])
            printf(" 目标点：%d,权值：%d;", e[j], w[j]);
        puts("");
    }
    return 0;
}

三、Acwing图的存储方式

方法：使用一个二维数组 g 来存边，其中 g[u][v] 为 1 表示存在 到的边，为 0 表示不存在。如果是带边权的图，可以在 g[u][v] 中存储到的边的边权。

案例：

最短距离Dijkstra

从s到t的最短距离算法流程：

b[]表示当前已经确定最短距离的点。

dis[s] = 0, dis[其他] = +∞

for (int i = 1; i <= n; i ++)

t：不在b中的最短距离的点

将t加入b[]

使用t更新其他未被确定的点的距离

代码实现：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510;

int n, m;
int w[N][N];
int dis[N];
bool b[N];

int dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    for (int i = 0; i < n; i ++) {
        int k = -1;
        for (int j = 1; j <= n; j ++)
            if (!b[j] && (k == -1 || dis[k] > dis[j]))
                k = j;

        b[k] = true;

        for (int j = 1; j <= n; j ++) {
            dis[j] = min(dis[j], dis[k] + w[k][j]);
        }
    }

    if (dis[n] == 0x3f3f3f3f) return -1;
    else return dis[n];
}

int main() {
    scanf("%d %d", &n, &m);

    memset(w, 0x3f, sizeof w);

    while (m --) {
        int i, j, k;
        scanf("%d %d %d", &i, &j, &k);
        w[i][j] = min(w[i][j], k);
    }

    int t = dijkstra();

    printf("%d", t);
    return 0;
}

2、复杂度

2、应用

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

3、邻接表

使用一个支持动态增加元素的数据结构构成的数组，如 vector g[n + 1] 来存边，其中 g[u] 存储的是点的所有出边的相关信息（终点、边权等）。

4、代码实现

数据定义：

h是n个链表的链表头, e存的是每一个节点的值, ne存的是 next指针是多少。

int h[N], e[M], ne[M], idx;
bool st[N];

5、插入边

插入一条a指向b的边

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

四、遍历

1、深度优先遍历

void dfs(int u) {
    st[u] = true;    // 标记已经被遍历过了
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

2、广度优先遍历

void bfs() {
    int q[N];    // 定义队列 
    int hh = 0, tt = 0;    // 头和尾指针 
    memset(st, 0, sizeof st);
    q[0] = 1;
    while (hh <= tt) {
        int t = q[hh ++];
        st[t] = true;
        cout << t << ' ';
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                q[++ tt] = j;
            }
        }
    }
}

3、复杂度

4、应用

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

尤其适用于需要对一个点的所有出边进行排序的场合。

5、实现案例

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = N * 2;

// h是n个链表的链表头, e存的是每一个节点的值, ne存的是 next指针是多少。 
int h[N], e[M], ne[M], idx;
bool st[N];
int n;    // n条边 

// 插入一条a指向b的边 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// 深度优先遍历
void dfs(int u) {
    cout << u << ' ';
    st[u] = true;    // 标记已经被遍历过了
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

// 广度优先遍历 
void bfs() {
    int q[N];    // 定义队列 
    int hh = 0, tt = 0;    // 头和尾指针 
    memset(st, 0, sizeof st);
    q[0] = 1;
    while (hh <= tt) {
        int t = q[hh ++];
        st[t] = true;
        cout << t << ' ';
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                q[++ tt] = j;
            }
        }
    }
}

int main () {
    memset(h, -1, sizeof h);
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        int a, b;
        cin >> a >> b; 
        add(a, b);
        add(b, a);
    }

    cout << "深度优先遍历：";
    dfs(1);
    cout << endl;
    cout << "广度优先遍历：";
    bfs(); 
    return 0;
}

6、 结构体+数组

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;     //点数最大值
int n, m, idx;          //n个点，m条边,idx是新结点加入的数据内索引号

//链式前向星
struct Edge {
    int to;     //到哪个结点
    int value;  //边权
    int next;   //同起点的下一条边的编号
} edge[N << 1]; //同起点的边的集合 N<<1就是2*N，一般的题目，边的数量通常是小于2*N的，这个看具体的题目要求

int head[N];    //以i为起点的边的集合入口处

//加入一条边，x起点，y终点，value边权
void add_edge(int x, int y, int value) {
    edge[++idx].to = y;         //终点
    edge[idx].value = value;    //权值
    edge[idx].next = head[x];   //以x为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[x] = idx;              //更新以x为起点上一条边的编号
}

/**
 * 测试数据
 4 6
 2 1 1
 1 3 2
 4 1 4
 2 4 6
 4 2 3
 3 4 5
 */
int main() {
    cin >> n >> m;

    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v, l;                //点u到点v有一条权值为l的边
        cin >> u >> v >> l;
        //加入到链式前向星
        add_edge(u, v, l);
    }

    //遍历每个结点
    for (int i = 1; i <= n; i++) {
        printf("出发点：%d ", i);
        for (int j = head[i]; j; j = edge[j].next)  //遍历每个结点的每一条边
            printf(" 目标点：%d,权值：%d;", edge[j].to, edge[j].value);
        puts("");
    }
    return 0;
}

7、 结构体+数组(2)

为什么链式前向星有两种实现方法呢？这其实是看用不用的问题，如果它用了，那么就是在加边的最后需要++，如果不用，进来就++。

第二个变化就是如果用了，那么就不能用做默认值了，所以需要初始化memset(head,-1 ,sizeof head);

第三个变化就是遍历时的条件变了，成了j!=-1,而不用的就是j就行了，我个人还是喜欢用不带的那个，就是上面的。是因为网上好多网友喜欢这种方式，如果我们看其它人的题解时，可能看不懂，所以也要了解一下。

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;     //点数最大值
int n, m, idx;          //n个点，m条边,idx是新结点加入的数据内索引号

//链式前向星
struct Edge {
    int to;     //到哪个结点
    int value;  //边权
    int next;   //同起点的下一条边的编号
} edge[N << 1]; //同起点的边的集合 N<<1就是2*N，一般的题目，边的数量通常是小于2*N的，这个看具体的题目要求

int head[N];    //以i为起点的边的集合入口处

//加入一条边，x起点，y终点，value边权
void add_edge(int x, int y, int value) {
    edge[idx].to = y;           //终点
    edge[idx].value = value;    //权值
    edge[idx].next = head[x];   //以x为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[x] = idx++;            //更新以x为起点上一条边的编号
}

/**
 * 测试数据
 4 6
 2 1 1
 1 3 2
 4 1 4
 2 4 6
 4 2 3
 3 4 5
 */
int main() {
    cin >> n >> m;

    //初始化head数组
    memset(head, -1, sizeof head);

    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v, l;                //点u到点v有一条权值为l的边
        cin >> u >> v >> l;
        //加入到链式前向星
        add_edge(u, v, l);
    }

    //遍历每个结点
    for (int i = 1; i <= n; i++) {
        printf("出发点：%d ", i);
        for (int j = head[i]; j != -1; j = edge[j].next)  //遍历每个结点的每一条边
            printf(" 目标点：%d,权值：%d;", edge[j].to, edge[j].value);
        puts("");
    }
    return 0;
}

到此这篇关于C++处理图存储的方式分享的文章就介绍到这了,更多相关C++处理图存储内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！