本文共 569 字，大约阅读时间需要 1 分钟。

图论问题主要分为：

BFSorDFS搜索，关键在于剪枝。 AOVorAOE图，关键在于排序，找关键路径。

---

问题A：

POJ1659 给出N个顶点度数，判断是否可图？

贪心方法尝试构图，时间O(NNlogN)

每次找出度数最大的点，与其后数个点构成边，构成边后，两个顶点度数-1。

但凡有一个顶点不能构成边，则不可图。

---

问题B：

POJ1465 给定一个5000以内的正整数N，给定M个10以内的非负数，则存在N的最小倍数的每一位都由M中数字组成，返回这个数。

逆向思维BFS，由M个数字从1位扩展到k位，来构造合法数字，保证从小到大，从而判断是否可以整除N。

同余剪枝，若a已经处理过，则出现b%B == a%N，b不再考虑，同余则代表小于N的部分相同，只能通过在末尾添加数字来改变，所以两种情况相同。

状态压缩，状态太多，每个状态都由大数(位数接近1000)表示，空间开销大。使用挂链的方式，每个后继位置的新数字指向之前数字，形成一条数字链，不同的状态可以共用数字。

---

问题C：

POJ1324 给定一个迷宫最大20*20，迷宫里可能有墙，给定迷宫里一条蛇，长度最多为7，蛇在移动时不可碰墙或自身，则到达指定位置步数？

BFS+状态压缩

关键在于蛇状态的保存，利用2位二进制表示四种状态蛇身，上下左右，则通过蛇头可以推断出连续蛇身的位置。

---

转载地址：http://udwji.baihongyu.com/