图论基础介绍

路径规划系列文章目录

1. 路径规划算法综述

图论基础介绍

图论在现实生活中有着广泛应用，很多问题都可以转化成为图论问题，如交通网络、计算机网络、神经网络、电路供应网络等等。当然我们重点讨论的路径规划也可以转化为图论问题。在图论算法的这部分，我们将讨论图在计算机中的两种存储方式，接着讨论图的遍历方式，以及常用的图论算法是如何解决路径规划问题的。

提示：以下是本篇文章正文内容。

一、图的基本概念

1.1 图的定义

• 如下图所示是一张图
  

• 在上图中包含了四个顶点，编号分别为v1,v2，v3,v4。有四条边，四条边的权重分别是8,2，5,4。因此一张图可以看成是由顶点集合与边集合两部分组成，顶点可以看成是各种对象，边的权重可以看成是距离或者代价等。

1.2 图的分类

• 图主要有无向图、有向图和带权图三种，下面分别介绍。

1.2.1 无向图

• 当图中所有边都是无向边的时候，这时组成的图就是无向图。如下图所示
  

• 所谓无向边即从沿着一条边从一个顶点v1可以到达另一个顶点v2，那么反过来，从另一个顶点v2沿着这条边一样能够到达v1。即为无向边。

1.2.2 有向图

• 有向图如下所示
  
• 从上图可见，有向图中所有边都是带箭头的，这意味着从一条边只能从一个顶点到达另一个顶点，反过来则是不能的。

1.2.3 带权图

• 带权图即每条边都有一定的权值，权值可以表示两顶点之间的距离，此外带权图每一条边既可以是有向边也可以是无向边。
  

二、图的相关术语

我们接下来介绍几个在图中经常使用的一些相关术语。

2.1 邻接(adjacent)

• 两个顶点之间有边连接，就代表二者邻接。
• 在无向图中，两个顶点之间有一条边，则二者互为邻接点
• 在有向图中，两个顶点v1,v2有条边，则称v1邻接v2，或者v2邻接v1。

2.2 顶点的度

• 所谓度其实就是与该顶点直接相连的边的数量。
• 对于有向图可以分为出度和入度，对于无向图没有这种划分。
• 出度即从顶点射出的边的数量
• 入度即射入顶点的边的数量
• 如下图所示，顶点v1出度为2，入度为3
  

2.3 环

• 所谓环，顾名思义即从一个顶点出发，走一圈能够走回来，就是环，如下图所示，v1,v2,v3,v4,v1就构成一个环
  

2.4 强连通图

• 当有向图中任意两点之间都有路可达，或者说通过一定的路径都能够走到，那么这个图就是强连通图。如下图所示。
• 

2.5 连通图

• 无向图中，任意两点之间可达。如下图所示
  

2.6 完全图

• 任意两个顶点之间都有互达的边。如下图所示
  
  
• 无向完全图中的边数量为n(n-1)/2条，n为顶点数量
• 有向完全图中的边数量为n(n-1)条。

2.7 连通图生成树

• 所谓连通图生成树即，该树中包含所有顶点，并且只有n-1条边（如果顶点总共是n个，那么边数一旦多于n-1，那么一定包含有环），但能够保证是连通图(或强连通图)。
• 下图是连通图(无向图)及其生成树

• 下图是强连通图(有向图)及其生成树
  

2.8 顶点编号

• 在计算机中进行表示的时候，通常会使用1,2,3,4来指代顶点编号v1,v2,v3,v4

总结

• 本文介绍了图的基本概念、图的分类以及相关术语，为后面在计算机中的表示以及算法的编写做铺垫。