结构体

代码

struct
{
    int a,b,w; //a为起点，b为终点，w为边权
}edge[M];
 
#include <vector>
#include <iostream>
using namespace std;
bool vis[10];
vector<int> h[10];
int n, m;
void dfs(int u) {
    vis[u] = true;
    cout << u << '\n';
    for (int i=0;i<h[u].size();i++) {
        if (!vis[h[u][i]]) {
            dfs(h[u][i]);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i=0;i<m;i++) {
        int x, y;
        cin >>x >> y;
        h[x].push_back(y);
    }
    dfs(1);
}

优点：

结构体可以灵活地定义每个节点的附加信息，例如权值、坐标等；
可以方便地遍历所有的边或节点；

缺点：

不利于图的迭代修改，因为很难动态地调整结构体中节点的顺序；
遍历某些节点的出边或入边会相对困难。

邻接表

代码

int e[N], ne[N], idx, h[N], w[N];
void add(int a,int b, int c)
{
    e[idx] = b,ne[idx] = h[a] , w[idx] = c, h[a] = idx++;
}

优点：

占用空间较小，只需存储每个节点与其出边或入边的关系；
方便存取和添加边。而且可以动态调整图的大小；
适用于存储稀疏图，因为只需存储每个节点的相邻节点即可。

缺点：

访问某个节点 $i$ 的相邻节点比较耗时，在存在大量出度非常高的情况下，时间复杂度可能达到 $O(E)$ ， $E$ 为边数；
在计算稠密图中的某些算法时，跟邻接矩阵比较，速度慢。

邻接矩阵

代码

int g[N][N]; //g[a][b] = w 中 a 为起点 b 为终点 w 为边权

优点：

快速访问节点 $i$ 和 $j$ 之间是否存在一条边，并可以快速获取两个节点之间的权重；
在邻接矩阵中查找某个节点的相邻节点非常容易， $O(1)$ 即可完成；
适用于存储稠密图，因为可以快速访问任意两个节点之间的距离。

缺点：

占用空间比较大，当图较稀疏时浪费空间；
在计算稀疏图中的某些算法时，跟邻接表比较，速度慢。

综上所述，不同的存储方式适合不同的场景，如何选择要根据实际情况来判断。如果希望得到更快的遍历和存取性能，则应该使用邻接矩阵；如果希望节省空间，则应该使用邻接表；如果需要存储节点的附加信息或遍历所有边，则应该使用结构体。

图的存储表示方法

结构体

代码

邻接表

代码

邻接矩阵

代码

评论