图的存储

邻接表Node要链接first_edge,Edge要链接next_edge,A_node,B_node.

邻接多重表在邻接表的基础上Edge的next_edge有两个,A_next,B_next,A_node,B_node.

十字链表在邻接多重表的基础上,Node有两种out_first,in_first

邻接矩阵和邻接表，是多对多的关系，分为有向图和无向图。

邻接矩阵和邻接表的对比

邻接矩阵表示法：在一个一维数组中存储所有的点，在一个二维数组中存储顶点之间的边的权值

邻接表表示法：图中顶点用一个一维数组存储，图中每个顶点vi的所有邻接点构成单链表

对比

1）在邻接矩阵表示中，无向图的邻接矩阵是对称的。矩阵中第 i 行或第 i 列有效元素个数之和就是顶点的度。

在有向图中第 i 行有效元素个数之和是顶点的出度，第 i 列有效元素个数之和是顶点的入度。

2）在邻接表的表示中，无向图的同一条边在邻接表中存储的两次。如果想要知道顶点的度，只需要求出所对应链表的结点个数即可。

有向图中每条边在邻接表中只出现一次，求顶点的出度只需要遍历所对应链表即可。求入度则需要遍历其他顶点的链表。

3）邻接矩阵与邻接表优缺点：

邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。而其缺点是如果顶点之间的边比较少，会比较浪费空间。因为是一个 n∗n 的矩阵。

而邻接表的优点是节省空间，只存储实际存在的边。其缺点是关注顶点的度时，就可能需要遍历一个链表。

图的存储

必须确定一个概念：存图到底是在存什么？点？不是，是点的关系。所以其实是在存边。而边是由点集中的两个点确定的。所以就有思路了:

矩阵法：构造边结点，使用方式矩阵表达边和结点的关系。
链表法：构造边结点，使用链式结构，边和两个端点的关系内涵在边结点中。

邻接矩阵

使用一个二维数组 edges 来存边，其中 adj[u][v] 为 1 表示存在 u 到 v 的边，为 0 表示不存在。如果是带边权的图，可以在 adj[u][v] 中存储 u 到 v 的边的边权。

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以 O(1) 查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

class Graph {
public:
    Graph(int n){
        size = n;
        nodes.resize(n, 0);
        edges.resize(n,vector<int>(n,0));
    };
    int getWeight(int n,int m){
        //越界检查
        return edges[n][m];
    }

private:
    int size;
    vector<int> nodes;
    vector<vector<int>> edges;
} Graph;

无权图:1有边,0无边,自身0
有权图:∞无边,权值有边,自身0

查询是否存在某条边： $O(1)$ 。
遍历一个点的所有出边： $O(n)$ 。
遍历整张图： $O(n^2)$ 。
空间复杂度： $O(n^2)$ 。

邻接表

使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[n + 1] 来存边，其中 adj[u] 存储的是点 u 的所有出边的相关信息（终点、边权等）。

class UG_Node{
    private:
    UG_Edge* first_edge;
};

class UG_Edge {
    private:
    int weight;
    UG_Node *A, *B;
    UG_Edge *A_next,*B_next;
};

class DG_Node{
    private:
    UG_Edge* first_edge;
};

class DG_Edge {
    private:
    int weight;
    DG_Node *from,*to;
    DG_Edge *from_next,*to_next;
};

查询是否存在 u 到 v 的边： $O(d^+(u))$ （如果事先进行了排序就可以使用二分查找做到 $O(\log(d^+(u)))$ ）。

遍历点 u 的所有出边： $O(d^+(u))$ 。

遍历整张图： $O(n+m)$ 。

空间复杂度： $O(m)$ 。

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

尤其适用于需要对一个点的所有出边进行排序的场合。

图的存储

邻接矩阵​

邻接表​

邻接矩阵

邻接表