python 实现有向图的邻接表

python 实现有向图的邻接表

事实上，用c++实现邻接表实在是太烦了，用链表实现，不同类的指针。索性用python随手写一个，用的是字典。
顺便加了bfs与dfs

看一下输入

【输入形式】
每一组第一行有两个数n、m表示n个顶点，m条有向边。
输入顶点信息，并用空格隔开，顶点信息以大写字母表示
接下来有m行，每行三个数u、v、w代表权值为w的一条由u到v的有向边
注意： 2<=n<=10，n<m<=10，w为正整数，输入保证没有自环

class graph():
    def __init__(self):
        self.g={} #字典

    def realize_matrix(self,edge):
        for i in edge:
            start, end, weight = i[0], i[1], int(i[2])
            if start not in self.g.keys():
                self.g[start] = {end: weight}
            else:
                self.g[start].update({end: weight})

    def BSF(self,start):
        bfs=[]
        queue=[]
        queue.append(start)
        seen = set()
        seen.add(start)
        while (len(queue)>0):
            vertex=queue.pop(0)
            try: #用try的原因是不想用collections中的库
                nodes = self.g[vertex].keys()
            except KeyError:
                nodes=None
            try:
                for w in nodes:
                    if w not in seen:
                        queue.append(w)
                        seen.add(w)
            except TypeError:
                pass
            bfs.append(vertex)
        return bfs


    def DSF(self,start): #事实上dsf与bsf的代码很像
        dfs=[]
        stack=[]
        stack.append(start)
        seen = set()
        seen.add(start)
        while (len(stack)>0):
            vertex=stack.pop()
            try:
                nodes = self.g[vertex].keys()
            except KeyError:
                nodes=None
            try:
                for w in nodes:
                    if w not in seen:
                        stack.append(w)
                        seen.add(w)
            except TypeError:
                pass
            dfs.append(vertex)
        return dfs


n,m=map(int,input().split()) #输入数据
vem =list(input().split()) #输入顶点
edge =[]  #用列表存储数据
for i in range(m):
    element =tuple(input().split())
    edge.append(element)

G=graph()
G.realize_matrix(edge)
for i in G.BSF('A'):
    print(i,end=' ')

print()
for i in G.DSF('A'):
    print(i, end=' ')


'''
4 3
A B C D
A B 1
B C 1
B D 1

5 7
A B C D E
A B 1 
B C 1
B D 1
C B 1
C D 1
C E 1
E A 1
'''