圖的存儲

在 OI 中，想要對圖進行操作，就需要先學習圖的存儲方式。

約定

本文默認讀者已閲讀並瞭解了 圖論相關概念 中的基礎內容，如果在閲讀中遇到困難，也可以在 圖論相關概念 中進行查閲。

在本文中，用 \(n\) 代指圖的點數，用 \(m\) 代指圖的邊數，用 \(d^+(u)\) 代指點 \(u\) 的出度，即以 \(u\) 為出發點的邊數。

直接存邊

方法

使用一個數組來存邊，數組中的每個元素都包含一條邊的起點與終點（帶邊權的圖還包含邊權）。（或者使用多個數組分別存起點，終點和邊權。）

參考代碼

C++Python

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
  int u, v;
};

int n, m;
vector<Edge> e;
vector<bool> vis;

bool find_edge(int u, int v) {
  for (int i = 1; i <= m; ++i) {
    if (e[i].u == u && e[i].v == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = 1; i <= m; ++i) {
    if (e[i].u == u) {
      dfs(e[i].v);
    }
  }
}

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

  vis.resize(n + 1, false);
  e.resize(m + 1);

  for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;

  return 0;
}

class Edge:
    def __init__(self, u = 0, v = 0):
        self.u = u
        self.v = v

n, m = map(int, input().split())

e = [Edge() for _ in range(m)]; vis = [False] * n

for i in range(m):
    e[i].u, e[i].v = map(int, input().split())

def find_edge(u, v):
    for i in range(m):
        if e[i].u == u and e[i].v == v:
            return True
    return False

def dfs(u):
    if vis[u]:
        return
    vis[u] = True
    for i in range(m):
        if e[i].u == u:
            dfs(e[i].v)

複雜度

查詢是否存在某條邊：\(O(m)\)。

遍歷一個點的所有出邊：\(O(m)\)。

遍歷整張圖：\(O(nm)\)。

空間複雜度：\(O(m)\)。

應用

由於直接存邊的遍歷效率低下，一般不用於遍歷圖。

在 Kruskal 算法 中，由於需要將邊按邊權排序，需要直接存邊。

在有的題目中，需要多次建圖（如建一遍原圖，建一遍反圖），此時既可以使用多個其它數據結構來同時存儲多張圖，也可以將邊直接存下來，需要重新建圖時利用直接存下的邊來建圖。

鄰接矩陣

方法

使用一個二維數組 adj 來存邊，其中 adj[u][v] 為 1 表示存在 \(u\) 到 \(v\) 的邊，為 0 表示不存在。如果是帶邊權的圖，可以在 adj[u][v] 中存儲 \(u\) 到 \(v\) 的邊的邊權。

參考代碼

C++Python

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

vis = [False] * (n + 1)
adj = [[False] * (n + 1) for _ in range(n + 1)]

for i in range(1, m + 1):
    u, v = map(lambda x:int(x), input().split())
    adj[u][v] = True

def find_edge(u, v):
    return adj[u][v]

def dfs(u):
    if vis[u]:
        return
    vis[u] = True
    for v in range(1, n + 1):
        if adj[u][v]:
            dfs(v)

複雜度

查詢是否存在某條邊：\(O(1)\)。

遍歷一個點的所有出邊：\(O(n)\)。

遍歷整張圖：\(O(n^2)\)。

空間複雜度：\(O(n^2)\)。

應用

鄰接矩陣只適用於沒有重邊（或重邊可以忽略）的情況。

其最顯著的優點是可以 \(O(1)\) 查詢一條邊是否存在。

由於鄰接矩陣在稀疏圖上效率很低（尤其是在點數較多的圖上，空間無法承受），所以一般只會在稠密圖上使用鄰接矩陣。

鄰接表

方法

使用一個支持動態增加元素的數據結構構成的數組，如 vector<int> adj[n + 1] 來存邊，其中 adj[u] 存儲的是點 \(u\) 的所有出邊的相關信息（終點、邊權等）。

參考代碼

C++Python

#include <iostream>
#include <vector>

using namespace std;

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

bool find_edge(int u, int v) {
  for (int i = 0; i < adj[u].size(); ++i) {
    if (adj[u][i] == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
}

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

  vis.resize(n + 1, false);
  adj.resize(n + 1);

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

  return 0;
}

vis = [False] * (n + 1)
adj = [[] for _ in range(n + 1)]

for i in range(1, m + 1):
    u, v = map(lambda x:int(x), input().split())
    adj[u].append(v)

def find_edge(u, v):
    for i in range(0, len(adj[u])):
        if adj[u][i] == v:
            return True
    return False

def dfs(u):
    if vis[u]:
        return
    vis[u] = True
    for i in range(0, len(adj[u])):
        dfs(adj[u][i])

複雜度

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

遍歷點 \(u\) 的所有出邊：\(O(d^+(u))\)。

遍歷整張圖：\(O(n+m)\)。

空間複雜度：\(O(m)\)。

應用

存各種圖都很適合，除非有特殊需求（如需要快速查詢一條邊是否存在，且點數較少，可以使用鄰接矩陣）。

尤其適用於需要對一個點的所有出邊進行排序的場合。

鏈式前向星

方法

本質上是用鏈表實現的鄰接表，核心代碼如下：

C++Python

// head[u] 和 cnt 的初始值都為 -1
void add(int u, int v) {
  nxt[++cnt] = head[u];  // 當前邊的後繼
  head[u] = cnt;         // 起點 u 的第一條邊
  to[cnt] = v;           // 當前邊的終點
}

// 遍歷 u 的出邊
for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
  int v = to[i];
}

# head[u] 和 cnt 的初始值都為 -1
def add(u, v):
    cnt = cnt + 1
    nex[cnt] = head[u] # 當前邊的後繼
    head[u] = cnt # 起點 u 的第一條邊
    to[cnt] = v # 當前邊的終點

# 遍歷 u 的出邊
i = head[u]
while ~i: # ~i 表示 i != -1
    v = to[i]
    i = nxt[i]

參考代碼

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<int> head, nxt, to;

void add(int u, int v) {
  nxt.push_back(head[u]);
  head[u] = to.size();
  to.push_back(v);
}

bool find_edge(int u, int v) {
  for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
    if (to[i] == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = head[u]; ~i; i = nxt[i]) dfs(to[i]);
}

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

  vis.resize(n + 1, false);
  head.resize(n + 1, -1);

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v);
  }

  return 0;
}

複雜度

查詢是否存在 \(u\) 到 \(v\) 的邊：\(O(d^+(u))\)。

遍歷點 \(u\) 的所有出邊：\(O(d^+(u))\)。

遍歷整張圖：\(O(n+m)\)。

空間複雜度：\(O(m)\)。

應用

存各種圖都很適合，但不能快速查詢一條邊是否存在，也不能方便地對一個點的出邊進行排序。

優點是邊是帶編號的，有時會非常有用，而且如果 cnt 的初始值為奇數，存雙向邊時 i ^ 1 即是 i 的反邊（常用於 網絡流）。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, sshwy, Xeonacid, partychicken, Anguei, HeRaNO
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用