图的基本概念

概念讲解

什么是图？

图（Graph）是由顶点（Vertex）和边（Edge）组成的数据结构。

图的分类

类型 说明
无向图 边没有方向
有向图 边有方向
加权图 边有权值
无权图 边没有权值

基本术语

术语 说明
顶点 图中的节点
边 连接两个顶点的线
度 与顶点相连的边数
入度 指向顶点的边数（有向图）
出度 从顶点出发的边数（有向图）
路径 从一个顶点到另一个顶点的边序列
连通图 任意两个顶点都连通
连通分量 极大连通子图

存储方式

邻接矩阵

12345678910111213const int N = 1005;
int graph[N][N];

// 添加边
void addEdge(int u, int v, int w = 1) {
    graph[u][v] = w;
    graph[v][u] = w;  // 无向图
}

// 判断是否有边
bool hasEdge(int u, int v) {
    return graph[u][v] != 0;
}

优点： 查询边 O(1)
缺点： 空间 O(V²)，适合稠密图

邻接表

123456789101112const int N = 100005;
vector<int> graph[N];  // 无权图
vector<pair<int, int>> graph2[N];  // 加权图

// 添加边
void addEdge(int u, int v, int w = 1) {
    graph[u].push_back(v);
    graph[v].push_back(u);  // 无向图
    
    graph2[u].push_back({v, w});
    graph2[v].push_back({u, w});  // 无向图
}

优点： 空间 O(V + E)，适合稀疏图
缺点： 查询边 O(degree)

链式前向星

123456789101112131415161718192021222324const int N = 100005;
const int M = 100005;

struct Edge {
    int to, next, w;
} edges[M];

int head[N], cnt = 0;

void init() {
    memset(head, -1, sizeof(head));
    cnt = 0;
}

void addEdge(int u, int v, int w) {
    edges[cnt] = {v, head[u], w};
    head[u] = cnt++;
}

// 遍历 u 的所有邻居
for (int i = head[u]; i != -1; i = edges[i].next) {
    int v = edges[i].to;
    int w = edges[i].w;
}

图的遍历

DFS 遍历

1234567891011bool visited[N];

void dfs(int u) {
    visited[u] = true;
    
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

BFS 遍历

12345678910111213141516171819void bfs(int start) {
    queue<int> q;
    bool visited[N] = {false};
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

考点分析

初赛考查方式

  1. 选择题： 图的基本概念
  2. 填空题： 计算度数
  3. 程序阅读： 理解图的遍历

常见题型

  • 连通分量计数
  • 最短路径
  • 拓扑排序

例题精讲

例题 1：连通分量计数

题目： 求无向图的连通分量个数。

解答：

12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>
#include <vector>
using namespace std;

const int N = 1005;
vector<int> graph[N];
bool visited[N];

void dfs(int u) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }
    
    cout << count << endl;
    
    return 0;
}

例题 2：度数计算

题目： 求无向图中每个顶点的度数。

解答：

1234567891011121314151617181920212223#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    int degree[n + 1] = {0};
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
    }
    
    for (int i = 1; i <= n; i++) {
        cout << degree[i] << " ";
    }
    cout << endl;
    
    return 0;
}

练习题

  1. 洛谷 P1451 求细胞数量
查看答案

思路：使用 DFS 或 BFS 统计连通块数量。

123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>
using namespace std;

int n, m;
char grid[105][105];
bool visited[105][105];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y) {
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] != '0') {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] != '0') {
                dfs(i, j);
                count++;
            }
        }
    }
    
    cout << count << endl;
    return 0;
}
  1. 洛谷 P1141 01 迷宫
查看答案

思路：使用 BFS 或 DFS，将连通块标记为同一个组，记录每个组的大小。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>
#include <queue>
using namespace std;

int n, m;
char grid[1005][1005];
int group[1005][1005];
int groupSize[1000005];
int groupCount = 0;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(int x, int y) {
    groupCount++;
    queue<pair<int,int>> q;
    q.push({x, y});
    group[x][y] = groupCount;
    int size = 1;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !group[nx][ny] && grid[nx][ny] != grid[x][y]) {
                group[nx][ny] = groupCount;
                q.push({nx, ny});
                size++;
            }
        }
    }
    
    groupSize[groupCount] = size;
}

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!group[i][j])
                bfs(i, j);
    
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << groupSize[group[x-1][y-1]] << endl;
    }
    
    return 0;
}
  1. 洛谷 P1162 填涂颜色
查看答案

思路：从边界上的 0 开始 BFS，标记所有与边界连通的 0，然后将剩余的 0 变为 2。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int a[n][n];
    bool visited[n][n] = {false};
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    
    queue<pair<int,int>> q;
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    
    // 从边界上的 0 开始 BFS
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ((i == 0 || i == n-1 || j == 0 || j == n-1) && a[i][j] == 0) {
                q.push({i, j});
                visited[i][j] = true;
            }
        }
    }
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && a[nx][ny] == 0) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    
    // 将未访问的 0 变为 2
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 0 && !visited[i][j]) {
                a[i][j] = 2;
            }
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

易错点

⚠️ 注意：

  1. 无向图的边要添加两次
  2. 注意自环和重边
  3. 邻接矩阵适合稠密图，邻接表适合稀疏图
  4. 图的遍历要标记访问