题目特点

PAT甲级中，图论题目主要集中在单源最短路、图的遍历上，此外还有可能将二者结合。由于PAT中数据量不大、对时间复杂度要求也不高，因此采用邻接矩阵存图、朴素版Dijkstra算法即可。

常见题型

图的遍历

dfs遍历，参照 回溯法
bfs遍历，需要使用队列。一起放入队列的，还可以节点所处的层数。这种方式就可以只遍历到距离小于某个值的节点。

while(!q.empty()){
    auto t = q.front();
    q.pop();
    int node = t.first;
    int idx = t.second;
    if (idx <= l && st[node] == 0){
        st[node] = 1;
        cnt++;
        for (int i = 0; i < path[node].size(); i++){
            q.push({path[node][i], idx + 1});
        }
    }
}

最短路+其他尺度的更新与选择

这类题型往往是试图让求出两点之间的最优路径，这个路径可能不仅要求距离最短，还要求统计最短路径的数量、或者在距离相同的情况下花费最小等等，涉及第二尺度的更新。这些第二尺度的更新，若是具有最优子结构（单纯依靠上一点的值进行更新），如开销、路径数等，那么往往在找到一条集合外的点到源点的最短距离，然后对大家到源点的距离试图更新的时候进行。如果需要针对一整条路径综合来看，那么可以先把所有最短路保存下来，最后dfs来选择路径。
拿一个统计最短路径数的题目作为例子，给出一个解题模板：

memset(dis, 0x3f, sizeof dis); // 初始化距离dis数组
dis[c1] = 0; //源点距离设置为0
num[c1] = 1; //源点的路径数设置为1
for (int i = 0; i < n - 1; i++){
    int t = -1;
    for (int j = 0; j < n; j++){
        if (st[j] == 0 && (t == -1 || dis[j] < dis[t])){ //找到没遍历过的最近的点
            t = j;
        }
    }
    st[t] = 1;
    for (int j = 0; j < n; j++){
        //分为距离和已经找到的相同和更小两种情况
        //相同，距离不变，其他变量择优更新
        if (dis[j] == dis[t] + path[t][j]){ 
            num[j] += num[t];
        }
        //如果更小，更新最短路，并且强制更新其他变量。
        else if (dis[j] > dis[t] + path[t][j]){
            dis[j] = dis[t] + path[t][j];
            num[j] = num[t];
        }
    }
}

如果变量需要在后期dfs的时候更新，那么只需要在更新其他路径的时候，把这个点作为前驱节点存下来即可。可参考如下代码：

for (int j = 0; j <= n; j++){
    if (dis[j] > dis[t] + path[t][j]) {
        shortPath[j].clear();
        shortPath[j].push_back(t);
        dis[j] = dis[t] + path[t][j];
    } else if (dis[j] == dis[t] + path[t][j]) {
        shortPath[j].push_back(t);
    }
}

而后dfs遍历（从终点到起点），到达起点时计算这一条边上的第二尺度变量。选择最优路径。

注意点

1. 由于题目常常是具体问题抽象出来的图，因此可能不会明确说明是双向边还是单向边，但是需要自己判断（比如公路之类的一般是双向的）。
2. 注意图和dis数组的初始化步骤。
3. 注意点的标号，从0开始还是从1开始，这会决定遍历时的迭代。
4. 题目可能给出的图的标号用的是字符串，可以用map对字符串和数字做一个映射（如果仅多一个字符如G1，那么直接加上一个大整数做映射即可）
5. PAT甲级使用英文题面，若发现有部分测试点一直出错，可以再仔细阅读一遍题目，看看是否有条件漏掉（比如答案需要排序之类的）

总结

总体来说，题目有一定套路性而言，但是代码量不小。不必过分畏难，但需多加练习。