1

入力にいくつかのリンクがあります:
"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]);
                }


            }
        }

    }
4

2 に答える 2

0

コンストラクターに変数「step」を追加するのはどうですか。あなたはすでにそれをインクリメントするためのコードを持っています。

于 2012-09-16T06:55:10.330 に答える
0

「メイン」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-16T10:06:49.573 に答える