前言

初次接触图这个数据结构，往往会觉得十分的复杂，难以接受。但是一旦学习完毕图的大致概念，尤其是邻接矩阵这个之后，一切都会变得简单很多。

简介

学习过树之后，大家应该对节点与节点之间的关系有了比较清晰的一个认识了吧，图也同样如此，只不过节点与节点之间的关系更为复杂。可以说树就是图的一种特殊情况。

图

在学习图之前，图的几个简单的概念还是需要进行一定的了解的，这边将大致进行描述。更具体的概念（其实还有很多，这边不一一介绍）大家可以看看这个B站视频离散数学【图论：图的基本概念】。

图1

有向图

上图展示的便是一张有向图。

在有向图中，任意两个节点的关联是有方向的，就像树一样，从一个节点到另一个节点。

每一个连接，对应的都是一个二元有序组，是一组关联。例如图中1 -> 2的一条边，便可以表示为二元有序组，而这个关系便是之后我们表示一个图的关键。

无向图

无向图与有向图的唯一区别就是节点与节点之间的关联是没有方向的。例如上图中的5号节点和6号节点，他们之间的边便是无向边，也就是说，无向边用有向边的来表示，就是一个双向的连接。因此表示成二元组便是，也可以表示为。

图的表示

如何记录一张图呢？当然，在纸上，我们可以把图画出来，进行很直观的观察。但是在计算机中，我们就只能使用一些基本的数据结构来进行储存。

在学习树的时候，我们创造了节点，通过指针的方式连接了起来。

同样的，在图的世界中，我们是不是也可以使用相同的方式进行建立呢？其实确实可以，但是很麻烦也不好用，因此我们将一张图抽象成每个简单之间的连接关系，也就是我们所说的邻接矩阵。

图1的邻接矩阵

很好理解，图1中1 -> 2这条边在关系矩阵中便成为了(1, 2)（第1行，第2列）中的那个1，图1中5 -> 6这条边在关系矩阵中成为了(5, 6)（第5行，第6列）中的那个1。

如果一个图的疏密程度比较密集，那么使用关系矩阵进行储存还算是个不错的选择。

但是对于像上图所示的图来说，你会发现，图中所空缺的位置还有很多，如果就这样开一个二维数组，那么就会造成很大的浪费，因此，图的最佳储存方式便是邻接链表。

邻接链表

图中，蓝色的一列便是我们的数组，而后面的便是储存在数组里面的节点的指针地址。

那么数组的下标所对应的节点便和每一个节点进行了关联。

比如图中的第一行，便是1号节点的两条有向边分别指向了2号节点和7号节点。

实现

我们可以写出链表的节点。

struct Node {
    int to; // 目标链接节点
    Node *next;
};

我们再用数组进行存储。

Node *g[100] = {NULL};

这样，我们的指针数组就建立完成了。

那么，建立图便是通过边的关系来建立链表。

int u, v;
scanf("%d %d", &u, &v); // 假如输入的关系是u -> v的一条有向边
Node *p = (Node*) malloc(sizeof(Node)); // 申请内存
p -> to = v; // 指定目标节点编号数
p -> next = g[u]; // 将链表的下一个节点指向当前节点（由于数组每个元素一开始已经初始化成NULL，所以可以直接这么写）
g[u] = p; // 更新节点地址

以上便是一个十分简单的建立邻接链表的一个过程。

代码小结

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int to;
    Node *next;
};

int main()
{
    Node *g[100] = {NULL};
    int u, v;
    int n;
    scanf("%d",&n);
    Node *p;
    for (int i = 0;i < n;i ++)
    {
        scanf("%d %d", &u, &v);
        p = (Node*) malloc(sizeof(Node));
        p -> to = v;
        p -> next = g[u];
        g[u] = p;
    }
    return 0;
}

无向图

那么如果是无向图呢？那原理是一样的，在插入u -> v边的同时也插入v -> u边即可。

// 插入u -> v边
p = (Node*) malloc(sizeof(Node));
p -> to = v;
p -> next = g[u];
g[u] = p;
// 插入v -> u边
p = (Node*) malloc(sizeof(Node));
p -> to = u;
p -> next = g[v];
g[v] = p;