Kruskal算法（python实现）

Love The Way You Lie 2022-05-24 03:42 312阅读 0赞

class Graph:  
      def \_\_init\_\_(self,maps,unconn=0):  
            vnum=len(maps)  
            for x in maps:  
                  if len(x)!=vnum:  
                        raise ValueError  
            self.\_maps=\[maps\[i\]\[:\] for i in range(vnum)\]  
            self.\_unconn=unconn  
            self.\_vnum=vnum  
  
  
      def vertex\_num(self):  
            return self.\_vnum  
  
  
      def invalide(self):  
            return  x<0 or x>=self.\_vnum  
                   
  
  
      def add\_vertex(self):  
            raise GraphError  
  
  
      def add\_edges(self,x,y,weight):  
            if self.invalide(x) or self.invalide(y) or x==y or weight<0:  
                  raise Grapherror  
            self.\_maps\[x\]\[y\]=self.\_maps\[y\]\[x\]=weight  
  
  
      def get\_edges(self,x,y):  
            if self.invalide(x) or self.invalide(y):  
                  raise GraphError  
            return self.\_maps\[x\]\[y\]  
  
  
      def out\_edges(self,x):  
            \#if self.invalide(x):  
                  \#raise GraphError  
            return self.\_out\_edges(self.\_maps\[x\], self.\_unconn)  
      @staticmethod  
      def \_out\_edges(row, unconn):  
            edges=\[\]  
            for i in range(len(row)):  
                  if row\[i\]!=unconn:  
                        edges.append((i,row\[i\]))  
            return edges  
  
  
def Kruskal(graph):  
      vnum=graph.vertex\_num()  
      resp=\[i for i in range(vnum)\]  
      mst=\[\]  
      edges=\[\]  
      for x in range(vnum):  
            for y,w in graph.out\_edges(x):  
                  edges.append((w,x,y))  
      edges.sort()  
      for w,x,y in edges:  
            if resp\[x\]!=resp\[y\]:  
                  mst.append(((x,y),w))  
                  if len(mst)==vnum-1:  
                        break  
                  rep,orep=resp\[x\],resp\[y\]  
                  for i in range(vnum):  
                        if resp\[i\]==orep:  
                              resp\[i\]=rep  
      return mst  
  
  
inf=float("inf")  
graph=Graph(\[\[inf,5,11,5,inf,inf,inf\],  
            \[5,inf,inf,3,9,inf,7\],  
            \[11,inf,inf,7,inf,6,inf\],  
            \[5,3,7,inf,inf,inf,20\],  
            \[inf,9,inf,inf,inf,inf,8\],  
            \[inf,inf,6,inf,inf,inf,8\],  
            \[inf,7,inf,20,8,8,inf\]\])

print(Kruskal(graph))

输出说明：（（i，j），weight）表示i到j的路径 权重为weight

\[((1, 3), 3), ((0, 1), 5), ((2, 5), 6), ((1, 6), 7), ((2, 3), 7), ((4, 6), 8)\]