深度優(yōu)先遍歷代碼

//////深度優(yōu)先遍歷接口For連通圖

///publicvoidDFSTraverse()

//////深度優(yōu)先遍歷算法

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

//////寬度優(yōu)先遍歷接口For連通圖

///publicvoidBFSTraverse()

//////寬度優(yōu)先遍歷算法

//////頂點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;

//訪問此頂點的所有鄰接節(jié)點

while(node!=null)

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

if(node.adjvex.isVisited==false)

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