基于Queue与Graph类实现演员Kevin Bacon数计算功能

需求说明 #

• 目前已实现Queue类与Graph类两个基础工具类

第一部分：实现kevin_bacon_number函数 #

函数定义如下：

kevin_bacon_number(moviegraph, actor)

功能：计算指定演员在电影图中的Kevin Bacon数。
测试要求：运行以下代码应返回1（因为De Niro, Robert和Kevin Bacon共同出演过同一部电影）：

g = Graph('movies.txt', False, '/')
kevin_bacon_number(g, 'De Niro, Robert')

第二部分：实现actors_with_number函数 #

函数定义如下：

actors_with_number(moviegraph, number)

功能：返回Kevin Bacon数等于指定数值的所有演员列表。
测试要求：

1. 运行以下代码应返回Bacon, Kevin：

g = Graph('movies.txt', False, '/')
actors_with_number(g, 0)

2. 'De Niro, Robert' in actors_with_number(g, 1)的判定结果应为True。

已实现基础类代码 #

Queue类 #

class Queue:

    #-------------------------------------------------------------------

    # 构造空的Queue对象

    def __init__(self):
        self._first = None  # 指向第一个_Node节点
        self._last = None   # 指向最后一个_Node节点
        self._length = 0    # 元素数量

    #-------------------------------------------------------------------

    # 队列空返回True，否则返回False

    def isEmpty(self):
        return self._first is None

    #-------------------------------------------------------------------

    # 将item添加到队列尾部

    def enqueue(self, item):
        oldLast = self._last
        self._last = _Node(item, None)
        if self.isEmpty():
            self._first = self._last
        else:
            oldLast.next = self._last
        self._length += 1

    #-------------------------------------------------------------------

    # 移除队列头部元素并返回

    def dequeue(self):
        item = self._first.item
        self._first = self._first.next
        if self.isEmpty():
            self._last = None
        self._length -= 1
        return item

    #-------------------------------------------------------------------

    # 返回队列元素数量

    def __len__(self):
        return self._length

    #-------------------------------------------------------------------

    # 返回队列的字符串表示

    def __str__(self):
        s = ''
        cur = self._first
        while cur is not None:
            s += str(cur.item) + ' '
            cur = cur.next
        return s

#----------------------------------------------------------------------

_Node对象包含存储元素的item属性和指向下一个_Node对象的next属性，Queue实例由若干个_Node节点串联组成。

_Node类 #

class _Node:
    def __init__(self, item, next):
        self.item = item  # 元素引用
        self.next = next  # 下一个_Node对象的引用

Graph类 #

class Graph:

    # 构造Graph对象，如果传入filename参数，则按指定分隔符读取文件数据填充图
    # 有向图需将directed参数设为True
    def __init__(self,  filename=None, directed=False, delimiter=None):
        self._directed = directed
        self._e = 0
        self._adj = dict()
        if filename is not None:
            f = open(filename, 'r')
            lines = f.read().split('\n')
            for line in lines:
                names = line.split(delimiter)
                for i in range(1, len(names)):
                    self.addEdge(names[0], names[i])
            line = ''
                
    # 向图中添加顶点v和w之间的边
    def addEdge(self, v, w):
        if not self.hasVertex(v): self._adj[v] = set()
        if not self.hasVertex(w): self._adj[w] = set()
        if not self.hasEdge(v, w):
            self._e += 1
            self._adj[v].add(w)
            if not self._directed: self._adj[w].add(v)
            
    # 返回顶点v的所有邻接顶点的可迭代集合
    def adjacentTo(self, v):
        return iter(self._adj[v])
    
    # 返回图中所有顶点的可迭代集合
    def vertices(self):
        return iter(self._adj)

    # 顶点v在图中存在返回True，否则返回False
    def hasVertex(self, v):
        return v in self._adj

    # 边v-w在图中存在返回True，否则返回False
    def hasEdge(self, v, w):
        return w in self._adj[v]
    
    # 返回图中顶点数量
    def countV(self):
        return len(self._adj)
    
    # 返回图中边数量
    def countE(self):
        return self._e
    
    # 返回顶点v的度
    def degree(self, v):
        return len(self._adj[v])

    # 返回图的字符串表示
    def __str__(self):
        s = ''
        for v in self.vertices():
            s += v + '  '
            for w in self.adjacentTo(v):
                s += w + ' '
            s += '\n'
        return s

内容的提问来源于stack exchange，提问作者Zahid Riaz