查看“︁霍普克洛夫特-卡普算法”︁的源代码

{{noteTA
|G1=IT
}}
{{Expert|time=2010-11-21}}
{{unreferenced|time=2009-07-22T13:14:54+00:00}}
{{图算法}}

'''霍普克洛夫特－卡普算法'''（'''Hopcroft Karp算法'''）是用來解決[[二分圖]]最大[[匹配]]問題的一種演算法。

在[[匈牙利算法]]中，我们每次寻找一条增广路来增加匹配集合M。可以证明，每次找增广路的复杂度是<math>\mathcal{O}\left( \left|E\right| \right)</math>，一共需要增广<math>\mathcal{O}\left(\left|V\right|\right)</math>次，因此总时间复杂度为<math>\mathcal{O}\left(\left|V\right|\left|E\right|\right)</math>。为了降低时间复杂度，在霍普克洛夫特－卡普算法中，我们在增加匹配集合M时，每次寻找多条增广路。可以证明，这样[[迭代]]次数最多为<math>2\sqrt{\left|V\right|}</math>，所以，时间复杂度就降到了<math>\mathcal{O}\left(\sqrt{\left|V\right|}\left|E\right|\right)</math>。

该算法由[[約翰·霍普克洛夫特]]和[[理查德·卡普]]于1973年提出。

<syntaxhighlight lang="pascal">
program Project1;
  const maxn=1000;
  var dx,dy,mx,my,q:array[1..maxn]of longint;
      adj:array[1..maxn,0..maxn]of longint;
      n,m,e,i,j,ans,ff,rr:longint;
  function bfs:boolean;
    var i,u,j:longint;
    begin
      bfs:=false;
      fillchar(q,sizeof(q),0);
      rr:=1;
      ff:=1;
      for i:=1 to n do
      if mx[i]=-1
      then begin
        q[ff]:=i;
        inc(ff);
      end;
      for i:=1 to n do dx[i]:=0;
      for i:=1 to m do dy[i]:=0;
      while rr<ff do
        begin
          u:=q[rr];
          inc(rr);
          for j:=1 to adj[u][0]do
            begin
              i:=adj[u][j];
              if dy[i]=0
                then begin
                  dy[i]:=dx[u]+1;
                  if my[i]=-1
                    then bfs:=true
                    else begin
                      dx[my[i]]:=dy[i]+1;
                      q[ff]:=my[i];
                      inc(ff);
                    end;
                end;
            end;
        end;
    end;
  function dfs(x:longint):boolean;
    var i,j:longint;
    begin
      for j:=1 to adj[x][0]do
        begin
          i:=adj[x][j];
          if dy[i]=dx[x]+1
            then begin
              dy[i]:=0;
              if(my[i]=-1)or dfs(my[i])
                then begin
                  mx[x]:=i;
                  my[i]:=x;
                  exit(true);
                end;
            end;
        end;
      exit(false);
    end;
  begin
    readln(n,m,e);
    for i:=1 to e do
      begin
        readln(ff,rr);
        inc(adj[ff][0]);
        adj[ff][adj[ff][0]]:=rr;
      end;
    for i:=1 to n do mx[i]:=-1;
    for i:=1 to m do my[i]:=-1;
    ans:=0;
    while bfs do
      for i:=1 to n do
        if(mx[i]=-1)and(dfs(i))
          then inc(ans);
    writeln(ans);
  end.
</syntaxhighlight>

{{算法}}
[[Category:图算法]]