[图论] 图的存储

https://blog.csdn.net/Binary_Heap/article/details/78209086

1.链式向前星存图 / 邻接表

//#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 10;

struct EDGE //边
{
    int next;   //下一条边
    int to;     //本边指向节点
    int val;    //权
}edge[MAXN];

int head[MAXN]; //以I为头节点的最后一条边地址 对应edge[I]

int cnt = 0;    //edge计数

void add(int x, int y, int z)
{
	edge[++cnt].next = head[x];
    edge[cnt].val = z;
    edge[cnt].to = y;
    head[x] = cnt;      //以I为头节点的最后一条边地址 对应edge[I] 覆盖更新 保证最后一条
}

void puts()
{
	int st;
	
	cin>>st;
	
	for(int i = head[st]; i != 0; i = edge[i].next) //链式向前星的遍历 从尾至头
	{
		printf("start:%d
", st);
		printf("end:%d
", edge[i].to);
		printf("val:%d
", edge[i].val);
	}
}


int main()
{
    ios::sync_with_stdio(false);

    cin.tie(0);     cout.tie(0);

    int n, m, s, x, y, z;
    
    cin>>n>>m>>s;
    
    for(int i = 0; i < m; i++)
    {
    	cin>>x>>y>>z;
    	
    	add(x, y, z);
	}
	
	puts();

    return 0;
}

2.vector实现邻接表

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 10;
ll n, m;

struct node
{
    int to, val;
};

vector <node> edge[MAXN];

void init()
{
    for(int i = 0; i < MAXN; i++)
        edge[i].clear();
}

void add(int x, int y, int z)
{
    node tmp;
    tmp.to = y;
    tmp.val = z;
    edge[x].push_back(tmp);
}


void puts()
{
    int st;
    
    cin>>st;
    
    for(int i = 0; i < edge[st].size(); i++) //链式向前星的遍历 从尾至头
    {
        printf("start:%d
", st);
        printf("end:%d
", edge[st][i].to);
        printf("val:%d
", edge[st][i].val);
    }
}


int main()
{
    ios::sync_with_stdio(false);

    cin.tie(0);     cout.tie(0);

    int n, m, s, x, y, z;
    
    cin>>n>>m>>s;
    
    for(int i = 0; i < m; i++)
    {
        cin>>x>>y>>z;
        
        add(x, y, z);
    }
    
    puts();

    return 0;
}

3.

邻接矩阵

如果我们想把图存下来，那么最直观的想法开个矩阵G[n][n] (n为点的个数)。G[i][j] 表示i到j的权值。这就是邻接矩阵啦。

观察上表可以发现，对于第i行来说记录的是i号点出发所能达到的地方，对于该行第j列来说如果i可以到达j，Mp[i][j]记录的就是一个正数，表示距离，如果为零，表示无法到达。

可是从上面的表格我们会发现一个问题，为了记录第i个顶点能去哪里，我们用了一行的空间，为每个点都安排了空间，但是事实上我们完全没必要浪费这些空间，因为我们关心的是我从i出发能到哪些点，而对于那些无法到达的点，我们并不关心，因此也就不必记录啦。由此引出了邻接表的概念。