图的常用存储结构

一、邻接矩阵

　　邻接矩阵是简单的也是比较常用的一种表示图的数据结构，对于一个有N个点的图，需要一个N*N的矩阵，这个矩阵的i行第j列的数值表示点vi到点vj的距离。邻接矩阵需要初始化，map[i][i] = 0;map[i][j] = INF(i != j)，对于每组读入的数据vi,vj,w(vi为边的起点,vj为边的终点,w为边的权值),赋值map[vi][vj] = w，另外邻接矩阵的值和边的输入顺序无关。

　　对于邻接矩阵来说，初始化需要O(n^2)的时间，建图需要O(m),所以总时间复杂度是O(n^2)，空间上，邻接矩阵的开销也是O(n^2)，和点的个数有关。

二、前向星

　　前向星是一种通过存储边的方式来存储图的数据结构。构造的时候，只需要读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序，前向星就构造完毕，为了查询方便，经常会有一个数组存储起点为vi的第一条边的位置.

　　由于涉及排序，前向星的构造时间复杂度与排序算法有关，一般情况下时间复杂度为O(mlogN)，空间上需要两个数组，所以空间复杂度为O(m + n),有点在于可以应对点非常多的情况，可以存储重边，但是不能直接判断任意两个顶点之间是否有边.

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;

const int MAXN = 1000 + 3;
int head[MAXN]; //存储起点为Vi的边第一次出现的位置

struct NODE
{
    int from;
    int to;
    int w;
};
NODE edge[MAXN];

bool cmp(NODE a, NODE b)
{
    if(a.from == b.from && a.to == b.to) return a.w < b.w;
    if(a.from == b.from) return a.to < b.to;
    return a.from < b.from;
}

int main()
{
    freopen("input.txt", "r", stdin);
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> edge[i].from >> edge[i].to >> edge[i].w;
    }
    sort(edge, edge + m, cmp);
    memset(head, -1, sizeof(head));
    head[edge[0].from] = 0;
    for(int i = 1; i < m; i++)
    {
        if(edge[i].from != edge[i - 1].from)
        {
            head[edge[i].from] = i;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int k = head[i]; edge[k].from == i && k < m; k++)
        {
            cout << edge[k].from << ' ' << edge[k].to << ' ' << edge[k].w <<endl;
        }
    }
    for(int i = 0; i <= n; i++)
    {
        cout << head[i] << " ";
    }
    cout << endl;
    return 0;
}

三、链式前向星

　　链式前向星采用数组模拟链表的方式实现邻接表的功能，并且使用很少的额外空间，是当前建图和遍历效率最高的存储方式.数组模拟链表的主要方式是记录下一个节点的数组的在哪一个位置。head数组存储描述点vi边信息的链的起点在Edges数组的位置。构造链式前向星就是将新加入的节点链对应链的最开始并修改head数组的对应位置的值.

　　链式前向星的建图时间复杂度为O(m)，空间上为O(m + n)。

//链式前向星
const int maxN = 100 + 3;
const int maxM = 1000 + 3;
int head[maxN];
int N, M;

struct EdgeNode
{
    int to;   //边的后继
    int w;    //权值
    int next;     //指向下一条边的位置
};
EdgeNode Edges[maxM];

int main()
{
    //freopen("input.txt", "r", stdin);
    memset(head, -1, sizeof(head));
    cin >> N >> M;　　//N个点,M条边
    for(int i = 1; i <= M; i++)
    {
        int x, y ,z;
        cin >> x >> y >> z;
        Edges[i].to = y;
        Edges[i].w = z;
        Edges[i].next = head[x];
        head[x] = i;
    }
    return 0;
}

void traversal()
{
    for(int i = 1; i <= N; i++)
    {
        for(int k = head[i]; k != -1; k = Edges[k].next)
        {
            cout << i << ' ' << Edges[k].to << ' ' << Edges[k].w << endl;
        }
    }
}