python实现基本数据结构第四篇（图：字典存储，邻接矩阵存储，邻接表存储）_数据结构图python实现

图是比树更复杂的一种数据结构。图中各个数据元素之间存在着多对多的关系，实际上日常生活中大部分关系都是图的关系，很多关系交错在一起就组成了一个规模很大的图，既然图这么重要，那么现在我们就谈谈如何在计算机中存储图这种数据元素存在多对多关系的数据结构。

当然，图分为无向图和有向图，至于基本概念，度娘里有很多，这里就不多赘述了。
图的字典形式存储python实现：
图中的每个顶点，都是字典中的键，和该顶点有边相连的顶点列表，就是该键的值。

class Graph():
    def __init__(self):
        nodelist = list(map(str,input('请输入图中的结点，以空格分开：').split(' ')))
        self.graph = {
   }
        for node in nodelist:
            flag = True
            node_bian = list(map(str,input('请输入以%s为起始点的边的终端点，没有边用"#"代替：' %node).split(' ')))
            if "#" in node_bian:
                self.graph[node] = []
            else:
                for i in node_bian:
                    if i not in nodelist:
                        flag = False
                        print('输入的终端结点中有结点不是图中的结点，请重新创建图。')
                        break
                self.graph[node] = node_bian
                if flag == False:
                    break

    def print_Graph(self):
        '''
        打印图
        :return:
        '''
        for i, j in self.graph.items():
            print('%s:%s' % (i, j))


    def generatePath(self,graph,path,end,results):
        '''
        构建指定路径
        :param graph: Graph
        :param path: list
        :param end: string
        :param results: list
        :return:list
        '''
        self.graph = graph
        state = path[-1]
        if state == end:
            results.append(path)
        else:
            for arc in self.graph[state]:
                if arc not in path:
                    self.generatePath(graph, path + [arc], end, results)


    def searchGraph(self,graph,start,end):
        '''
        从图中找出指定路径
        :param graph: Graph
        :param start: string
        :param end: string
        :return: list
        '''
        self.graph = graph
        results = []
        self.generatePath(self.graph, [start], end, results)  # 生成路径
        results.sort(key=lambda x: len(x))  # 按路径长短排序
        return results

    def print_all_path(self):
        '''
        输入指定起始点和终止点，在图中寻找和构建路径
        :return:
        '''
        start_node,end_node = map(str,input('请输入要查询的起始点和终止点（以空格分开）：').split(' '))
        r = self.searchGraph(self.graph,start_node,end_node)
        print("********* %s -------> %s 的所有路径 ************" %(start_node,end_node))
        for i in r:
            print(i)
        print("##################\n共计%d条路径" %len(r))
        for j in r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73