TIP

图在数据结构中比较重要，但是了解的却非常的少，所以现在就重新再学习一遍。图的存储结构用的最多的就是邻接矩阵了，因为简单，只需要开一个二维数组就可以了，但是边的数量非常的少时，空间就比较浪费了，所以为了提高效率，就必须做出改变，下面就来一一说说吧。

邻接矩阵

邻接矩阵比较简单，也更加的直观，二维数组的下标就是代表一组坐标，例如a[x][y] (x,y)就是在这个矩阵中的一个坐标，当a[x][y]=1时代表这两个点之间有连线，当a[x][y]=0时代表这两个点之间没有连线，代码如下(默认以无向图为例)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;//n代表有几个点,m代表有几条边
    cin >> n >> m;
    int a[n+1][n+1];//不用数组0下标
    fill(a[0],a[0]+(n+1)*(n+1),0);//将数组初始化为0
    for(int i=0; i<m; i++){
        int x,y;
        cin >> x >> y;
        a[x][y]=1;
        a[y][x]=1;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

邻接表

邻接表开始我也不是很理解，不知道如何用代码实现，看着那个图好像是那么回事，无法下手。做这个之前，需要先了解一下，构成邻接表需要哪些东西，一个顶点域，顶点的下标就是代表起始点，还有一部分数据域，里面的内容是从顶点到哪个顶点，还有权值，还有指向下一顶点的指针，代码如下(默认以有向图为例)

#include<bits/stdc++.h>
using namespace std;
const int Max=1e4+3;
typedef struct ENode
{
    int to;//终止点
    int w;//权值
    ENode *next;//指向下一终止点
};
typedef struct VNode
{
    int from;//开始点，实际上没用到
    ENode *first;//指向终止点
};
VNode adjlist[Max];//初始化顶点
int main()
{
    int n,m;//n代表有几个顶点,m代表有几条边
    cin >> n >> m;
    for(int k=0;k<m;k++){
        int i,j,w;//i代表起点,j代表终点,w代表权值
        cin >> i >> j >> w;
        ENode *p=new ENode;
        p->to=j;
        p->w=w;
        p->next=adjlist[i].first;
        adjlist[i].first=p;
    }
    for(int i=1;i<=n;i++){
        for(ENode *k=adjlist[i].first;k!=NULL;k=k->next){
            printf("%d %d %d\n",i,k->to,k->w);
        }
    }
    return 0;
}

vector版本邻接表

如果上面的邻接表不好理解的话，这个vector版本绝对是适合大多数人的，比较好实现。实现原理是这样的，定义一个一维结构体容器，一维数组的下标代表起始点，结构体包括终止点和权值，这样对于同一起始点的就可以放在同一行了，实现起来很容易，代码如下(有向图)

#include<bits/stdc++.h>
using namespace std;
const int Max=1e4+3;
typedef struct ENode
{
    int to;
    int w;
};
vector<ENode> s[Max];
int main()
{
    int n,m;//n代表起点,m代表终点
    cin >> n >> m;
    for(int i=0;i<n;i++){
        s[i].clear();
    }
    for(int k=0;k<m;k++){
        int i,j,w;
        cin >> i >> j >> w;
        ENode e;
        e.to=j;
        e.w=w;
        s[i].push_back(e);
    }
    for(int i=1;i<=n;i++){
        for(auto it=s[i].begin();it!=s[i].end();it++){
            ENode k=*it;
            printf("%d %d %d\n",i,k.to,k.w);
        }
    }
    return 0;
}