【数据结构必备基础知识】之图的基本概念详解

快来打我* 2021-06-11 15:13 1198阅读 0赞

# 一、前言 #

从今天开始就给大家分享有关于图的概念和代码啦，不知道大家有没有看够树的相关内容呢？以后还会慢慢给大家再分享的，代码要一遍一遍过，一轮一轮学习。第一轮树就先到这里，等第二轮还会给大家分享的。

图应该是数据结构中处于霸王地位的一部分了，图会涉及到图论的相关知识，咱们现在还涉及不到，等到以后分享数学基础，讲离散数学的时候，会给大家分享有关图论的内容。

为什么称图是霸王地位呢？因为图应该是数据结构中最难的：

1.图状结构是我们研究的结构里面最复杂的结构

我们在讲解数据的逻辑结构时给大家讲到数据结构有如下四个：集合，线性结构，树形结构，图状结构或网状结构。**集合只有同属于一个集合；线性结构存在一对一的关系；树形结构存在一对多的关系；图状结构存在多对多的关系**。

2.图的相关关系非常复杂，相关概念非常多

图有有向图，有无向图；有简单图，有多重图；有连通图，非连通图等等等等。如果把图画出来，我们人去看一个图比较简单，我们会有各种各样去分析这个图的方法，计算机不同，他们没有人这么强大的大脑，很多对于图的分析很死板，需要我们把图分析好了再做处理（如果人工智能发展比较好的话，这个问题可能会解决）。

但是图又很重要，不管是地图，人物关系等，把每个人或者每个地方看作一个点，其他的点都会与之有上千万的联系。所有就都有及其复杂的网络，不管是路径规划，导航提醒还是警察在断案，其实本质上都是图的应用。

所以，在这里把图的相关定义给大家分享一下，方便以后的学习。

# 二、图的定义 #

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)的集合。

**注意：线性表可以是空表，树可以是空树，图不可以是空图，图可以没有边，但是至少要有一个顶点**。

## 1.有向图 ##

若E是有向边（简称弧）的有限集合时，则G为有向图。弧是顶点的有序对，记为<v,w>，其中 v，w 是顶点，v 是弧尾，w 是弧头。称为从顶点v到顶点w的弧。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][] 有向图

如上图所示G可表示为：

G=(V,E)
    V={1,2,3}
    E={<1,2>, <2,1>, <2,3>}

## 2.无向图 ##

若E是无向边（简称边）的有限集合时，则G为无向图。边是顶点的无序对，记为 (v,w) 或(w,v) ，且有 (v,w) =(w,v) 。其中 v，w 是顶点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1][] 无向图

如上图所示，无向图G可表示为：

G=(V, E)
    
    V={1,2,3,4}
    
    E={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}

## 3.简单图 ##

简单图满足以下两条内容：

**1）不存在重复边**

**2）不存在顶点到自身的边**

所以上面的有向图和无向图都是简单图。**与简单图相对的是多重图，即：两个结点直接边数多于一条，又允许顶点通过同一条边与自己关联**。但是我们在数据结构中仅讨论简单图，所以多重图不单独讲解啦。

## 4.完全图 ##

**无向图中任意两点之间都存在边，称为无向完全图**；如无向图中的示例就是完全图。

**有向图中任意两点之间都存在方向向反的两条弧，称为有向完全图**；如示例中的图就不是完全图，但如果没有顶点3和指向顶点3 的边，就是一个完全图。即下图是一个完全图。

![20181103231118250.png][] 有向完全图

## 5.子图 ##

若有两个图G=(V,E),G1=(V1,E2)，若V1是V的子集且E2是E的子集，称G1是G的子图。

如上面的有向完全图是有向图的一个子图。

## 6.连通、连通图、连通分量 ##

在无向图中，两顶点有路径存在，就称为连通的。若图中任意两顶点都连通，同此图为连通图。无向图中的极大连通子图称为连通分量。

以下面两个图为例，下面的图是上面的图的连通分量，并且下面的图是连通图。上面图中I与J也是连通的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 3][] 上图的一个连通分量

## 7.强连通图、强连通分量 ##

在有向图中，两顶点两个方向都有路径，两顶点称为强连通。若任一顶点都是强连通的，称为强连通。有向图中极大强连通子图为有向图的强连通分量。

以下面的图为例：下图就是一个强连通图，并且是下面图的强连通分量。

![20181103232147107.png][] 强连通图

![20181103232300175.png][]

## 8.生成树和生成森林 ##

连通图的生成树是包含图中全部顶点的一个极小连通子图，若图中有n个顶点，则生成树有n-1条边。所以对于生成树而言，若砍去一条边，就会变成非连通图。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

![20181103232621645.png][] 无向图的一个生成树

## 9.顶点的度、入度和出度 ##

顶点的度为以该顶点为一个端点的边的数目。

**对于无向图，顶点的边数为度，度数之和是顶点边数的两倍。**

**对于有向图，入度是以顶点为终点，出度相反。有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和。**

**注意：入度与出度是针对有向图来说的。**

## 10.边的权和网 ##

图中每条边上标有某种含义的数值，该数值称为该边的**权值**。这种图称为带树图，也称作网。

## 11.路径、路径长度和回路 ##

两顶点之间的路径指顶点之间经过的顶点序列，经过路径上边的数目称为路径长度。若有n个顶点，且边数大于n-1，此图一定有环。

## 12.简单路径、简单回路 ##

顶点不重复出现的路径称为简单路径。

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

## 13.距离 ##

若两顶点存在路径，其中最短路径长度为距离。

## 14.有向树 ##

有一个顶点的入度为0，其余顶点的入度均为1的有向图称作有向树。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 4][] 有向树

图的概念很重要，后面会经常用到，希望大家能够牢记于心，最好的记忆方式就是不断练习，不断重复。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/48a099e944be41d2b1d0c9a03f9617be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1]: /images/20210516/5b5f972ed9ed4577b799a65b6de65ce7.png
[20181103231118250.png]: /images/20210516/e9a3fe56a4ce4317a23b06d56ab9099f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 2]: /images/20210516/492edbaabdf741acb7a29c53a232e794.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 3]: /images/20210516/3e849ba973d84d139760a9647b63c528.png
[20181103232147107.png]: /images/20210516/e33b77f520504d2dbaa021e1e3d19560.png
[20181103232300175.png]: /images/20210516/d221e3f45c3d4e53b4aa6b8c3bc50aa9.png
[20181103232621645.png]: /images/20210516/04b4f98ba0ce440a8a231ac6e12faca5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 4]: /images/20210516/3fbeacd1ee664d9bbb8e7c64778a4367.png