演算法的點點滴滴

並查集與十度好友

一、問題簡介     首先說下問題吧,這裡就不做廣告了,在社交網路中,假設A和B是好友,B和C是好友,如果A和C不是好友,那麼就說C是A的二度好友,在一個有10萬人人際網路中,如何在時間O(n)時間裡,找到某個人的十度好友。     查了下網上人們對這個問題解法的思路,大致有兩種觀點:(1)BFS; […]

線上演算法和離線演算法的概念

一、線上演算法   在電腦科學中,一個線上演算法是指它可以以序列化的方式一個個的處理輸入,也就是說在開始時並不需要已經知道所有的輸入。相對的,對於一個離線演算法,在開始時就需要知道問題的所有輸入資料,而且在解決一個問題後就要立即輸出結果。例如,選擇排序在排序前就需要知道所有待排序元素,然而插入排序就 […]

判斷無向圖和有向圖是否有迴路

一、無向圖迴路的判斷     對於無向圖,判斷其是否有迴路有四種方法,如下所示:     1、利用深度優先搜尋DFS,在搜尋過程中判斷是否會出現後向邊(DFS中,連線頂點u到它的某一祖先頂點v的邊),即在DFS對頂點進行著色過程中,若出現所指向的頂點為黑色,則此頂點是一個已經遍歷過的頂點(祖先),出 […]