深度優先遍歷代碼

//////深度優先遍歷接口For連通圖

///publicvoidDFSTraverse()

//////深度優先遍歷算法

//////頂點privatevoidDFS(Vertexv)

v.isVisited=true;//首先將訪問標志設為true標識為已訪問

Console.Write(v.data.ToString()+);//進行訪問操作：這里是輸出頂點data

Nodenode=v.firstEdge;

while(node!=null)

if(node.adjvex.isVisited==false)//如果鄰接頂點未被訪問

2.3.2廣度優先策略圖的廣度優先遍歷算法是一個分層遍歷的過程，和二叉樹的廣度優先遍歷類似，其基本思想在于：從圖中的某一個頂點Vi觸發，訪問此頂點后，依次訪問Vi的各個為層訪問過的鄰接點，然后分別從這些鄰接點出發，直至圖中所有頂點都被訪問到。對于上圖所示的無向連通圖，若從頂點V1開始，則廣度優先遍歷的頂點訪問順序是V1→V2→V3→V4→V5→V6→V7→V8。廣度優先遍歷代碼：

//////寬度優先遍歷接口For連通圖

///publicvoidBFSTraverse()

//////寬度優先遍歷算法

//////頂點privatevoidBFS(Vertexv)

v.isVisited=true;//首先將訪問標志設為true標識為已訪問

Console.Write(v.data.ToString()+);//進行訪問操作：這里是輸出頂點data

QueueverQueue=newQueue();//使用隊列存儲

verQueue.Enqueue(v);

while(verQueue.Count>0)

Vertexw=verQueue.Dequeue();

Nodenode=w.firstEdge;

//訪問此頂點的所有鄰接節點

while(node!=null)

//如果鄰接節點沒有被訪問過則訪問它的邊

if(node.adjvex.isVisited==false)

