想看本篇文章英文版的點(diǎn)擊這里溶浴，收到谷歌 hr 郵件的我心血來潮乍迄，寫了篇英文版的，雖然中國朋友都不愛看（我知道）士败。闯两。。
這是我的算法課的第三個(gè) project谅将，第二個(gè)在這里漾狼。為什么我連學(xué)校的 project 都拿來寫文章分析呢。因?yàn)檫@課算是我研究生階段最難的課之一饥臂，布置的 project 也都是 NPC 級別的逊躁，這個(gè)沒有 NPC，也有 NP-intermediate 了隅熙，所拿來分析分析稽煤，總結(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)是否相對應(yīng)。也就是說站宗，圖p中的 A 點(diǎn)和 B 點(diǎn)間有一條邊闸准，那么圖g中也得有這么兩個(gè)點(diǎn)，M 和 N 間有一條邊梢灭；如果圖p中 A 和 B 間沒有邊夷家，那么圖g中相對應(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)樣式畫出來膀曾，那么其實(shí)就很容易看出來怎么求那個(gè)小圓環(huán)了。比如下面這個(gè)小圖：
我們可以畫一棵相應(yīng)的小樹：
其實(shí)這里我們就能看出來阳啥，2 這個(gè)點(diǎn)是4和6的共同的孩子節(jié)點(diǎn)。那么我們只要 bfs 遍歷這棵樹财喳，找到這個(gè)共同的節(jié)點(diǎn)就好了察迟。用一個(gè) label[] 去標(biāo)識走過的點(diǎn)，2會(huì)走兩遍耳高，第二次經(jīng)過它的時(shí)候就知道它這里有個(gè)環(huán)了扎瓶。
因?yàn)槲矣玫?swift 做 project 的，所以我用的是 array 來做的泌枪。我刷 leetcode
用的是 java概荷。 C++ 太麻煩了，還是不用了碌燕。误证。因?yàn)槲覀兝蠋熯€要我們 plot 出不用節(jié)點(diǎn)數(shù)的圖的時(shí)間的 performance。修壕。愈捅。Swift 還有個(gè)好處就是我可以用 iOS 作圖，比較方便慈鸠。而且 swift 的 array 可以當(dāng) linkedlist 用蓝谨。但是我們還是可以做一個(gè) node 來存儲沒個(gè)點(diǎn)的深度信息 depth。
class Node {
public int vertex, depth;
public Node(int vertex, int depth) {
this.vertex = vertex;
this.depth = depth;
}
}
其實(shí)用什么語言都無所謂青团，如果你用 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 的時(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))锨阿。
