【数据结构】五分钟带你了解及自定义有向图

作者：迷彩

2022 年 9 月 20 日
广东
本文字数：1525 字
阅读完需：约 5 分钟

前言

什么是有向图

在数学中，一个图(Graph)是表示物件与物件之间的关系的方法，是图论的基本研究对象。一个图看起来是由一些小圆点(称为顶点或结点)和连结这些圆点的直线或曲线(称为边)组成的。

以下数有向图在数学中的定义：

有向图是一个二元组<V,E>，其中

1.V 是非空集合，称为顶点集。

2.E 是 V×V 的子集，称为弧集。

而图在数据结构中是中一对多的关系，一般分为有向图和无向图。有向图和无向图最大的区别在于每条路径都带有方向性。在有向图中，边是单向的，每条边连接的两个顶点都是一个有序对。假如把无向图看成是双行道，可以任意穿梭的话，有向图就是一座只有单行道的城市，而且这些单行道是杂乱无章的。因此要求解一处到另一处的路径问题就会变得复杂起来。其实在开发的过程中，我们接触过的很多场景都是有向图，比如：任务调度的依赖关系和社交网络的任务关系等。相对应的概念有：孤立点、简单图、完备图、基本图、强连通图、弱连通图、单向连通图、强连通分支、有向通路。。。等。由于篇幅原因，这里仅仅是抛转引玉点到为止，感兴趣的童鞋，可以自行了解这些相关的概念。

无向图:

下面就是一个简单的有向图：

基本概念

有向图的基本概念概括如下：

有向图：由一组顶点和一组有方向的边组成，每条有方向的边都连接着一组顶点。
顶点的出度：该顶点指出的边的总数。
顶点的入度：指向该顶点的边的总数。
度：顶点的入度+顶点的出度，称为该顶点的度。自环（起点和终点为同一顶点），此时出度算一度，入度也算一度。
有向路径：由一系列顶点组成，其中每个顶点都存在一条有向边，由它指向序列中的下一个顶点
有向环：至少含有一条边，且起点和终点相同的有向路径。虽然有向图中环的数量和大小也是有用的信息，但是在实际应用过程中，我们更多的只关心是否存在有向环。
简单有向环：除了起点和终点外，不含有重复的顶点和边的环。

代码实现

实现流程

自定义有向图，并用邻接表进行储存。实现所有途径和最短路径的求解，通过 isinstance() 函数判断数据类型.
对输入的数据进行存储

如何实现有向图

使用关键字 class,创建 DirectedGraph 类,并且定义__init__()方法,初始化变量，存储输入的数据。代码如下:

class DirectedGraph(object):     def __init__(self,d):         if isinstance(d,dict):             self.__graph = d         else:             self.__graph = dict() #字典             print('发生错误')

复制代码

在 DirectedGraph 类中定义生成路径的__generatePath()方法.代码如下:

     def __generatePath(self,graph,path,end,results):         curret = path[-1]         if curret == end:             results.append(path)         else:             for n in graph[curret]:                 if n not in path:                     self.__generatePath(graph,path+[n],end,results)

复制代码

在 DirectedGraph 类中定义 searchPath()方法，搜寻并展示所有路径:

     def searchPath(self,start,end):         self.__results = []         self.__generatePath(self.__graph,[start],end,self.__results)         self.__results.sort(key=lambda  x:len(x))                    #按路径长度进行排序         print(self.__results[0][0],'到',self.__results[0][-1],'的路径是:')         for path in self.__results:             print(path)

复制代码

终于到了见证奇迹的时刻，验证代码是否正确：

#输入一个字典d={'A':['B','C','D'],     'B':['E'],     'C':['D','F'],     'D':['B','E','G'],     'E':['D'],     'F':['D','G'],     'G':['E']}
g=DirectedGraph(d)#遍历不同顶点的所有路径g.searchPath('A','D')g.searchPath('A','G')g.searchPath('A','F')