树与图

在讲树之前，我们先看看图。因为树是图的一种特殊情况。

图

图论是组合数学的一个分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

维基百科对图论的介绍似乎有点让人困惑，那么回想一下链表的结构。

节点之间有着某种线性的关系，最终能通过这些关系将所有节点穿成一条链。这就是链表

而图，节点之间的关系不再是单一的指向性的关系，它可能会带有一些信息，譬如边的权重，边的指向等。

在很多数据结构的书里，图的关系都以二维数组的形式存储。一是实现简单，二是运算方便。

但我打算用哈希表来介绍图，较为直观，更容易理解，但本质都一样，表达节点之间的关系即可。来看下面一个有向图的代码

class GraphNode:

    def __init__(self, data=None):
        self.data = data

    def __str__(self):
        return f"[{self.data}]"


class DirectedGraph:
    """有向图"""

    def __init__(self):
        self.__relationship = {}

    def __str__(self):
        nodes = [each for each in self.__relationship.keys()]
        s = 'Graph\t'
        for node in nodes:
            s += (str(node) + "\t")
        else:
            s += "\r\n"
        for x_node in nodes:
            s += (str(x_node) + "\t")
            for y_node in nodes:
                s += (str(self.get_relation(x_node, y_node)) + "\t")
            s += '\r\n'
        return s

    def set_relation(self, x: GraphNode, y: GraphNode, side):
        if self.__relationship.get(x) is None:
            self.__relationship[x] = {}
        self.__relationship[x][y] = side

    def get_relation(self, x: GraphNode, y: GraphNode):
        if self.__relationship.get(x) is not None and self.__relationship[x].get(y) is not None:
            return self.__relationship[x][y]
        return None

当边所携带的数据为权重时，这种图就叫有权图。当图中任意的两个节点的边都有对称性(A->B = B->A)，这种图叫无向图。当图中任意两个节点之间直接相连或者通过其他相互连通的节点能够达到时，则称之为连通图，否则叫非连通图。两个孤立的节点是最简单的非连通图。

图是一种极为常见的数据结构。人与人之间的关系就是一张图，有好事者甚至提出了众所周知的六度分隔理論。互联网当中的网页之间，通过超链接也构成了一张极为复杂的图，搜索引擎排名算法当中著名的PR算法也正是基于这张图当中节点的关系而提出的。

图的实现并不复杂，复杂的是基于图的一些数学研究。但这不是本书的目的，所以在此不做赘述。

树