

Python实现“维基百科六度分隔理论“之最终版【优化版】

CDA数据分析师

2017-04-02

导读：前面两篇分别说了简单的爬虫从一个页面到另一个页面，以及用MySQL数据库存储爬取到的数据。但是还有许多需要改进的地方，今天来优化完善一下之前的内容。

戳蓝字关注我们！

作者 Airy

本文转自AiryData，转载需授权

前言

前面两篇分别说了简单的爬虫从一个页面到另一个页面，以及用MySQL数据库存储爬取到的数据。但是还有许多需要改进的地方，今天来优化完善一下之前的内容。

有向图和无向图

前面的爬虫体现了一种从一个页面指向另一个页面的链接路径选择问题，这个是有向图问题，其中AB连通，并不意味着BA同样连通，比我百度搜索我的网站，可以跳转到我的网站，但是我的网站如果不添加百度的链接的话，是不能跳转到百度的。

但是，原来的凯文·贝肯六度分割游戏是一个无向图问题，即凯文·贝肯的维基百科词条有链接到他合作的演员的链接，同样与他合作的演员的维基百科词条也有链接到凯文·贝肯的词条，这两者的关系是相互的（即没有方向性），这是无向图问题。

在寻找有向图的最短路径的问题中，即找出维基百科中凯文·贝肯词条与其他词条之间最短链接路径的方法中，效果最好的且最常用的一种方法是广度优先搜索算法。

广度优先搜索算法（BFS）

广度优先搜索算法（breadth-first search）的思路是优先搜索直接连接到起始页的所有链接（而不是找到一个链接进行纵向深入搜索）。如果这些链接步包含目标页面（我们想要找的词条），就对第二层的链接——连接到起始页的页面的所有链接——进行搜索。这个过程不断重复（递归），直到达到搜索深度限制（我们使用的层数限制是6层，因为是六度分割）或者找到目标页面为止。

昨天我们已经获得了十几万条链接并存储到了数据库中，今天我们来实现一个完整的广度优先搜索算法（BFS），代码如下：

from urllib.request import urlopen
from bs4 import BeautifulSoup
import pymysql

conn = pymysql.connect(host = '127.0.0.1', port = 3306, user = 'root', passwd = '12345678', db = 'wiki', charset = 'utf8mb4')

cur = conn.cursor()

class SolutionFound(RuntimeError):
  def __init__(self, message):
  self.message = message

def getLinks(fromPageId):
cur.execute("SELECT toPageId FROM links WHERE fromPageId = %s", (fromPageId))
  if cur.rowcount == 0:
  return None
  else:
  return [x[0] for x in cur.fetchall()]

def constructDict(currentPageId):
links = getLinks(currentPageId)
  if links:
  return dict(zip(links, [{}]*len(links)))
  return {}

#链接树要么为空，要么包含多个链接
def searchDepth(targetPageId, currentPageId, linkTree, depth):
  if depth == 0:
  #停止递归，返回结果
  return linkTree
  if not linkTree:
linkTree = constructDict(currentPageId)
  if not linkTree:
  #若此节点页面无链接，则跳过此节点
  return {}
  if targetPageId in linkTree.keys():
  print("TARGET" + str(targetPageId) + "FOUND!")
  raise SolutionFound("PAGE: " + str(currentPageId))

  for branchKey, branchValue in linkTree.items():
  try:
  #递归建立链接树
linkTree[branchKey] = searchDepth(targetPageId, branchKey, branchValue, depth - 1)
  except SolutionFound as e:
  print (e.message)
  raise SolutionFound("PAGE: "+ str(currentPageId))
  return linkTree

try:
searchDepth(134951, 1, {}, 4)
  print("No solution found")
except SolutionFound as e:
  print (e.message)

这里函数getLinks和constructDict是辅助函数，用来用数据库里获取给定页面的链接，然后把链接转换成字典，主函数searchDepth会递归执行，同时构建和搜索链接树，一次搜索一层，运行规则如下：

如果递归限制已经到达（即程序已经调用过多次），就停止搜索，返回结果。
如果函数获取的链接字典是空的，就对当前页面的链接进行搜索。如果当前页面也没链接，就返回空链接字典。
如果当前页面包含我们搜索的页面链接，就把页面ID复制到递归的栈顶，然后抛出一个异常，显示页面已经找到。递归过程中的每个栈都会打印当前页面的ID，然后抛出异常显示页面已经找到，最终打印在屏幕上的就是一个完整的页面ID路径列表。
如果链接没找到，把递归限制减1，然后调用函数搜索下一层链接。

小结

这里我们对之前的算法进行了优化，使用了BFS算法提高效率，加深我们对之前知识的了解，提高问题解决能力，希望大家更上一层楼。

希望通过上面的内容能帮助大家。如果你有什么好的意见，建议，或者有不同的看法，我都希望你留言和我们进行交流、讨论。