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

如何将变量“步骤”添加到您的构造函数。您已经有了增加它的代码。

于 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)再次调用 from 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)

wherevisited是一个映射，将 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 回答