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

举报
迷彩 发表于 2023/05/25 17:41:58 2023/05/25
【摘要】 前言什么是有向图在数学中,一个图(Graph)是表示物件与物件之间的关系的方法,是图论的基本研究对象。一个图看起来是由一些小圆点(称为顶点或结点)和连结这些圆点的直线或曲线(称为边)组成的。以下数有向图在数学中的定义:有向图是一个二元组<V,E>,其中1.V是非空集合,称为顶点集。2.E是V×V的子集,称为弧集。而图在数据结构中是中一对多的关系,一般分为有向图和无向图。有向图和无向图最大的区...

前言

什么是有向图

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

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

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

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

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

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

无向图:


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


基本概念

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

  • 有向图:由一组顶点和一组有方向的边组成,每条有方向的边都连接着一组顶点。

  • 顶点的出度:该顶点指出的边的总数。

  • 顶点的入度:指向该顶点的边的总数。

  • 度:顶点的入度+顶点的出度,称为该顶点的度。自环(起点和终点为同一顶点),此时出度算一度,入度也算一度。

  • 有向路径:由一系列顶点组成,其中每个顶点都存在一条有向边,由它指向序列中的下一个顶点

  • 有向环:至少含有一条边,且起点和终点相同的有向路径。虽然有向图中环的数量和大小也是有用的信息,但是在实际应用过程中,我们更多的只关心是否存在有向环。

  • 简单有向环:除了起点和终点外,不含有重复的顶点和边的环。





代码实现

实现流程


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

  2. 对输入的数据进行存储



如何实现有向图


使用关键字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')

执行结果如下:


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。