数据结构——图结构

我就是我 2024-04-06 11:16 76阅读 0赞

**目录**

一. 图的概述

1.1 图的基本概念

1.2 为什么要有图

1.3 几种常见图

1.4 图的基本术语

二. 图的存储结构

2.1 邻接矩阵

2.2 邻接矩阵表述形式

--------------------

> 图是较线性表和树更为复杂的数据结构，因此和线性表、树对节点的定义有所不同。在本章中主要是介绍图结构在计算机中的具体实现。

--------------------

## 一. 图的概述 ##

### 1.1 图的基本概念 ###

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

概念为：

> 由顶点（Vertex）集和边( Edge）集组成， 记为G＝（V，E）,其中V 是有穷非空集合，称为顶点集，v ∈V称为顶点。E是有穷集合，称为边集， e∈E 称为边。

### 1.2 为什么要有图 ###

> 1.  前面我们学了线性表和树
> 2.  线性表局限于一个直接前驱和一个直接后继的关系
> 3.  树也只能有一个直接前驱也就是父节点
> 4.  当我们需要表示多对多的关系时， 这里我们就用到了图

### 1.3 几种常见图 ###

>  *  在图中，如果代表边的顶点对（或序偶）是无序的，则称为**无向图**。无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。如(i，j)表示顶点i与顶点j的一条无向边，显然，(i，j)和(j，i)所代表的是同一条边。

![8a033400208c452c1e8b2c6f995312bc.png][]

>  *  如果表示边的顶点对（或序偶）是有序的，则称为**有向图**。在有向图中代表边的顶点对通常用尖括号括起来，用以表示一条有向边（又称为弧），如<i，j>表示从顶点i到顶点j的一条边。

![34c40b646a797bfdc97e6d0e55769f21.png][]

>  *  图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图

![579a15a57f16a65135f239a6e6f0a14e.png][]

### 1.4 图的基本术语 ###

>  *  在一个无向图中，若存在一条边(i，j)，则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。
>  *  在一个有向图中，若存在一条边<i，j>，则称此边是顶点i的一条出边，同时也是顶点j的一条入边。i和j分别为此边的起始端点（简称为起点）和终止端点（简称终点）。并称顶点j是i的出边邻接点，顶点i是j的入边邻接点。
>  *  在无向图中，顶点所具有的边的数目称为该顶点的度。在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。以顶点i为起点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
>  *  若一个图（无论有向图或无向图）中有n个顶点和e条边，每个顶点的度为di（0≤i≤n-1），则有：
>     
>     ![08750fef333ad1131843d8e7c2b4332f.png][]

--------------------

## 二. 图的存储结构 ##

### 2.1 邻接矩阵 ###

>  **邻接矩阵**是表示顶点之间邻接关系的矩阵。设G=(V，E)是含有n（设n>0）个顶点的图，各顶点的编号为0～n-1，则G的邻接矩阵数组A是n阶方阵。

> （所谓邻接矩阵，就是一个反应边与边之间联系的一个二维数组。这个二维数组我们使用A\[n\]\[n\]来表示，其中 n 是顶点数。）

>  *  如果是**不带权图**，则二维数组中的每一个元素的值根据是否有边，设置为 0 或 1：

![a92b00385140b5891282cfe98b113ae3.png][]

>  *  如果是**带权图**，则：

![e6d100f75f08d8b722341048f348bf7d.png][]

### 2.2 邻接矩阵表述形式 ###

![51231414e82af56d80affb512e7948c5.png][]

> 可以这样理解上图：
> 
> 第一行表示：0 顶点与 1、3、4 顶点有边，与自身和 2 顶点没有边
> 
> 第二行表示：1 顶点与 0、2、3 顶点有边，与自身和 4 顶点没有边
> 
> 第三行表示：2 顶点与 1、3、4 顶点有边，与自身和 0 顶点没有边
> 
> ... ...

![971091debe8a6f9ca79bbd77d8b098e8.png][]

![850fe4deea5eec74f9bcb15a3861c070.png][]

[8a033400208c452c1e8b2c6f995312bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/173eb4fd47d0479aa405025543085931.png
[34c40b646a797bfdc97e6d0e55769f21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/81bbeeae8f84461db8986cad4c0b1b47.png
[579a15a57f16a65135f239a6e6f0a14e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/475fb1f6e98a4d3ebecb3b997c3b3bde.png
[08750fef333ad1131843d8e7c2b4332f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/608caa1b7c0d40e89a2eaec03776e91c.png
[a92b00385140b5891282cfe98b113ae3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/6f17ce1ad66148469d28560d981db42e.png
[e6d100f75f08d8b722341048f348bf7d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2de6434db3554607aecdb9c2e20e23e4.png
[51231414e82af56d80affb512e7948c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c2791e3865994e71bce25289738d70b3.png
[971091debe8a6f9ca79bbd77d8b098e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/73f800c01bfb46589a0912939986264d.png
[850fe4deea5eec74f9bcb15a3861c070.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/71c3b53e510141258cd2b22b2b2b15fb.png