本文由本人@takooctopus对LeetCode每日打卡签到，做点记录。

847. Shortest Path Visiting All Nodes

题目描述:

An undirected, connected graph of N nodes (labeled 0, 1, 2, …, N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example

Note:

{{- code -}}

Solution

Heapq Solution

{{- code -}}

上面是堆排序的方法：

其中memo为一个空集合，final的值为$ 2^{N}-1 $，即两点路径总数，q作为一个列表，保存了[(0,0,2^0), ..., (0,N,2^N)]共N+1个元素。注意q中元素实际上在循环内用作[steps, node, state]表示了其各个Node的状态。

heappop()返回最小的元素。

我们考虑二级的for循环：

其中state实际使用了二进制，对于节点i，其只有第i位为1。首先其状态state与1 << v抑或，将这条路径中加入新的节点v。

再将这一步后新产生的(steps+1, 新节点, 新路径)压入堆中。

再加入集合memo表示已经算过这条路径。

直到将所有点的与其他点的关系全部算清。

然后我们根据steps的数值从小到大依此取出列表q的元素。因为我们要将其全部走一遍，所以我们最终需要的是状态在2进制下N位全为一，换成10进制就是$ 2^{N}-1 $，即我们定义的final的值。

即当我们状态states == final时，我们就能得到最短步数了。

BFS Solution

{{- code -}}

上面的相比之下为广度优先的搜索：

判断的原理和堆排差不多，q依旧表示[node, state]，但这次每走一步都会留下这一步的快照，并将其看作下一步开始状态。

因为是按照步数走，所以只要走完所有点，就一定为最小步数。

Deque Solution

{{- code -}}

上面是队列搜索：

在这里使用了collection.deque()，也能通过appendleft()从左侧添加。同理也有pop()以及poplect()。

我们最开始选择初始点，将其从collection左侧依次取出，当(更新的状态, 要去的节点)不重复时，将(要去的节点，steps, 更新的状态)新加进集合的右侧。

循环往复，也是将steps从小到大搜索，直到我们最终发现状态state更新为全部走过。