遞歸計數深度

我們有一些輸入鏈接：
「http://test.com」此鏈接有鏈接：
「http://test.com」，「http://test.com/some 」，「http://google.com」
和「http://test.com/some」有聯繫：「http://facebook.com」，「some.com」
遞歸計數深度

所需結果：
步驟主要：0鏈接：「http://test.com」 ExtLinksCount：1個

步驟主要：1條鏈路：「http://test.com/some」 ExtLinksCount：2

我算的extlinks，但我不知道怎麼算的遞歸

public void info(String url) throws IOException { 

     if (!parsedLinks.contains(url)) { 

      parsedLinks.add(url); 
      String[] links = hp.getLinks(url); 
      System.out.println("Link : " + url + "\n" 
           +"ExtLinksCount : " + externalLinksCount(links) + "\n" 
           +"Steps to main : " + step 
          ); 
      String strippedLink; 

      for (int i = 0; i < links.length; i++) { 

       strippedLink = LinkParser.parseLink(links[i]); 

       if (strippedLink.contains(this.baseUrl)) { 
        ++ step; 
        info(links[i]); 
       } 


      } 
     } 

    }

來源

2012-09-16 incredible_titan

一步如何添加變量「步」到你的構造。你已經有了增加它的代碼。

來源

2012-09-16 06:55:10 hatcyl

我已經在counstructor這個變量。但它不計算深度，因爲它只適用於遞歸的一個分支 –

我不知道如何計算遞歸的所有分支 –

@incredible_titan我認爲@hatcyl的意思是讓'step'成爲方法並在每次遞歸調用中增加它：'public void info（String url，int step）{[...] info（link，step + 1）; [...]}'。如果'step'在'info'之外被定義，它會計數*累計*步數。但請注意，雖然會準確測量遞歸的深度，但它不一定會讓您達到某個URL的最低步數。 –

如果您想確定從「主」URL開始到達某個URL所需的步驟數，跟蹤深度並不總能得到您想要的結果，因爲遞歸實現的行爲與深度優先搜索。

請考慮以下圖表：A -> [B, C]; B -> [C]。調用info(A)，您將遍歷鏈接到B和C.首先，您撥打info(B)，將距離（A，B）設置爲1.現在，從撥打電話info(B)，撥打info(C)，設置距離（A，C）到2. info(C)和info(B)返回，並且您再次調用info(C)，這次是從info(A)，但此調用立即返回而沒有將距離（A，C）更新爲1，因爲C已經在解析鏈接集中。

使用遞歸，你可以嘗試這樣的事情（僞）：

info(url): 
    for link in links(url): 
     if link not in visited or visited[link] > visited[url] + 1: 
      visited[link] = visited[url] + 1 
      info(link)

其中visited是地圖，URL映射到從主URL的距離，被初始化，以便visited[main] = 0。然而，這仍然將參觀一些聯繫多次，所以這將是更有效地使用廣度優先搜索：

info(main): 
    visited = map{main: 0} 
    queue = queue(main) 
    while queue not empty: 
     url = queue.pop() 
     for link in links(url): 
      if link not in visited: 
       visited[link] = visited[url] + 1 
       queue.append(link)

來源

2012-09-16 10:06:49

感謝您的解決方案） –

遞歸計數深度

回答

相關問題