图的基本概念

- 日理万妓 2021-07-24 13:46 498阅读 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

....

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/d20c0114e50f461486e406645a70218b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/83e10e27f91c411ca54fe578101edfb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2]: /images/20210724/3e11c03222f54376b37fc3892dc29790.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 3]: /images/20210724/694549a8773a41089c72d898a9c26e2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 4]: /images/20210724/92d97b3265464efc82573ad868888016.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 5]: /images/20210724/71c398257c3d478b835b914a851401b8.png