数据结构--图

图的抽象数据类型简述

图的顶点集合、边集合、图形描述：

图有两种抽象数据类型：邻接矩阵、邻接表。
邻接矩阵很可能是稀疏的，如果直接存储，比较浪费存储空间。邻接表更加高效。

★上图就形象地表示了邻接表的数据结构。图对象的属性就只有verList和numVertices。顶点对象的属性也是上图所示。

邻接表中，每一个顶点对象都维护一个列表【实际上在python实现中用的是字典，键是顶点，值是权重】，其中记录了与它相连的顶点。
定义Vertex类，属性有字典，存储与该顶点邻接的顶点。

python实现

两个类：Graph【属性有：包含所有顶点的列表】、Vertex【属性有：包含所有邻接点的字典】

Vertex：
id属性：给顶点起个名字。
conected_to属性：记录相连顶点，是个字典。
add_neighbor方法：添加该点到另一个点的连接，注意要改变下conected_to属性。
get_connections方法：返回邻接表中所有顶点。
get_weight(nbr) 方法：返回从当前顶点到以参数传入的顶点之间的边的权重。
get_id方法：获取id。
重写 __str__方法：打印顶点信息。

Graph 类：
vertList属性：
numVertices属性：
addVertex方法：
getVertex方法：
addEdge方法：
getVertices方法: 返回所有顶点id。
重写__contains__方法：使得这个类对象可以用 in 关键字。
重写__iter__方法：使得这个类对象可以被循环迭代。这里返回vertList的值们转化成iter对象。

class Vertex:
    def __init__(self, key):
        self.id = key  # 顶点名
        self.connect_to = {}  # 字典存储关联顶点，键是顶点对象，值是边权重

    def get_connections(self):
        return self.connect_to.keys()

    def add_neighbor(self, nbr, weight=0):
        self.connect_to[nbr] = weight

    def get_id(self):
        return self.id

    def get_weight(self, nbr):
        return self.connect_to[nbr]

    def __str__(self):
        return self.id + 'connect to ' + str([x.id for x in self.connect_to])


# 顶点对象通过id属性获取顶点名
# 知道id，可以通过Graph的字典获取顶点对象

class Graph:
    def __init__(self):
        self.ver_list = {}  # 用来存储所有的顶点，键是顶点名，值是顶点对象
        self.num_ver = 0

    def add_vertex(self, id):
        """添加节点指数要输入id"""
        self.ver_list[id] = Vertex(id)
        self.num_ver += 1
        return self.ver_list[id]

    def get_vertex(self, key):
        if key in self.ver_list:
            return self.ver_list[key]
        else:
            return None

    def add_edge(self, f, v, weight):
        """在两个顶点之间添加边，这里传的f和v都是顶点的id名称"""
        # 如果这两个顶点不在该图中，需要自动添加
        if f not in self.ver_list:
            self.ver_list[f] = self.add_vertex(f)
        if v not in self.ver_list:
            self.ver_list[v] = self.add_vertex(v)
        self.ver_list[f].add_neighbor(self.ver_list[v], weight)  # 单向图只需要对f添加邻居，双向图要f和v都添加

    def __contains__(self, item):
        return item in self.ver_list

    def get_Vertices(self):
        return self.ver_list.keys()

    def __iter__(self):
        return iter(self.ver_list.values())


g = Graph()
for i in range(5):
    g.add_vertex(i)

g.add_edge(0, 1, 5)
g.add_edge(0, 5, 2)
g.add_edge(1, 2, 4)
g.add_edge(2, 3, 9)
g.add_edge(3, 4, 7)
g.add_edge(3, 5, 3)
g.add_edge(4, 0, 1)
g.add_edge(5, 4, 8)
g.add_edge(5, 2, 1)

# 输出相连着的顶点
for v in g:
    for w in v.connect_to:
        print('(%d,%d,%d)' % (v.id, w.id, v.connect_to[w]))
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
74
75
76
77
78