存图的三种方式

邻接矩阵

空间复杂度过高

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
const int V = 1000;  //最大顶点数
int mat[maxn][maxn];//开设二维数组来存矩阵
int main()
{
    int i,j,w;
    memset(mat, 0, sizeof(mat));  //初始化操作假设权值为0表示没有该边
    scanf("%d%d%d",&i,&j,&w);//输入边的信息：起点、终点、权重
    mat[i][j] = w;// //增加顶点i到顶点j的权值为w的边
    mat[i][j] = 0;//删除边
    printf("%d",mat[i][j]);//查询边
}

邻接表

内存利用率较高，但重边不好处理

1
2
3
4
5
6
7
8
9
10
11
12
#include<vector>
using namespace std;
const int V = 100000;// 最大顶点数
vector<int> e[V];// 不考虑边权，存储类型为int型
e[i].clear();// 邻接表的初始化操作,将起点为`i`的边链表全部清空
e[i].push_back(j);// 新增边
e[i][0];// 查询边
for (int j=0; j<(int)e[i].size(); ++j) {
    if (e[i][j] == k) {
        ......
    }
}

数组模拟邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1010;
int h[N], e[M], w[M], nxt[M], eidx;
void add(int u, int v, int weight){   // 添加有向边 u->v, 权重为weight
    e[eidx] = v;        // 记录边的终点
    w[eidx] = weight;   // 记录边的权重
    nxt[eidx] = h[u];   // 将下一条边指向结点u此时的第一条边
    h[u] = eidx;        // 将结点u的第一条边的编号改为此时的eidx
    eidx++;             // 递增边的编号edix, 为将来使用
}
void iterate(int u){   // 遍历结点u的所有邻边
    // 从u的第一条边开始遍历，直到eid==-1为止
    for(int eid = h[u]; eid != -1; eid = nxt[eid]){
        int v = e[eid];
        int weight = w[eid];
        cout << u << "->" << v << ", weight: " << weight << endl;
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    memset(h, -1, sizeof h);  // 初始化h数组为-1
    eidx = 0;                 // 初始化边的编号为0
    while(m--){
        int u, v, weight;
        cin >> u >> v >> weight;
        add(u, v, weight);
    }
    for(int u = 1; u <= n; ++u)
        iterate(u);
    return 0;
}

链式前向星

内存利用率高，不像vector实现的邻接表有爆内存的风险，但重边不好处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int maxn = 10005;//点的最大个数
int head[maxn], cnt=0;//head数组用来表示以i为起点的一条边存储的位置,cnt用来记录序号
struct Edge{
    int to; //此边的终点
    int w; //此边的权重
    int next; //同一起点的上一条边的储存位置
}Edge edge[maxn];
void add(int u,int v,int w){  //初始化加边
    edge[cnt].w = w;//记录边的权重
    edge[cnt].to = v;//记录边的终点
    edge[cnt].next = head[u];//存储同一起点的上一条边的位置
    head[u] = cnt++;//给边赋予序号
}
int main()
{
    for(int i=0; i<=n; i++)
        for(int j=head[i]; j！=-1; j=edge[j].next){
            ......
        }
}