搜索引擎蜘蛛如何爬行URL并形成快照僅作了解。2.3.3反向鏈接數策略?反向鏈接數是指一個網頁被其他網頁鏈接指向的數量。反向鏈接數表示的是一個網頁的內容受到其他人的推薦的程度。因此，很多時候搜索引擎的抓取系統會使用這個指標來評價網頁的重要程度，從而決定不同網頁的抓取先后順序。?在真實的網絡環境中，由于廣告鏈接、作弊鏈接的存在，反向鏈接數不能完全等他我那個也的重要程度。因此，搜索引擎往往考慮一些可靠的反向鏈接數。2.3.4PartialPageRank策略?PartialPageRank算法借鑒了PageRank算法的思想：對于已經下載的網頁，連同待抓取URL隊列中的URL，形成網頁集合，計算每個頁面的PageRank值，計算完之后，將待抓取URL隊列中的URL按照PageRank值的大小排列，并按照該順序抓取頁面。?如果每次抓取一個頁面，就重新計算PageRank值，一種折中方案是：每抓取K個頁面后，重新計算一次PageRank值。但是這種情況還會有一個問題：對于已經下載下來的頁面中分析出的鏈接，也就是我們之前提到的未知網頁那一部分，暫時是沒有PageRank值的。為了解決這個問題，會給這些頁面一個臨時的PageRank值：將這個網頁所有入鏈傳遞進來的PageRank值進行匯總，這樣就形成了該未知頁面的PageRank值，從而參與排序。下面舉例說明：2.3.5OPIC策略策略?該算法實際上也是對頁面進行一個重要性打分。在算法開始前，給所有頁面一個相同的初始現金（cash）。當下載了某個頁面P之后，將P的現金分攤給所有從P中分析出的鏈接，并且將P的現金清空。對于待抓取URL隊列中的所有頁面按照現金數進行排序。?2.3.6大站優先策略?對于待抓取URL隊列中的所有網頁，根據所屬的網站進行分類。對于待下載頁面數多的網站，優先下載。這個策略也因此叫做大站優先策略。三、網絡爬蟲分類?開發網絡爬蟲應該選擇Nutch、Crawler4j、WebMagic、scrapy、WebCollector還是其他的？上面說的爬蟲，基本可以分3類：?（1）分布式爬蟲：Nutch?（2）JAVA爬蟲：Crawler4j、WebMagic、WebCollector?（3）非JAVA爬蟲：scrapy（基于Python語言開發）?3.1分布式爬蟲?爬蟲使用分布式，主要是解決兩個問題：?1)海量URL管理?2)網速?現在比較流行的分布式爬蟲，是Apache的Nutch。但是對于大多數用戶來說，Nutch是這幾類爬蟲里，最不好的選擇，理由如下：?1)Nutch是為搜索引擎設計的爬蟲，大多數用戶是需要一個做精準數據爬取（精抽取）的爬蟲。Nutch運行的一套流程里，有三分之二是為了搜索引擎而設計的。對精抽取沒有太大的意義。也就是說，用Nutch做數據抽取，會浪費很多的時間在不必要的計算上。而且如果你試圖通過對Nutch進行二次開發，來使得它適用于精抽取的業務，基本上就要破壞Nutch的框架，把Nutch改的面目全非，有修改Nutch的能力，真的不如自己重新寫一個分布式爬蟲框架了。?2)Nutch依賴hadoop運行，hadoop本身會消耗很多的時間。如果集群機器數量較少，爬取速度反而不如單機爬蟲快。?3)Nutch雖然有一套插件機制，而且作為亮點宣傳。可以看到一些開源的Nutch插件，提供精抽取的功能。但是開發過Nutch插件的人都知道，Nutch的插件系統有多蹩腳。利用反射的機制來加載和調用插件，使得程序的編寫和調試都變得異常困難，更別說在上面開發一套復雜的精抽取系統了。而且Nutch并沒有為精抽取提供相應的插件掛載點。Nutch的插件有只有五六個掛載點，而這五六個掛載點都是為了搜索引擎服務的，并沒有為精抽取提供掛載點。大多數Nutch的精抽取插件，都是掛載在“頁面解析”(parser)這個掛載點的，這個掛載點其實是為了解析鏈接（為后續爬取提供URL），以及為搜索引擎提供一些易抽取的網頁信息(網頁的meta信息、text文本)。?4)用Nutch進行爬蟲的二次開發，爬蟲的編寫和調試所需的時間，往往是單機爬蟲所需的十倍時間不止。了解Nutch源碼的學習成本很高，何況是要讓一個團隊的人都讀懂Nutch源碼。調試過程中會出現除程序本身之外的各種問題(hadoop的問題、hbase的問題)。?5)很多人說Nutch2有gora，可以持久化數據到avro文件、hbase、mysql等。很多人其實理解錯了，這里說的持久化數據，是指將URL信息（URL管理所需要的數據）存放到avro、hbase、mysql。并不是你要抽取的結構化數據。其實對大多數人來說，URL信息存在哪里無所謂。?6)Nutch2的版本目前并不適合開發。官方現在穩定的Nutch版本是nutch2.2.1，但是這個版本綁定了gora-0.3。如果想用hbase配合nutch（大多數人用nutch2就是為了用hbase)，只能使用0.90版本左右的hbase，相應的就要將hadoop版本降到hadoop0.2左右。而且nutch2的官方教程比較有誤導作用，Nutch2的教程有兩個，分別是Nutch1.x和Nutch2.x，這個Nutch2.x官網上寫的是可以支持到hbase0.94。但是實際上，這個Nutch2.x的意思是Nutch2.3之前、Nutch2.2.1之后的一個版本，這個版本在官方的SVN中不斷更新。而且非常不穩定（一直在修改）。?所以，如果你不是要做搜索引擎，盡量不要選擇Nutch作為爬蟲。有些團隊就喜歡跟風，非要選擇Nutch來開發精抽取的爬蟲，其實是沖著Nutch的名氣（Nutch作者是DougCutting），當然最后的結果往往是項目延期完成。?如果你是要做搜索引擎，Nutch1.x是一個非常好的選擇。Nutch1.x和solr或者es配合，就可以構成一套非常強大的搜索引擎了。如果非要用Nutch2的話，建議等到Nutch2.3發布再看。目前的Nutch2是一個非常不穩定的版本。?分布式爬蟲平臺架構圖?3.2JAVA爬蟲?這里把JAVA爬蟲單獨分為一類，是因為JAVA在網絡爬蟲這塊的生態圈是非常完善的。相關的資料也是最全的。這里可能有爭議，我只是隨便談談。?其實開源網絡爬蟲（框架）的開發非常簡單，難問題和復雜的問題都被以前的人解決了（比如DOM樹解析和定位、字符集檢測、海量URL去重），可以說是毫無技術含量。包括Nutch，其實Nutch的技術難點是開發hadoop，本身代碼非常簡單。網絡爬蟲從某種意義來說，類似遍歷本機的文件，查找文件中的信息。沒有任何難度可言。之所以選擇開源爬蟲框架，就是為了省事。比如爬蟲的URL管理、線程池之類的模塊，誰都能做，但是要做穩定也是需要一段時間的調試和修改的。?對于爬蟲的功能來說。用戶比較關心的問題往往是：?1）爬蟲支持多線程么、爬蟲能用代理么、爬蟲會爬取重復數據么、爬蟲能爬取JS生成的信息么？?不支持多線程、不支持代理、不能過濾重復URL的，那都不叫開源爬蟲，那叫循環執行http請求。?能不能爬js生成的信息和爬蟲本身沒有太大關系。爬蟲主要是負責遍歷網站和下載頁面。爬js生成的信息和網頁信息抽取模塊有關，往往需要通過模擬瀏覽器(htmlunit,selenium)來完成。這些模擬瀏覽器，往往需要耗費很多的時間來處理一個頁面。所以一種策略就是，使用這些爬蟲來遍歷網站，遇到需要解析的頁面，就將網頁的相關信息提交給模擬瀏覽器，來完成JS生成信息的抽取。?2）爬蟲可以爬取ajax信息么？?網頁上有一些異步加載的數據，爬取這些數據有兩種方法：使用模擬瀏覽器（問題1中描述過了），或者分析ajax的http請求，自己生成ajax請求的url，獲取返回的數據。如果是自己生成ajax請求，使用開源爬蟲的意義在哪里？其實是要用開源爬蟲的線程池和URL管理功能（比如斷點爬取）。?如果我已經可以生成我所需要的ajax請求（列表），如何用這些爬蟲來對這些請求進行爬取？?爬蟲往往都是設計成廣度遍歷或者深度遍歷的模式，去遍歷靜態或者動態頁面。爬取ajax信息屬于deepweb（深網）的范疇，雖然大多數爬蟲都不直接支持。但是也可以通過一些方法來完成。比如WebCollector使用廣度遍歷來遍歷網站。爬蟲的第一輪爬取就是爬取種子集合(seeds)中的所有url。簡單來說，就是將生成的ajax請求作為種子，放入爬蟲。用爬蟲對這些種子，進行深度為1的廣度遍歷（默認就是廣度遍歷）。?3）爬蟲怎么爬取要登陸的網站？?這些開源爬蟲都支持在爬取時指定cookies，模擬登陸主要是靠cookies。至于cookies怎么獲取，不是爬蟲管的事情。你可以手動獲取、用http請求模擬登陸或者用模擬瀏覽器自動登陸獲取cookie。?4）爬蟲怎么抽取網頁的信息？?開源爬蟲一般都會集成網頁抽取工具。主要支持兩種規范：CSSSELECTOR和XPATH。至于哪個好，這里不評價。?5）爬蟲怎么保存網頁的信息？?有一些爬蟲，自帶一個模塊負責持久化。比如webmagic，有一個模塊叫pipeline。通過簡單地配置，可以將爬蟲抽取到的信息，持久化到文件、數據庫等。還有一些爬蟲，并沒有直接給用戶提供數據持久化的模塊。比如crawler4j和webcollector。讓用戶自己在網頁處理模塊中添加提交數據庫的操作。至于使用pipeline這種模塊好不好，就和操作數據庫使用ORM好不好這個問題類似，取決于你的業務。?6）爬蟲被網站封了怎么辦？?爬蟲被網站封了，一般用多代理（隨機代理）就可以解決。但是這些開源爬蟲一般沒有直接支持隨機代理的切換。所以用戶往往都需要自己將獲取的代理，放到一個全局數組中，自己寫一個代理隨機獲取（從數組中）的代碼。?7）網頁可以調用爬蟲么？?爬蟲的調用是在Web的服務端調用的，平時怎么用就怎么用，這些爬蟲都可以使用。?8）爬蟲速度怎么樣？?單機開源爬蟲的速度，基本都可以講本機的網速用到極限。爬蟲的速度慢，往往是因為用戶把線程數開少了、網速慢，或者在數據持久化時，和數據庫的交互速度慢。而這些東西，往往都是用戶的機器和二次開發的代碼決定的。這些開源爬蟲的速度，都很可以。?9）明明代碼寫對了，爬不到數據，是不是爬蟲有問題，換個爬蟲能解決么？?如果代碼寫對了，又爬不到數據，換其他爬蟲也是一樣爬不到。遇到這種情況，要么是網站把你封了，要么是你爬的數據是javascript生成的。爬不到數據通過換爬蟲是不能解決的。?10）哪個爬蟲可以判斷網站是否爬完、那個爬蟲可以根據主題進行爬取？?爬蟲無法判斷網站是否爬完，只能盡可能覆蓋。?至于根據主題爬取，爬蟲之后把內容爬下來才知道是什么主題。所以一般都是整個爬下來，然后再去篩選內容。如果嫌爬的太泛，可以通過限制URL正則等方式，來縮小一下范圍。?11）哪個爬蟲的設計模式和構架比較好？?設計模式純屬扯淡。說軟件設計模式好的，都是軟件開發完，然后總結出幾個設計模式。設計模式對軟件開發沒有指導性作用。用設計模式來設計爬蟲，只會使得爬蟲的設計更加臃腫。?至于構架，開源爬蟲目前主要是細節的數據結構的設計，比如爬取線程池、任務隊列，這些大家都能控制好。爬蟲的業務太簡單，談不上什么構架。?所以對于JAVA開源爬蟲，我覺得，隨便找一個用的順手的就可以。如果業務復雜，拿哪個爬蟲來，都是要經過復雜的二次開發，才可以滿足需求。?3.3非JAVA爬蟲?在非JAVA語言編寫的爬蟲中，有很多優秀的爬蟲。這里單獨提取出來作為一類，并不是針對爬蟲本身的質量進行討論，而是針對larbin、scrapy這類爬蟲，對開發成本的影響。?先說python爬蟲，python可以用30行代碼，完成JAVA50行代碼干的任務。python寫代碼的確快，但是在調試代碼的階段，python代碼的調試往往會耗費遠遠多于編碼階段省下的時間。使用python開發，要保證程序的正確性和穩定性，就需要寫更多的測試模塊。當然如果爬取規模不大、爬取業務不復雜，使用scrapy這種爬蟲也是蠻不錯的，可以輕松完成爬取任務。?上圖是Scrapy的架構圖，綠線是數據流向，首先從初始URL開始，Scheduler會將其交給Downloader進行下載，下載之后會交給Spider進行分析，需要保存的數據則會被送到ItemPipeline，那是對數據進行后期處理。另外，在數據流動的通道里還可以安裝各種中間件，進行必要的處理。因此在開發爬蟲的時候，最好也先規劃好各種模塊。我的做法是單獨規劃下載模塊，爬行模塊，調度模塊，數據存儲模塊。?對于C++爬蟲來說，學習成本會比較大。而且不能只計算一個人的學習成本，如果軟件需要團隊開發或者交接，那就是很多人的學習成本了。軟件的調試也不是那么容易。?還有一些ruby、php的爬蟲，這里不多評價。的確有一些非常小型的數據采集任務，用ruby或者php很方便。但是選擇這些語言的開源爬蟲，一方面要調研一下相關的生態圈，還有就是，這些開源爬蟲可能會出一些你搜不到的BUG（用的人少、資料也少）四、反爬蟲技術?因為搜索引擎的流行，網絡爬蟲已經成了很普及網絡技術，除了專門做搜索的Google，Yahoo，微軟，百度以外，幾乎每個大型門戶網站都有自己的搜索引擎，大大小小叫得出來名字得就幾十種，還有各種不知名的幾千幾萬種，對于一個內容型驅動的網站來說，受到網絡爬蟲的光顧是不可避免的。?一些智能的搜索引擎爬蟲的爬取頻率比較合理，對網站資源消耗比較少，但是很多糟糕的網絡爬蟲，對網頁爬取能力很差，經常并發幾十上百個請求循環重復抓取，這種爬蟲對中小型網站往往是毀滅性打擊，特別是一些缺乏爬蟲編寫經驗的程序員寫出來的爬蟲破壞力極強，造成的網站訪問壓力會非常大，會導致網站訪問速度緩慢，甚至無法訪問。?一般網站從三個方面反爬蟲：用戶請求的Headers，用戶行為，網站目錄和數據加載方式。前兩種比較容易遇到，大多數網站都從這些角度來反爬蟲。第三種一些應用ajax的網站會采用，這樣增大了爬取的難度。4.1通過Headers反爬蟲?從用戶請求的Headers反爬蟲是最常見的反爬蟲策略。很多網站都會對Headers的User-Agent進行檢測，還有一部分網站會對Referer進行檢測（一些資源網站的防盜鏈就是檢測Referer）。如果遇到了這類反爬蟲機制，可以直接在爬蟲中添加Headers，將瀏覽器的User-Agent復制到爬蟲的Headers中；或者將Referer值修改為目標網站域名[評論：往往容易被忽略，通過對請求的抓包分析，確定referer，在程序中模擬訪問請求頭中添加]。對于檢測Headers的反爬蟲，在爬蟲中修改或者添加Headers就能很好的繞過。4.2基于用戶行為反爬蟲?還有一部分網站是通過檢測用戶行為，例如同一IP短時間內多次訪問同一頁面，或者同一賬戶短時間內多次進行相同操作。[這種防爬，需要有足夠多的ip來應對]?大多數網站都是前一種情況，對于這種情況，使用IP代理就可以解決。可以專門寫一個爬蟲，爬取網上公開的代理ip，檢測后全部保存起來。這樣的代理ip爬蟲經常會用到，最好自己準備一個。有了大量代理ip后可以每請求幾次更換一個ip，這在requests或者urllib2中很容易做到，這樣就能很容易的繞過第一種反爬蟲。[評論：動態撥號也是一種解決方案]?對于第二種情況，可以在每次請求后隨機間隔幾秒再進行下一次請求。有些有邏輯漏洞的網站，可以通過請求幾次，退出登錄，重新登錄，繼續請求來繞過同一賬號短時間內不能多次進行相同請求的限制。[評論：對于賬戶做防爬限制，一般難以應對，隨機幾秒請求也往往可能被封，如果能有多個賬戶，切換使用，效果更佳4.3動態頁面的反爬蟲?上述的幾種情況大多都是出現在靜態頁面，還有一部分網站，我們需要爬取的數據是通過ajax請求得到，或者通過Java生成的。首先用Firebug或者HttpFox對網絡請求進行分析[評論：感覺google的、IE的網絡請求分析使用也挺好]。如果能夠找到ajax請求，也能分析出具體的參數和響應的具體含義，我們就能采用上面的方法，直接利用requests或者urllib2模擬ajax請求，對響應的json進行分析得到需要的數據。能夠直接模擬ajax請求獲取數據固然是極好的，但是有些網站把ajax請求的所有參數全部加密了。我們根本沒辦法構造自己所需要的數據的請求。我這幾天爬的那個網站就是這樣，除了加密ajax參數，它還把一些基本的功能都封裝了，全部都是在調用自己的接口，而接口參數都是加密的。遇到這樣的網站，我們就不能用上面的方法了，我用的是selenium+phantomJS框架，調用瀏覽器內核，并利用phantomJS執行js來模擬人為操作以及觸發頁面中的js腳本。從填寫表單到點擊按鈕再到滾動頁面，全部都可以模擬，不考慮具體的請求和響應過程，只是完完整整的把人瀏覽頁面獲取數據的過程模擬一遍用這套框架幾乎能繞過大多數的反爬蟲，因為它不是在偽裝成瀏覽器來獲取數據（上述的通過添加Headers一定程度上就是為了偽裝成瀏覽器），它本身就是瀏覽器，phantomJS就是一個沒有界面的瀏覽器，只是操控這個瀏覽器的不是人。利用selenium+phantomJS能干很多事情，例如識別點觸式（12306）或者滑動式的驗證碼，對頁面表單進行暴力破解等等。它在自動化滲透中還會大展身手，以后還會提到這個。