想看本篇文章英文版的點(diǎn)擊這里，收到谷歌 hr 郵件的我心血來(lái)潮，寫了篇英文版的，雖然中國(guó)朋友都不愛看（我知道）。。。
這是我的算法課的第三個(gè) project，第二個(gè)在這里。為什么我連學(xué)校的 project 都拿來(lái)寫文章分析呢。因?yàn)檫@課算是我研究生階段最難的課之一，布置的 project 也都是 NPC 級(jí)別的，這個(gè)沒有 NPC，也有 NP-intermediate 了，所拿來(lái)分析分析，總結(jié)一下經(jīng)驗(yàn)，還是很有幫助的。我學(xué)什么都非常講究方法，我個(gè)人覺得方法比努力重要，就像選擇比努力重要一樣。當(dāng)然不努力也白搭。。
Requirement
我已經(jīng)把我們 project 的要求放在了 Github上。 如果你想自己嘗試一下，你可以點(diǎn)擊 這里，做一做我們學(xué)校的作業(yè)，你如果感興趣，我可以把我們學(xué)校的所有課程內(nèi)容發(fā)給你哈。
當(dāng)然 source code 也放在 Github上了。
圖同構(gòu)問題
最上面顯示的那個(gè)就是最經(jīng)典的圖同構(gòu)問題的模型。目前最快的圖同構(gòu)問題解決方案是 NAUTY，就用到了這個(gè)模型，很眼熟吧？
其實(shí)這個(gè)問題在現(xiàn)在的計(jì)算機(jī)界或者數(shù)學(xué)界，反正什么屆里都還算是一個(gè)未能完全解決的問題。在 wikipedia 上還有這么個(gè)問題呢：
Unsolved problem in computer science:
Can the graph isomorphism problem be solved in polynomial time?
我才疏學(xué)淺，不討論那些高深的話題，我只講一講最基礎(chǔ)的實(shí)現(xiàn)方式，用 backtracking，然后檢查是否符合要求。
基本思想是檢查兩個(gè)圖中的每個(gè)點(diǎn)是否相對(duì)應(yīng)。也就是說(shuō)，圖p中的 A 點(diǎn)和 B 點(diǎn)間有一條邊，那么圖g中也得有這么兩個(gè)點(diǎn)，M 和 N 間有一條邊；如果圖p中 A 和 B 間沒有邊，那么圖g中相對(duì)應(yīng)的那兩個(gè)點(diǎn)，也不可以有邊。用 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;
}
這個(gè)算法的時(shí)間復(fù)雜度是 O(N2*N!)，N 是頂點(diǎn)的數(shù)量。
Girth of Graph
不知道怎么翻譯，就用 Girth 吧。反正就是在一個(gè)圖中存在的最小圓環(huán)。我們老師 pdf 上的定義是：
The shortest cycle in a graph G is called the girth of G.
如果我們把圖用樹的結(jié)構(gòu)樣式畫出來(lái)，那么其實(shí)就很容易看出來(lái)怎么求那個(gè)小圓環(huán)了。比如下面這個(gè)小圖：
我們可以畫一棵相應(yīng)的小樹：
其實(shí)這里我們就能看出來(lái)，2 這個(gè)點(diǎn)是4和6的共同的孩子節(jié)點(diǎn)。那么我們只要 bfs 遍歷這棵樹，找到這個(gè)共同的節(jié)點(diǎn)就好了。用一個(gè) label[] 去標(biāo)識(shí)走過(guò)的點(diǎn)，2會(huì)走兩遍，第二次經(jīng)過(guò)它的時(shí)候就知道它這里有個(gè)環(huán)了。
因?yàn)槲矣玫?swift 做 project 的，所以我用的是 array 來(lái)做的。我刷 leetcode
用的是 java。 C++ 太麻煩了，還是不用了。。因?yàn)槲覀兝蠋熯€要我們 plot 出不用節(jié)點(diǎn)數(shù)的圖的時(shí)間的 performance。。。Swift 還有個(gè)好處就是我可以用 iOS 作圖，比較方便。而且 swift 的 array 可以當(dāng) linkedlist 用。但是我們還是可以做一個(gè) node 來(lái)存儲(chǔ)沒個(gè)點(diǎn)的深度信息 depth。
class Node {
public int vertex, depth;
public Node(int vertex, int depth) {
this.vertex = vertex;
this.depth = depth;
}
}
其實(shí)用什么語(yǔ)言都無(wú)所謂，如果你用 java，你可以用 ArrayDeque(), 或者LinkedList()，C++ 的話可以用 std::queue<int>，都差不多。下面是 bfs 遍歷的主要過(guò)程：
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 的時(shí)間復(fù)雜度是 O(m + n)，其中m和n分別是點(diǎn)和邊的數(shù)量。因?yàn)檫@個(gè)算法需要嘗試每個(gè)點(diǎn)作為root，從每個(gè)點(diǎn)都出發(fā)做一次 bfs 尋找最小圈，所以外層還有個(gè)循環(huán)，while(root < n - 2 && short > 3). 所以時(shí)間復(fù)雜度是 O(n * (m + n))。
