图的基本概念

- 日理万妓 2021-07-24 13:46 687阅读 0赞

一 图的引入

1 线性表局限于一个直接前驱和一个直接后继的关系。

2 树也只能有一个直接前驱，也就是父节点。

3 当需要表示多对多的关系时， 就用到了图。

二 图的举例

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70

三 图的常用概念

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1

1 顶点(vertex)

2 边(edge)

3 路径

例如：从 D -> C 的路径有

a D->B->C

b D->A->B->C

4 无向图

顶点之间的连接没有方向，比如A-B,既可以是 A-> B 也可以 B->A。

5 有向图

顶点之间的连接有方向。比如A-B,只能是 A-> B，不能是 B->A。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2

6 带权图

这种边带权值的图也叫网。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 3

四 图的表示方式

图的表示方式有两种：

1 二维数组表示

邻接矩阵

2 链表表示

邻接表

五 邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1….n个点。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 4

六 邻接表

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

2 邻接表的实现只关心存在的边，不关心不存在的边，因此没有空间浪费。

3 邻接表由数组+链表组成。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 5

说明

标号为0的结点的相关联的结点为 1 2 3 4

标号为1的结点的相关联结点为0 4

标号为2的结点相关联的结点为 0 4 5

….

发表评论

表情：
评论列表 （有 0 条评论，687人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构——图的基本概念

    数据结构——图的基本概念 不同于线性结构和树形结构，图结构中的元素之间的关系是多对多的。 1、相关定义： > 图：图G由数据元素（顶点）集合V和边的集合E组

    女爷i女爷i/ 0 赞/ 502 阅读

    相关 图的基本概念

    一 图的引入 1 线性表局限于一个直接前驱和一个直接后继的关系。 2 树也只能有一个直接前驱，也就是父节点。 3 当需要表示多对多的关系时， 就用到了图。 二 图

    - 日理万妓- 日理万妓/ 0 赞/ 688 阅读