文章目录
- 1、图的表示
- 1.1 邻接矩阵
- 1.2 邻接表
- 1.3 关联矩阵
- 2、带权图
- 2.1 最短路径问题
- 2.2 中国邮递员问题
- 2.3 旅行商问题
- THE END
1、图的表示
1.1 邻接矩阵
\qquad
将图的所有顶点分别构成一个二维矩阵的行列,将顶点之间的边关系表示在构成的矩阵之中,则称这个二维矩阵为图的邻接矩阵。无向图和有向图的邻接矩阵如下图所示。
1.2 邻接表
\qquad
上述使用图的邻接矩阵表示图的时候,当图时一个稀疏图时(图中的边数量较少),在图的存储时会浪费大量的存储空间,所以需要将图进行压缩存储。一种简单的方式就是利用图的邻接表来存储图。邻接表中表的头结点表示图中每一个顶点,邻接表中的每一个节点中有值域和指针域,值域存储图中节点的编号,指针域存储一个指针,指向和当前结点相邻接的其他结点。无向图和有向图的邻接表的形式如下图所示。
1.3 关联矩阵
\qquad
将图的所有顶点和所有的边分别构成一个二维矩阵的行列,将顶点之间和边之间的关系表示在构成的矩阵之中,则称这个二维矩阵为图的关联矩阵。无向图和有向图的关联矩阵如下图所示。
2、带权图
\qquad 给定一个图 G = ( V , E , f , g ) G=(V,E,f,g) G=(V,E,f,g),其中 f : V → R f:V\rightarrow R f:V→R表示每一个顶点到实数的映射, g : E → R g:E\rightarrow R g:E→R表示每一条边到实数的映射,则称 G G G为一个带权图。
2.1 最短路径问题
\qquad
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中
两结点之间的最短路径。算法具体的形式包括:
- 确定起点的最短路径问题。也叫单源最短路问题,即已知起始结点,求最短路径的问题。在边权非负时适合使用Dijkstra算法,若边权为负时则适合使用Bellman-ford算法或者SPFA算法。
- 确定终点的最短路径问题。与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
- 确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。
- 全局最短路径问题也叫多源最短路问题,求图中所有的最短路径。适合使用Floyd-Warshall算法
2.2 中国邮递员问题
\qquad
在一个连通的无向图中找到一最短的封闭路径,且此路径需通过所有边至少一次。现实意义中,中国邮递员问题就是在一个已知的地区,邮差要设法找到一条最短路径,走过此地区所有的街道,且最后要回到出发点。
\qquad
此问题是图遍历问题的一种。无向图的中国邮递员问题是容易解决的,是P问题;而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出。
2.3 旅行商问题
\qquad
是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每对城市之间的距离,求解访问每座城市一次并回到起始城市的最短回路。
\qquad
可以用无向加权图来对TSP建模,则城市是图的顶点,道路是图的边,道路的距离就是该边的长度。它是起点和终点都在一个特定顶点,访问每个顶点恰好一次的最小化问题。通常,该模型是一个完全图(即每对顶点由一条边连接)。如果两个城市之间不存在路径,则增加一条非常长的边就可以完成图,而不影响计算最优回路。