您现在的位置是：首页 > Python

当前栏目

Kruskal算法（python实现）

Python 算法

2023-03-02 11:48:05 时间

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)\]

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

Kruskal算法（python实现）

相关文章