文档章节

数据结构之图的基本介绍

o
 osc_yim3173g
发布于 07/01 16:56
字数 742
阅读 20
收藏 0

精选30+云产品,助力企业轻松上云!>>>

图的基本介绍

线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点。当我们需要表示多对多的关系时,就需要用到图。

图的基本概念

图(Graph)是一种数据结构,由顶点(vertex)和边(edge)组成,通常表示为G=(V,E):

  • G:表示一个图
  • V:表示图中顶点的集合,顶点集V有穷且非空
  • E: 表示图中边的集合,边集E可以是空的

边:两个顶点之间的连接。

路径:一个顶点到另一个顶点的通路。

比如下面的无向图中,从顶点D到顶点C的路径有:

  1. D->B->C
  2. D->B->A->C

无向图
无向图(Undirected Graph):顶点之间的路径没有方向,比如A-B,即可以是A->B也可以B->A,上面的图就是一个无向图。

有向图(Directed Graph):顶点之间的路径有方向,比如A-B,只能是A->B,不能是B->A,下面的图就是一个有向图。

有向图
出度(Out-degree):一个顶点的出度为x,是指有x条边以该顶点为起点,例如上面的有向图中,顶点A的出度是2。

入度(In-degree):一个顶点的入度为x,是指有x条边以该顶点为终点,例如上面的有向图中,顶点C的入度是2。

出度、入度适用于有向图。

带权图(Weighted Graph):边带权值的图也叫网。

带权图

图的表示方式

图的表示方式有两种:

  • 邻接矩阵(Adjacency Matrix)
  • 邻接表(Adjacency List)

邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵,通常采用一个存放顶点信息的一位数组和一个存放边信息的二维数组实现。

使用邻接矩阵实现的无向图如下:

邻接矩阵实现无向图
说明:

  • 邻接矩阵中的1代表两个顶点之间直连,0代表两个顶点之间不直连。
  • 顶点V1与顶点V0和顶点V2直连,所以邻接矩阵的第二行第一列和第三列为1。

使用邻接矩阵实现的有向图如下:

邻接矩阵实现有向图

邻接矩阵比较适合稠密图,不然会比较浪费内存。

邻接表

邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失。

邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成。

使用邻接表实现的无向图如下:

邻接表实现的无向图
说明:

  • 顶点V1与顶点V0和顶点V2直连,所以顶点V1对应的链表为V0->V3。

使用邻接表实现的有向图如下:

邻接表实现有向图
更多精彩内容关注本人公众号:架构师升级之路
在这里插入图片描述

o
粉丝 0
博文 53
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

switch linux mint 20 apt repository to tsinghua' mirrors

edit file /etc/apt/sources.list.d/cat official-package-repositories.list lwk@qwfys:/etc/apt/sources.list.d$ lltotal 12drwxr-xr-x 2 root root 4096 Jul 5 20:01 ./drwxr-xr-x 7 ......

qwfys
38分钟前
7
0
面试系列之C++的对象布局【建议收藏】

我们都知道C++多态是通过虚函数表来实现的,那具体是什么样的大家清楚吗?开篇依旧提出来几个问题: 普通类对象是什么布局? 带虚函数的类对象是什么布局? 单继承下不含有覆盖函数的类对象是...

伊牙牙嘿哈哈
今天
17
0
OpenCV开发笔记(六十六):红胖子8分钟带你总结形态学操作-膨胀、腐蚀、开运算、闭运算、梯度、顶帽、黑帽(图文并茂+浅显易懂+程序源码)

若该文为原创文章,未经允许不得转载 原博主博客地址:https://blog.csdn.net/qq21497936 原博主博客导航:https://blog.csdn.net/qq21497936/article/details/102478062 本文章博客地址:h...

红模仿_红胖子
今天
12
0
base 64编码用于什么? - What is base 64 encoding used for?

问题: I've heard people talking about "base 64 encoding" here and there. 我听说有人在这里和那里谈论“base 64编码”。 What is it used for? 它是干什么用的? 解决方案: 参考一: ......

技术盛宴
今天
21
0
2020阿里巴巴官方最新Redis开发规范!

本文主要介绍在使用阿里云Redis的开发规范,从下面几个方面进行说明。 键值设计 命令使用 客户端使用 相关工具 通过本文的介绍可以减少使用Redis过程带来的问题。 一、键值设计 1、key名设计...

北柠Java
今天
26
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部