python——图

class ArcNode:
    def __init__(self,adjvex = None, weight= 0,nextarc = None):
        self.adjvex = adjvex
        self.weight = weight
        self.nextarc = None
        
class VNode:
    def __init__(self,data = None, firstarc = None):
        self.data=data
        self.firstarc =firstarc
        
class AdjGraph:
    def __init__(self,adjlist=[],n=0,e=0):#adjlist列表的元素就是VNode
        self.adjlist=adjlist
        self.n=n
        self.e=e

inf = float("inf")        
class MatGraph:
    def __init__(self, n):               #n表示顶点的个数
        self.n = n
        self.edges = [[inf] * n for i in range(n) ]
        #对角线上的元素值取0
        for i in range(n):
            self.edges[i][i]=0
        

    def add_edge(self, u, v, w = 1): #此代码是针对无向图，两顶点直接关联，默认权值为1，注意输入图形的边时的下标
        self.edges[u][v] = w
        self.edges[v][u] = w

    def show(self):
        for i in self.edges:
            for j in i:
                print('{:<8.0f}'.format(j),end='')  #占位8位，小数点取0位左对齐
            print('')        
def MattoList(g):
    n=g.n
    adjlist=[VNode(None,None) for i in range(n)]
    G=AdjGraph(adjlist,n)
    for i in range(n):
        G.adjlist[i].data = i
        for j in range(n-1,-1,-1):
            if (g.edges[i][j]!=0 and g.edges[i][j]!=inf):
                p=ArcNode(j,g.edges[i][j])
                #采用头插法进行插入结点p
                p.nextarc = G.adjlist[i].firstarc
                G.adjlist[i].firstarc = p
    G.n = g.n  
    return G

def DispAdj(G):
    for i in range(G.n):
        vdata = G.adjlist[i].data
        print('%3d---->'%vdata,end='')
        p=G.adjlist[i].firstarc
        while(p!=None):
            print("%3d--->"%p.adjvex,end='')
            p=p.nextarc
        print("^\n")   
  

      
        
if __name__ == '__main__':
    g=MatGraph(5)
   
    g.add_edge(0,1)
    g.add_edge(0,4)
    g.add_edge(1,0)
    g.add_edge(1,4)
    g.add_edge(4,1)
    g.add_edge(4,3)
    g.add_edge(1,3)
    g.add_edge(1,2)
    g.add_edge(2,3)
    g.add_edge(3,4)
    print("\n邻接矩阵：")
    g.show()   
    print("\n邻接表：")
    G= MattoList(g)
    DispAdj(G)