美文网首页
数据结构(8)-图论

数据结构(8)-图论

作者: tianyl | 来源:发表于2019-03-03 19:32 被阅读0次

定义

图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关

图的数据存储结构

图是由顶点的有穷非空集合顶点之间边的集合组成,通过表示为G(V,E)
其中,G标示一个图,V是图G中顶点的集合,E是图G中边的集合。

图的属性定义

  1. 图中的数据元素,称之为顶点(Vertex);

  2. 线性表中可以没有数据元素,称为空表,树种可以没有元素,叫做空树。但是图不存在没有数据元素的情况,最少会有一个顶点。

  3. 在图中,任意两个顶点都可能有关系,顶点之间的逻辑关系用边表示。

  4. 无边图:若顶点Vi到Vj之间的边没有方向,则称这条边为无项边(Edge),用序偶对(Vi,Vj)标示。如果有方向,就用<Vi,Vj>表示。

  5. 在无向图中,如果任意两个顶点之间都存在边,则称为该图为无向完全图。例如:


  6. 如果从顶点Vi到Vj的边有方向,则称为这条边为有向边,也称为弧。
    用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。如果任意两个顶点之间的边都是有向边,则称为该图为有向图。在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称为该图为有向完全图。

  7. 权(Weight):有些图的边和弧有相关的数,这个数叫做权(Weight)。这些带权的图通常称为网(Network)。例如:


  8. 连通图:在无向图中,如果从顶点V到V'有路径,则称V和V'是连通的,如果任意两个顶点Vi,Vj都是连通的,则称该图是连通图。

  9. 度:无向图中,顶点的边数叫度,有向图中,顶点的边数,叫出度和入度。

图的存储结构

邻接矩阵

图的邻接矩阵的存储方式是用两个数组来表示图,一个一维数组存储图中的顶点信息,一个二维数组存储图中的边和弧的信息。例如:


横着的是出度,竖着的是入度。

带权的邻接矩阵

例如:


邻接表

邻接矩阵会存在空间浪费的现象,讲到了一种孩子表示法,将结点存入数组,并对结点的孩子进行链式存储,不管有多少孩子,也不会存在空间浪费问题,这个思路同样适用于图的存储。我们把这种数组与链表相结合的存储方法称为邻接表。

无向图的邻接表

无向图连接表就是讲顶点连接的元素用链表的形式表现出来,如图,这是一个无向图连接表


V0连接着V1,V2,V3,所以第一排的表就是1,2,3
V1连接着V0和V2,所以第二排的表就是0和2
V2连接着V0,V1,V3,所以第三排的表就是0,1,3
V3连接着V0和V2,所以第四排的表就是0和2

有向图的邻接表

有向图连接表就是讲顶点出度的的顶点用链表的形式表现出来,如图,这是一个有向图连接表


V0出度的顶点是V3,所以第一行表就是3
V1出度的顶点是V0,V2,所以第二行表就是0,2
V2出度的顶点是V0,V1,,所以第三行表就是0,1
V3没有出度的顶点,所以第四行没有

带权邻接表

如果在连接表加入权,那么就是带权连接表,如下图


数据结构导读目录

相关文章

  • 数据结构(8)-图论

    定义 图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代...

  • 线性表

    数据结构: 数据项 数据对象 数据结构 线性表 队列 堆栈 树 (HashMap(1.8)内置红黑树) 图论 排...

  • 08.图论介绍

    图论介绍 一、图的概念 图是一种特殊的数据结构,由节点和边组成 图论涉及的研究领域如下举例 二、图的分类 1). ...

  • 数据结构_图论

    图的概念 图是一种非线性的数据结构,一个图中有两类东西,一种是结点,一种是边.我们用V这个集合来表示节点(vert...

  • 数据结构-图论

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

  • 数据结构实验之图论六:村村通公路(最小生成树之Prim算法)

    数据结构实验之图论六:村村通公路 Time Limit: 1000MS Memory Limit: 655...

  • 数据结构实验之图论八:欧拉回路

    数据结构实验之图论八:欧拉回路 Time Limit: 1000MS Memory Limit: 65536KB ...

  • 数据结构实验之图论二:图的深度遍历

    数据结构实验之图论二:图的深度遍历 Time Limit: 1000MS Memory Limit: 65536K...

  • 开源计划。

    讲图论的python代码进行开源。写成博客。github开源。作为一个数据结构工具库。

  • 基于邻接表的广度优先搜索

    数据结构实验之图论二:基于邻接表的广度优先搜索遍历 Time Limit: 1000MS Memory Limit...

网友评论

      本文标题:数据结构(8)-图论

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