美文网首页
数据结构5、图 Graph

数据结构5、图 Graph

作者: 四月不见 | 来源:发表于2021-12-24 19:12 被阅读0次

一、定义

由顶点的有穷非空集合(在图结构中不允许没有顶点)和顶点之间边的集合组成,通常表示为:G(V,E)。其中,G是一个图,V是图G中顶点的集合,E是图G中边的集合。图中任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

顶点 (Vertex) :图中数据元素,也可以叫做节点

树实际上是图的一种,但并不是所有的图都是树(树是没有环路的连通图)。

简单来说,图是顶点与顶点之间边的集合。

  • 图可以分为向图或无向图。有向图的边可以类比为单行道,而无向图的边可以类比为双向车道。
  • 图可以包括多个相互隔离的子图。如果任意一对节点都存在一条路径,那么该图被称为连通图。
  • 图也可以包括(或不包括)环路。无环路图(acyclic graph)是指没有环路的图。

有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图称为"网"(Network)

二、存储结构

这里介绍两种比较常见的图的存储结构。

1、邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图G有n个顶点,则邻接矩阵是一个n×n的方阵,定义为:

无向图的邻接矩阵:

对于矩阵的主对角线的值,即arc[0][0]、arc1、arc2、arc3,全为0是因为不存在顶点到自身的边,比如V0到V0。arc0=1是因为V0到V1的边存在,而arc1=0是因为V1到V3的边不存在。并且由于是无向图,V1到V3的边不存在,意味着V3到V1的边也不存在。所以无向图的边数组是一个对称矩阵。

有向图的邻接矩阵:

因为是有向图,所以此矩阵并不对称,比如由v1到v0有弧,得到arc1[0]=1,而v0到v1没有弧,因此arc0=0。 有向图讲究入度与出度,顶点v1的入度为1,正好是第v1列各数之和。顶点v1的出度为2,即第v1行的各数之和。 与无向图同样的办法,判断顶点vi到vj是否存在弧,只需要查找矩阵中arc[i][j]是否为1即可。要求vi的所有邻接点就是将矩阵第i行元素扫描一遍,查找arc[i][j]为1的顶点。

网的邻接矩阵:

设图G是网图,有n个顶点,则邻接矩阵是一个n×n的方阵,定义为:

这里Wij表示(Vi,Vj)或上的权值。∞表示一个计算机允许的、大于所有边上权值的值,也就是一个不可能的极限值。不为0的原因在于权值Wij大多数情况下是正值,但个别时候可能就是0,甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。下就是一个有向网图,右图就是它的邻接矩阵:

2、邻接表

邻接矩阵对于边数相对顶点较少的图,存在对存储空间的极大浪费的现象。因此这种存储方式对于稀疏图来说不是很合适。借鉴于线性表的解决方案,可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。即使用数组与链表相结合的存储方式,就诞生了邻接表(Ad-jacency List)。

三、图的遍历

从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历。

如深度优先遍历(深度优先搜索),广度优先遍历(广度优先搜索),详细了解这两种算法可查看我前面的章节。

参考

1、《数据结构-图的相关概念》https://www.zybuluo.com/defias/note/291041
2、《算法图解》https://www.manning.com/books/grokking-algorithms

相关文章

  • 数据结构5、图 Graph

    一、定义 图由顶点的有穷非空集合(在图结构中不允许没有顶点)和顶点之间边的集合组成,通常表示为:G(V,E)。其中...

  • 图的 python实现

    介绍 图(Graph)是一种网状数据结构,其形式化定义如下:Graph=(V, R)V={X | X属于DataO...

  • 【恋上数据结构与算法二】(三)图(Graph)

    数据结构回顾 图(Graph) ◼图由顶点(vertex)和边(edge)组成,通常表示为 G = (V, E)...

  • 数据结构 图Graph

    一些概念: 连通图:在无向图中,若任意两个顶点v与u都有路径相通,则称该无向图为连通图。 强连通图:在有向图中,若...

  • 数据结构:图(Graph)

    图看起来就像下图这样: 在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示...

  • 12-图(Graph)

    图(Graph) 在讨论图这种数据结构之前,先来回顾一下前面介绍的几种数据结构 线性结构 数组 链表 栈 队列 哈...

  • tensorflow 学习

    基本概念 使用图(graph)来表示计算任务 在会话(session)中执行图 使用(tensor)来表示数据结构...

  • 2020-08-10【数据结构&c++】图

    (摘自书:数据结构c++实现) 图的基本概念 图的术语 1.完全图(complete graph)(略) 2.权(...

  • 图-基本知识

    Graph-基本知识 Graph: 图。 图是由一些点V和一些边E组成的数据结构E。对于任一一条边(v, w),v...

  • 012-数据结构与算法-图

    什么是图 ? 前面总结了“树”这种数据结构,而这篇博客总结的是更为复杂的一种数据结构:图(graph),它表明了物...

网友评论

      本文标题:数据结构5、图 Graph

      本文链接:https://www.haomeiwen.com/subject/lzakoltx.html