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;
}