图的表示方法

在算法竞赛中，选择合适的图的表示方法对于算法的性能和代码的简洁性至关重要。本节介绍两种主要的图表示方法。

邻接矩阵表示法

【定义】邻接矩阵是一个二维数组，用于表示顶点之间的连接关系。如果顶点i和j之间有一条边，则matrix[i][j]等于这条边的权值（无权图则为1），否则为0或无穷大。

邻接矩阵的C++实现

const int MAXN = 1000;  // 最大顶点数
int graph[MAXN][MAXN];  // 邻接矩阵

// 初始化图
void initGraph(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                graph[i][j] = 0;  // 自己到自己的距离为0
            } else {
                graph[i][j] = INT_MAX;  // 初始化为无穷大，表示不可达
            }
        }
    }
}

// 添加边（有向图）
void addEdge(int from, int to, int weight) {
    graph[from][to] = weight;
}

// 添加边（无向图）
void addUndirectedEdge(int u, int v, int weight) {
    graph[u][v] = weight;
    graph[v][u] = weight;  // 无向图需要添加两条边
}

邻接矩阵的优缺点

优点：

  1. 实现简单，容易理解
  2. 查询两点是否有边的时间复杂度为O(1)
  3. 适合稠密图（边数接近顶点数的平方）
  4. 方便实现Floyd等算法

缺点：

  1. 空间复杂度为O(V²)，对于大型图会消耗大量内存
  2. 对于稀疏图（边数远小于顶点数的平方）效率低下
  3. 添加/删除顶点的操作复杂度高

邻接表表示法

【定义】邻接表使用一个顶点数组，每个顶点维护一个链表，存储与该顶点相连的所有顶点和边的信息。

邻接表的C++实现

使用STL的vector实现：

const int MAXN = 100000;  // 最大顶点数

// 边的结构
struct Edge {
    int to;      // 目标顶点
    int weight;  // 权值

    Edge(int _to, int _weight) : to(_to), weight(_weight) {}
};

vector<Edge> graph[MAXN];  // 邻接表

// 添加边（有向图）
void addEdge(int from, int to, int weight) {
    graph[from].push_back(Edge(to, weight));
}

// 添加边（无向图）
void addUndirectedEdge(int u, int v, int weight) {
    graph[u].push_back(Edge(v, weight));
    graph[v].push_back(Edge(u, weight));
}

// 遍历从顶点u出发的所有边
void traverseEdges(int u) {
    for (const Edge& e : graph[u]) {
        cout << "Edge from " << u << " to " << e.to 
             << " with weight " << e.weight << endl;
    }
}

邻接表的优缺点

优点：

  1. 空间复杂度为O(V+E)，适合稀疏图
  2. 快速查找顶点的所有邻居
  3. 添加边的操作简单高效
  4. 适合实现Dijkstra、Kruskal等算法

缺点：

  1. 查询两点之间是否有边需要O(degree)时间
  2. 实现相对复杂
  3. 不适合需要频繁查询两点连接关系的场景

其他表示方法

链式前向星

链式前向星是邻接表的一种静态实现，在某些竞赛中很常用：

const int MAXN = 10005;  // 最大顶点数
const int MAXM = 100005; // 最大边数

struct Edge {
    int to, weight, next;
} edges[MAXM];

int head[MAXN]; // 每个顶点的第一条边的索引
int cnt = 0;    // 边的计数器

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

// 添加边
void addEdge(int from, int to, int weight) {
    edges[cnt].to = to;
    edges[cnt].weight = weight;
    edges[cnt].next = head[from];
    head[from] = cnt++;
}

// 遍历从顶点u出发的所有边
void traverseEdges(int u) {
    for (int i = head[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        int w = edges[i].weight;
        // 处理边(u,v,w)
    }
}

选择合适的表示方法

选择图的表示方法时，考虑以下因素：

  1. 图的稠密程度：稠密图选择邻接矩阵，稀疏图选择邻接表
  2. 需要的操作：频繁查询连接关系选择邻接矩阵
  3. 内存限制：内存受限时选择邻接表
  4. 算法需求：某些算法在特定表示下实现更容易

竞赛实战技巧

  1. 在ACM竞赛中，通常使用vector<vector<int>>或vector<vector<pair<int,int>>>实现邻接表，代码简洁且灵活
  2. 对于静态图，链式前向星效率高，且容易实现
  3. 在处理大规模图时，注意内存限制，选择合适的表示方法
  4. 邻接矩阵适合Floyd算法，邻接表适合Dijkstra和BFS/DFS

练习题目推荐

  1. 洛谷P3916 图的遍历
  2. POJ 1236 Network of Schools
  3. CodeForces 20C Dijkstra?

通过这些题目练习不同表示方法的使用场景和实现技巧。