目录

• 邻接矩阵（最简单，空间复杂度最高）
• 邻接表（以点为基本单位，尾插）
• 链式前向星（以边为基本单位，头插）

一、邻接矩阵

方法

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

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<bool> > adj;

bool find_edge(int u, int v) { return adj[u][v]; }

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int v = 1; v <= n; ++v) {
    if (adj[u][v]) {
      dfs(v);
    }
  }
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);
  adj.resize(n + 1, vector<bool>(n + 1, false));

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u][v] = true;
  }

  return 0;
}

复杂度

查询是否存在某条边：O(1)。

遍历一个点的所有出边：O(n)。

遍历整张图：O(n^2)。

空间复杂度：O(n^2)。

应用

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

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

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

二、邻接表

三、链式前向星

---

📝我的个人主页

🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​

💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊

✉️今天你做别人不想做的事，明天你就能做别人做不到的事♐