当DFS遇上邻接表：一种被低估的图论问题解决范式

在算法竞赛和编程能力测试中，图论问题往往让选手们望而生畏。面对最短路径问题时，大多数人的第一反应是套用Dijkstra算法——这几乎成了一种条件反射。但今天我们要探讨的是一种经常被低估的解决方案：DFS（深度优先搜索）与邻接表的黄金组合。

1. 重新认识DFS在图论中的应用价值

深度优先搜索常被视为"暴力搜索"的代名词，但在特定场景下，它却能展现出惊人的效率与优雅。当问题满足以下条件时，DFS往往能成为比Dijkstra更合适的选择：

• 节点规模有限 （N≤100）：小规模数据下，DFS的时间复杂度完全可以接受
• 双重优化目标 ：既要求路径最短，又要求换乘最少
• 特殊约束条件 ：如每个换乘点的线路不超过5条

传统的最短路径算法如Dijkstra虽然能高效解决单目标优化问题，但在面对"路径长度优先，换乘次数次优"的双重约束时，实现起来往往复杂且容易出错。相比之下，DFS可以自然地在搜索过程中同时追踪多个优化目标。

DFS在此类问题中的独特优势 ：

• 天然支持路径记录
• 可以灵活处理多个优化条件
• 代码实现通常比Dijkstra更简洁
• 对小规模图效率足够

2. 邻接表：图的高效表示法

邻接表是表示稀疏图的理想数据结构，特别适合处理像交通网络这样连接相对稀疏的场景。与邻接矩阵相比，邻接表在空间效率上具有明显优势：

vector<int> G[maxn]; // 邻接表表示

邻接表构建的关键步骤 ：

1. 读取每条线路的所有站点
2. 将相邻站点双向连接
3. 记录站点间的线路归属信息

for(int i = 1; i <= n; i++){
    cin >> m >> pre;
    for(int j = 2; j <= m; j++){
        cin >> tmp;
        G[pre].push_back(tmp);  // 双向连接
        G[tmp].push_back(pre);
        line[pre][tmp] = i;     // 记录线路归属
        line[tmp][pre] = i;
        pre = tmp;
    }
}

这种表示法不仅节省空间，还能快速访问任意节点的所有邻居，为DFS提供了理想的基础。

3. DFS实现的双重优化策略

在本题中，我们需要同时优化两个目标：经停站最少（主目标），换乘次数最少（次目标）。DFS可以优雅地处理这种多目标优化：

void dfs(int u, int end, int cnt){
    if(u == end){
        int trans = count(tempath); // 计算当前路径的换乘次数
        if(cnt < minCnt || (cnt == minCnt && trans < minTrans)){
            minCnt = cnt;
            minTrans = trans;
            path = tempath;
        }
        return;
    }
    // 递归搜索所有相邻节点
    for(int v : G[u]){
        if(!vis[v]){
            vis[v] = 1;
            tempath.push_back(v);
            dfs(v, end, cnt+1);
            vis[v] = 0;
            tempath.pop_back();
        }
    }
}

关键优化点 ：

• 实时记录当前路径
• 到达终点时比较并更新最优解
• 优先比较路径长度，长度相同时再比较换乘次数

4. 换乘次数统计的艺术

换乘次数的统计是本题的一个精妙之处。我们需要比较相邻路段是否属于同一线路：

int count(vector<int> a){
    int cnt = -1, preLine = 0; // 初始化为-1，因为第一次不算换乘
    for(int i = 1; i < a.size(); i++){
        if(line[a[i-1]][a[i]] != preLine) cnt++;
        preLine = line[a[i-1]][a[i]];
    }
    return cnt;
}

换乘统计逻辑 ：

1. 遍历路径中的每一段
2. 比较当前段与上一段的线路是否相同
3. 不同则增加换乘计数
4. 注意初始段的特殊处理

5. 路径输出的技巧

最终的路径输出需要满足特定格式要求，只显示起点、换乘点和终点：

int preLine = 0, preTrans = a; // 初始线路和换乘点
for(int j = 1; j < path.size(); j++){
    if(line[path[j-1]][path[j]] != preLine){
        if(preLine != 0) // 不是第一条线路
            printf("Go by the line of company #%d from %04d to %04d.\n", 
                  preLine, preTrans, path[j-1]);
        preLine = line[path[j-1]][path[j]];
        preTrans = path[j-1];
    }
}
// 输出最后一段
printf("Go by the line of company #%d from %04d to %04d.\n", 
      preLine, preTrans, b);

输出逻辑要点 ：

• 跟踪当前线路和上次换乘点
• 只在线路变更时输出前一段
• 最后单独处理终点段
• 注意格式化输出（如%04d保证4位数字）

6. 为什么不用Dijkstra？

虽然Dijkstra算法是解决最短路径问题的经典选择，但在本题的特定条件下，它存在几个明显劣势：

1. 多目标优化复杂 ：需要维护额外信息来处理换乘次数
2. 实现复杂度高 ：优先队列+复杂的状态表示
3. 对小规模图优势不明显 ：N≤100时，DFS的O(N!)最坏情况实际不会出现

DFS与Dijkstra的对比 ：

特性	DFS	Dijkstra
实现复杂度	简单	中等
多目标处理	自然支持	需要额外设计
时间复杂度	O(N!)最坏，但实际常可接受	O((N+M)logN)
空间复杂度	O(N)	O(N)
路径记录	直接	需要额外处理

7. 实战建议与常见陷阱

在实际编码实现时，有几个关键点需要特别注意：

常见陷阱 ：

• 忘记重置访问标记（vis数组）
• 换乘计数初始值设置错误
• 线路编号与数组索引混淆
• 输出格式不符合要求（如站点编号不足4位）

优化建议 ：

1. 预处理阶段仔细检查图的构建
2. 使用全局变量记录最优解和临时路径
3. 封装换乘计数函数提高代码可读性
4. 输出前先收集所有结果再统一格式化

// 初始化相关全局变量
minCnt = 1e9, minTrans = 1e9;
tempath.clear();
tempath.push_back(a);
vis[a] = 1;
dfs(a, b, 0);
vis[a] = 0; // 重要：重置起始点访问状态

8. 扩展思考：何时选择DFS而非传统最短路径算法

通过这个案例，我们可以总结出一些选择DFS而非Dijkstra等算法的场景判断标准：

1. 数据规模 ：节点数N≤200时值得考虑
2. 多目标优化 ：需要同时优化多个指标时
3. 路径记录需求 ：需要完整路径而非仅距离时
4. 特殊约束 ：存在换乘限制等特殊条件时
5. 实现时间 ：比赛或考试中快速实现的需求

在实际的算法竞赛中，这种"化繁为简"的思维往往比掌握更多复杂算法更重要。理解问题本质，选择最适合而非最强大的工具，是成为高水平选手的关键。