当前位置：物联沃-IOTWORD物联网 > 技术教程 > 软考中级-数据库-3.4 数据结构-图
代码收藏家代码收藏家 技术教程

软考中级-数据库-3.4 数据结构-图

图的定义

  • 一个图G(Graph)是由两个集合:V和E所组成的，V是有限的非空顶点(Vertex)集合，E是用顶点表示的边(Edge)集合，图G的顶点集和边集分别记为V(G)和E(G)，而将图G记作G=(V，E)。
  • 可以看出，一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。
  • 在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。

    • 图的相关概念

    有向图(括号是尖括号）

  • 图中每条边都是有方向的。从顶点vi到顶点vj表示为<vi，vj>

    • 而从顶点vj到顶点vi表示为<vj,vi>。有向边也称为弧。起点称为弧尾终点称为弧头。

    无向图(括号是圆括号）

    完全图

    若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图共有n(n-1)/2条边，类似地，有n个顶点的有向完全图中弧的数目为n(n-1)，即任意两个不同顶点之间都存在方向相反的两条弧。

    图的存储结构

    (1)邻接矩阵表示法

    有边就记为1，无边记为0

    无向图都是对称的

    网(带有权值的图)的邻接矩阵的表示:

    (2)邻接链表表示法

  • 邻接链表是为图的每一个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的表(对于有向图是以vi为尾的弧)
  • 邻接链表中的表节点有表节点和表头节点两种类型

    • 无向图的邻接链表表示法

    有向图的邻接链表表示法

    带权值的网的邻接链表表示法

    作者：Lightning_2017

    物联沃分享整理
    物联沃-IOTWORD物联网 » 软考中级-数据库-3.4 数据结构-图

    代码收藏家 普通

    分享到：

    相关推荐

    发表回复