Python中图的实现

writer：lIcht                      email：lIcht.gzl@gmail.com                 Date:  2019.9.18

        图是一种数学结构，数学里有分枝“图论”，研究这种拓扑结构。数据结构把图看成一类复杂数据结构，用于表示各种具有复杂关系的数据集合。图在实际应用中很广泛，有很多的实现方式，和许多的典型算法。在在这里使用Python语言进行部分功能的实现：

xxxxxxxxxx
# 图的操作
​
​
class Graph(object):
    """图结构类"""
    def __init__(self):
        self.graph = {}
        self.queue = []
        self.flag = 0
        self.long = 0
​
    def add_v(self, item):
        # 图中添加顶点,索引0记录每一个key的父顶点
        self.graph[item] = []
​
    def add_e(self, a, b):
        # 添加一条a指向b的路径
        self.graph[a].append(b)
​
    def parents(self, item):
        # 遍历一个顶点的所有父顶点
        parent = []
        for i in self.graph:
            for j in self.graph[i]:
                if j == item:
                    parent.append(i)
        return parent
​
    def child(self, item):
        # 遍历所有子顶点
        return self.graph[item]
​
    def is_exist(self, a, b, queue=[]):
        # 判断a指向b是否存在通路，广度遍历
        if len(queue) == self.long:
            if queue == []:
                queue.append(a)
            else:
                self.long = 0
                self.flag = 0
                return False
        for n in queue:
            if n == b:
                # self.long = 0
                self.flag = 0
                return True
        self.long = len(queue)
        for i in self.graph[a]:
            if i not in queue:
                queue.append(i)
        if len(queue) > self.long:
            self.flag += 1  # queue元素扩充后，flag才+1
        print(queue)
        return self.is_exist(queue[self.flag], b, queue)
​
​
if __name__ == "__main__":
    g = Graph()
    g.add_v("A")
    g.add_v("B")
    g.add_v("C")
    g.add_v("D")
    g.add_e("A", "D")
    g.add_e("D", "C")
    g.add_e("B", "D")
    g.add_e("C", "A")
    print(g.parents("A"))
    print(g.parents("D"))
    print(g.parents("C"))
    print(g.child("A"))
    print(g.child("B"))
    print(g.child("D"))
    print(g.flag)
    print(g.long)
    print(g.is_exist("A", "B"))
    print(g.flag)
    print(g.long)
​