图的存储方式选择

图结构常见的存储方案有两种，需根据实际场景选用。

邻接矩阵适用于顶点规模较小的场景，采用二维数组实现：

int adj[MaxN][MaxN];  // adj[i][j] 表示 i 到 j 的边权

邻接表适用于边数较多的稀疏图，配合动态数组使用：

struct Arc {
    int dest;   // 目标顶点
    int cost;   // 边权
};
vector<Arc> adjList[MaxN];

// 添加边
void addEdge(int from, int to, int weight) {
    adjList[from].push_back({to, weight});
}

图的遍历框架

深度优先搜索（DFS）的核心在于递归访问未标记邻点，常用于连通块分析：

bool marked[MaxN];

void explore(int cur) {
    marked[cur] = true;
    for (int nxt : adjList[cur]) {
        if (!marked[nxt]) {
            explore(nxt);
        }
    }
}

void countComponents(int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (!marked[i]) {
            explore(i);
            cnt++;
        }
    }
}

Dijkstra 算法详解

该算法求解单源最短路径，要求边权非负。朴素实现时间复杂度为 O(V²)，适合稠密图：

const int INF = 0x3f3f3f3f;
int dist[MaxN];
bool finalized[MaxN];

void dijkstra(int src, int n) {
    fill(dist, dist + n, INF);
    dist[src] = 0;
    
    for (int round = 0; round < n; round++) {
        int u = -1, minDist = INF;
        for (int i = 0; i < n; i++) {
            if (!finalized[i] && dist[i] < minDist) {
                minDist = dist[i];
                u = i;
            }
        }
        if (u == -1) break;
        finalized[u] = true;
        
        for (int v = 0; v < n; v++) {
            if (adj[u][v] != INF && !finalized[v]) {
                if (dist[u] + adj[u][v] < dist[v]) {
                    dist[v] = dist[u] + adj[u][v];
                }
            }
        }
    }
}

带约束的最短路径问题

实际题目常需记录额外信息，如最短路径条数、最大点权等：

int pathCnt[MaxN], maxValue[MaxN], nodeWeight[MaxN];

void dijkstraEnhanced(int src, int n) {
    fill(dist, dist + n, INF);
    dist[src] = 0;
    pathCnt[src] = 1;
    maxValue[src] = nodeWeight[src];
    
    for (int round = 0; round < n; round++) {
        int u = -1, minDist = INF;
        for (int i = 0; i < n; i++) {
            if (!finalized[i] && dist[i] < minDist) {
                minDist = dist[i];
                u = i;
            }
        }
        if (u == -1) break;
        finalized[u] = true;
        
        for (int v = 0; v < n; v++) {
            if (adj[u][v] == INF || finalized[v]) continue;
            
            int newDist = dist[u] + adj[u][v];
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pathCnt[v] = pathCnt[u];
                maxValue[v] = maxValue[u] + nodeWeight[v];
            } else if (newDist == dist[v]) {
                pathCnt[v] += pathCnt[u];
                if (maxValue[u] + nodeWeight[v] > maxValue[v]) {
                    maxValue[v] = maxValue[u] + nodeWeight[v];
                }
            }
        }
    }
}

多维度路径回溯：Dijkstra + DFS

当存在多条最短路径需按第二指标筛选时，先用 Dijkstra 构建前驱树，再用 DFS 枚举：

vector<int> predecessor[MaxN];
vector<int> bestPath, tempPath;
int bestMetric = INF;

void dijkstraBuildTree(int src, int n) {
    fill(dist, dist + n, INF);
    dist[src] = 0;
    
    for (int round = 0; round < n; round++) {
        int u = -1, minDist = INF;
        for (int i = 0; i < n; i++) {
            if (!finalized[i] && dist[i] < minDist) {
                minDist = dist[i];
                u = i;
            }
        }
        if (u == -1) break;
        finalized[u] = true;
        
        for (int v = 0; v < n; v++) {
            if (adj[u][v] == INF || finalized[v]) continue;
            int newDist = dist[u] + adj[u][v];
            if (newDist < dist[v]) {
                dist[v] = newDist;
                predecessor[v].clear();
                predecessor[v].push_back(u);
            } else if (newDist == dist[v]) {
                predecessor[v].push_back(u);
            }
        }
    }
}

void dfsTrace(int cur, int src) {
    tempPath.push_back(cur);
    if (cur == src) {
        // 计算当前路径的第二指标
        int metric = evaluatePath(tempPath);
        if (metric < bestMetric) {
            bestMetric = metric;
            bestPath = tempPath;
        }
    } else {
        for (int pre : predecessor[cur]) {
            dfsTrace(pre, src);
        }
    }
    tempPath.pop_back();
}

字符串顶点的映射处理

处理地名等非整数标识时，需建立字符串到编号的映射：

unordered_map<string, int> idMap;
unordered_map<int, string> nameMap;
int assignId(const string& name) {
    if (idMap.count(name)) return idMap[name];
    int newId = idMap.size();
    idMap[name] = newId;
    nameMap[newId] = name;
    return newId;
}

并查集判连通分量

验证图是否为树结构时，需检查连通性：

int fa[MaxN];

int findRoot(int x) {
    return fa[x] == x ? x : fa[x] = findRoot(fa[x]);
}

void unite(int a, int b) {
    fa[findRoot(a)] = findRoot(b);
}

bool isTree(int n) {
    int comp = 0;
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) comp++;
    }
    return comp == 1;
}

广度优先搜索与层级控制

BFS 天然适合求解最短步数、最少转发次数等问题，通过结构体记录深度：

struct State {
    int vertex;
    int level;
};

int bfsLimited(int src, int limit, int n) {
    queue<State> q;
    bool visited[MaxN] = {false};
    q.push({src, 0});
    visited[src] = true;
    int reached = 0;
    
    while (!q.empty()) {
        State cur = q.front(); q.pop();
        for (int nxt : adjList[cur.vertex]) {
            if (!visited[nxt] && cur.level < limit) {
                visited[nxt] = true;
                reached++;
                q.push({nxt, cur.level + 1});
            }
        }
    }
    return reached;
}

最小生成树算法对比

拓扑排序与入度管理

有向无环图（DAG）的排序依赖入度为零的顶点：

vector<int> topoSort(int n) {
    vector<int> result;
    queue<int> zeroIn;
    
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) zeroIn.push(i);
    }
    
    while (!zeroIn.empty()) {
        int cur = zeroIn.front(); zeroIn.pop();
        result.push_back(cur);
        for (int nxt : adjList[cur]) {
            inDegree[nxt]--;
            if (inDegree[nxt] == 0) zeroIn.push(nxt);
        }
    }
    return result;
}