学习系列 —— 图论2：图的存储 1：直接存边 - Problem

【约定】
用 $n$ 代指图的点数，用 $m$ 代指图的边数，用 $d^+(u)$ 代指点 $u$ 的出度，即以 $u$ 为出发点的边数。

【直接存边】
使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）
【参考代码】

// C++ Version
#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) return;
  vis = 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;
}

# Python Version
class Edge:
    u = 0
    v = 0

n, m = map(lambda x:int(x), input().split())

e = [Edge()] * m; vis = [False] * n

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

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

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

【复杂度】

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

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

遍历整张图：$O(nm)$。

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

【使用场合】
由于直接存边的遍历效率低下，一般不用于遍历图。

在 Kruskal 算法中，由于需要将边按边权排序，需要直接存边。

在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。

6252: 学习系列 —— 图论2：图的存储 1：直接存边

Description

HINT

Source/Category