python - 广度优先搜索 - 标准 Python 库

Question

我有一个问题需要解决，涉及公司相互控制利益。如果 A 拥有 B 超过 50% 的股份，或者如果 A 拥有一系列其他公司，这些公司加在一起拥有 B 超过 50% 的股份，则该公司控制另一家公司。

我使用代表与所有公司的所有关系的顶点和边图来解决这个问题。

我认为我需要实现的是广度优先搜索(或者Dijkstra 算法 最长路径而不是最短路径)，沿着公司之间的路径，只要从 A 到 B 的路径总和的权重大于 50%。我不知道如何实现它，因为我只能使用标准 Python 3.x 库 来解决这个问题。任何帮助将不胜感激!

示例输入

CompanyA CompanyB 30
CompanyB CompanyC 52
CompanyC CompanyD 51
CompanyD CompanyE 70
CompanyE CompanyD 20
CompanyD CompanyC 20

示例输出

CompanyA has a controlling interest in no other companies.
CompanyB has a controlling interest in CompanyC, CompanyD, and CompanyE.
CompanyC has a controlling interest in CompanyD, and CompanyE.
CompanyD has a controlling interest in CompanyE.
CompanyE has a controlling interest in no other companies.

到目前为止我的代码:

import sys

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

    def addNeighbour(self, nbr, weight = 0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + 'connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, nbr):
        return self.connectedTo[nbr]

class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVerticies = 0

    def addVertex(self, key):
        self.numVerticies = self.numVerticies + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self, n):
        return n in self.vertList

    def addEdge(self, f, t, cost = 0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbour(self.vertList[t], cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())

#all code above this line deals with the ADTs for Vertex and Graph objects
#all code below this line deals with taking input, parsing and output

def main():
    f = sys.argv[1] #TODO deal with standard input later
    temp = graphFunction(f)

def graphFunction(filename):
    openFile = open(filename, 'r')
    coList = []
    g = Graph()

    for line in openFile:
        lineSplit = line.split()
        g.addEdge(lineSplit[0], lineSplit[1], lineSplit[2])
        coList.append(lineSplit[0])
        coList.append(lineSplit[1])
    coSet = set(coList)
    coList = list(coSet) #converting this from a list to a set to a list removes all duplicate values within the original list
    openFile.close()

    #this is where there should be a Breadth First Search. Notthing yet, code below is an earlier attempt that kinda sorta works.

    newConnList = [] #this is a list of all the new connections we're going to have to make later
    for v in g: #for all verticies in the graph
        for w in v.getConnections(): #for all connections for each vertex
            #print("%s, %s, with weight %s" % (v.getId(), w.getId(), v.getWeight(w)))
            #print(v.getId(), w.getId(), v.getWeight(w))
            firstCo = v.getId()
            secondCo = w.getId()
            edgeWeight = v.getWeight(w)
            if int(edgeWeight) > 50: #then we have a controlling interest situation
                for x in w.getConnections():
                    firstCo2 = w.getId()
                    secondCo2 = x.getId()
                    edgeWeight2 = w.getWeight(x)
                    #is the secondCo2 already in a relationship with firstCo?
                    if x.getId() in v.getConnections():
                        #add the interest to the original interest
                        tempWeight = int(v.getWeight(x))
                        print(tempWeight)
                        tempWeight = tempWeight + int(w.getWeight(x))
                        newConnList.append((firstCo, secondCo2, tempWeight)) #and create a new edge
                        print('loop pt 1')
                    else:
                        newConnList.append((firstCo, secondCo2, edgeWeight2))
    for item in newConnList:
        firstCo = item[0]
        secondCo = item[1]
        edgeWeight = item[2]
        g.addEdge(firstCo, secondCo, edgeWeight)
        #print(item)
    for v in g:
        for w in v.getConnections():
            print(v.getId(), w.getId(), v.getWeight(w))

main()

Answer 1

我相信深度优先搜索会是更好的方法，因为您需要知道谁拥有谁。

所以，我所做的是创建一个名为 com.txt 的文本文件，并在其中:

A B 30
B C 52
C D 51
D E 70
E D 20
D C 20

这是脚本:

从集合中导入 defaultdict，双端队列

with open('com.txt', 'r') as companies:

    # Making a graph using defaultdict
    connections = defaultdict(list)
    for line in companies:
        c1, c2, p = line.split()
        connections[c1].append((c2, int(p)))

    for item in connections:
        q = deque([item])
        used = set()
        memory = []
        while q:
            c = q.pop()
            if c in connections and c not in used:
                memory.append(c)
                to_add = [key for key, cost in connections[c] if cost > 50]
                if to_add:
                    q.extend(to_add)
                    used.add(c)
                else:
                    break
        if len(memory) < 2:
            print(memory[0], "does not own any other company")
        else:
            owner = memory[0]
            comps = memory[1:]
            print(owner, "owns", end=' ')
            print(" and ".join(comps))
        del used

当我第一次制作连接列表时，我过滤掉了没有一家公司 50% 所有权的变量。这个脚本产生:

{'A': [('B', 30)], 'C': [('D', 51)], 'B': [('C', 52)], 'E': [('D', 20)], 'D': [('E', 70), ('C', 20)]}
A does not own any other company
C owns D and E
B owns C and D and E
E does not own any other company
D owns E

正如预期的那样。