Python中的Hopcroft–Karp算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在尝试使用networkx作为图形表示形式在Python中实现Hopcroft

Karp算法。

目前我对此：

#Algorithms for bipartite graphs
import networkx as nx
import collections
class HopcroftKarp(object):
    INFINITY = -1
    def __init__(self, G):
        self.G = G
    def match(self):
        self.N1, self.N2 = self.partition()
        self.pair = {}
        self.dist = {}
        self.q = collections.deque()
        #init
        for v in self.G:
            self.pair[v] = None
            self.dist[v] = HopcroftKarp.INFINITY
        matching = 0
        while self.bfs():
            for v in self.N1:
                if self.pair[v] and self.dfs(v):
                    matching = matching + 1
        return matching
    def dfs(self, v):
        if v != None:
            for u in self.G.neighbors_iter(v):
                if self.dist[ self.pair[u] ] == self.dist[v] + 1 and self.dfs(self.pair[u]):
                    self.pair[u] = v
                    self.pair[v] = u
                    return True
            self.dist[v] = HopcroftKarp.INFINITY
            return False
        return True
    def bfs(self):
        for v in self.N1:
            if self.pair[v] == None:
                self.dist[v] = 0
                self.q.append(v)
            else:
                self.dist[v] = HopcroftKarp.INFINITY
        self.dist[None] = HopcroftKarp.INFINITY
        while len(self.q) > 0:
            v = self.q.pop()
            if v != None:
                for u in self.G.neighbors_iter(v):
                    if self.dist[ self.pair[u] ] == HopcroftKarp.INFINITY:
                        self.dist[ self.pair[u] ] = self.dist[v] + 1
                        self.q.append(self.pair[u])
        return self.dist[None] != HopcroftKarp.INFINITY
    def partition(self):
        return nx.bipartite_sets(self.G)

该算法取自http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm，

但是它不起作用。我使用以下测试代码

G = nx.Graph([
(1,"a"), (1,"c"),
(2,"a"), (2,"b"),
(3,"a"), (3,"c"),
(4,"d"), (4,"e"),(4,"f"),(4,"g"),
(5,"b"), (5,"c"),
(6,"c"), (6,"d")
])
matching = HopcroftKarp(G).match()
print matching

不幸的是，这不起作用，我陷入了一个无休止的循环:(。有人可以发现错误，我没有主意，我必须承认我还没有完全理解算法，所以它主要是伪算法的实现。维基百科上的代码

回答：

线

if self.pair[v] and self.dfs(v):

应该

if self.pair[v] is None and self.dfs(v):

按照Wikipedia页面上的伪代码。我看到的唯一另一个问题是，您将双端队列用作堆栈，并且希望将其用作队列。为了解决这个问题，您只需要向左弹出而不是弹出（向右弹出）即可。所以线

v = self.q.pop()

应该

v = self.q.popleft()

希望其他所有东西都可以。我只是在检查您的Python代码是否与Wikipedia上的伪代码相同，因此希望该伪代码是正确的。

以上是 Python中的Hopcroft–Karp算法 的全部内容， 来源链接： utcz.com/qa/400691.html

回到顶部