图的存储

直接存边(邻接表)

1
2
3
4
5
6
7
8
int n,k;
cin>>n>>k; // n为顶点数，k为边数
vector<vector<int>> graph(n+1, vector<int>()); // n为顶点数
for(int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
}

这种方法的优点是简单，但难以判断两个顶点之间是否有边相连。

邻接矩阵

1
2
3
4
5
6
7
8
int n, k;
cin >> n >> k; // n为顶点数，k为边数
vector<vector<int>> graph(n+1, vector<int>(n+1, 0)); // n为顶点数
for(int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    graph[a][b] = 1;
}

这种方法的优点是可以快速判断两个顶点之间是否有边相连，但空间复杂度较高。

DFS

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {
    if(visited[start]) return;
    visited[start] = true;
    for(int i = 1; i <= n; i++) {
        if(graph[start][i] == 1 && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

int main() {
    
}

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {
    if(visited[start]) return;
    visited[start] = true;
    for(int i: graph[start]) {
        if(!visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

int main() {

}

BFS

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(n+1, false);
    q.push(start);
    visited[start] = true;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int i = 1; i <= n; i++) {
            if(graph[cur][i] == 1 && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {

}

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(n+1, false);
    q.push(start);
    visited[start] = true;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int i: graph[cur]) {
            if(!visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {

}

总结

  • DFS适合用于寻找连通性，寻找环等。
  • BFS适合用于寻找最短路径。
  • 无论哪种方法，都可以遍历整个图。
  • 这里的两种图的存储方式，邻接表和邻接矩阵，可以根据实际情况选择。