图的同构和 Girth 问题
想看本篇文章英文版的点击这里，收到谷歌 hr 邮件的我心血来潮，写了篇英文版的，虽然中国朋友都不爱看（我知道）。。。
这是我的算法课的第三个 project，第二个在这里。为什么我连学校的 project 都拿来写文章分析呢。因为这课算是我研究生阶段最难的课之一，布置的 project 也都是 NPC 级别的，这个没有 NPC，也有 NP-intermediate 了，所拿来分析分析，总结一下经验，还是很有帮助的。我学什么都非常讲究方法，我个人觉得方法比努力重要，就像选择比努力重要一样。当然不努力也白搭。。
Requirement
我已经把我们 project 的要求放在了 Github上。 如果你想自己尝试一下，你可以点击 这里，做一做我们学校的作业，你如果感兴趣，我可以把我们学校的所有课程内容发给你哈。
当然 source code 也放在 Github上了。
图同构问题
最上面显示的那个就是最经典的图同构问题的模型。目前最快的图同构问题解决方案是 NAUTY，就用到了这个模型，很眼熟吧？
其实这个问题在现在的计算机界或者数学界，反正什么届里都还算是一个未能完全解决的问题。在 wikipedia 上还有这么个问题呢：
Unsolved problem in computer science:
Can the graph isomorphism problem be solved in polynomial time?
我才疏学浅，不讨论那些高深的话题，我只讲一讲最基础的实现方式，用 backtracking，然后检查是否符合要求。
基本思想是检查两个图中的每个点是否相对应。也就是说，图p中的 A 点和 B 点间有一条边，那么图g中也得有这么两个点，M 和 N 间有一条边；如果图p中 A 和 B 间没有边，那么图g中相对应的那两个点，也不可以有边。用 backtracking 遍历每种情况，然后 checkEdges()。下面是伪代码
bool DFS(int n, int level, int[][] graph1, int[][] graph2, int[] used, int[] perm) {
bool result = false;
if (level == -1) {
result = checkEdges(n, graph1, graph2);
} else {
index i = 0;
while (i < n && result == false) {
if (used[i] == false) {
used[i] = true;
perm[level] = i;
result = DFS(n, level - 1, graph1, graph2, used, perm);
}
i++;
}
}
return result;
}
检查是否相同：
bool checkEdges(int n, int[][] graph1, int[][] graph2) {
bool same = true;
for x = 0 to n - 1 {
index y = 0;
while (y > 0 && same == true) {
if (graph1[x][y] != graph2[perm[x]][perm[y]]) {
same = false;
}
y++;
}
}
return same;
}
这个算法的时间复杂度是 O(N2*N!)，N 是顶点的数量。
Girth of Graph
不知道怎么翻译，就用 Girth 吧。反正就是在一个图中存在的最小圆环。我们老师 pdf 上的定义是：
The shortest cycle in a graph G is called the girth of G.
如果我们把图用树的结构样式画出来，那么其实就很容易看出来怎么求那个小圆环了。比如下面这个小图：
我们可以画一棵相应的小树：
其实这里我们就能看出来，2 这个点是4和6的共同的孩子节点。那么我们只要 bfs 遍历这棵树，找到这个共同的节点就好了。用一个 label[] 去标识走过的点，2会走两遍，第二次经过它的时候就知道它这里有个环了。
因为我用的 swift 做 project 的，所以我用的是 array 来做的。我刷 leetcode
用的是 java。 C++ 太麻烦了，还是不用了。。因为我们老师还要我们 plot 出不用节点数的图的时间的 performance。。。Swift 还有个好处就是我可以用 iOS 作图，比较方便。而且 swift 的 array 可以当 linkedlist 用。但是我们还是可以做一个 node 来存储没个点的深度信息 depth。
class Node {
public int vertex, depth;
public Node(int vertex, int depth) {
this.vertex = vertex;
this.depth = depth;
}
}
其实用什么语言都无所谓，如果你用 java，你可以用 ArrayDeque(), 或者LinkedList()，C++ 的话可以用 std::queue<int>，都差不多。下面是 bfs 遍历的主要过程：
while(node != null && short > 3 && (node.depth + 1)* 2 - 1 < short)
{
int depth = node.depth + 1;
for (int neighbor in node.vertex’s all neighbor)
{
// if we haven’t went through this neighbor
if (label[neighbor] < 0) {
queue.add(new Node(neighbor, depth));
label[neighbor] = depth;
} else if (label[neighbor] == depth - 1) {
// odd neighbors
if (depth * 2 -1 < short)
short = depth * 2 - 1;
} else if (label[neighbor] == depth) {
// even neighbors
if (depth * 2 < short)
short = depth * 2;
}
}
// go another node
node = queue’s first element, and remove the first element;
}
// start a new bfs from another vertex
remove all elements from queue;
root++;
我们都知道 bfs 的时间复杂度是 O(m + n)，其中m和n分别是点和边的数量。因为这个算法需要尝试每个点作为root，从每个点都出发做一次 bfs 寻找最小圈，所以外层还有个循环，while(root < n - 2 && short > 3). 所以时间复杂度是 O(n * (m + n))。
