图论学习笔记

什么是图论？

图论是数学的一个分支，研究图的性质和图之间的关系。图是由顶点和边组成的。顶点代表图中的对象，边则代表它们之间的联系。我们可以将很多问题转化为图论问题，然后使用图论算法解决它们。

在图论中，简单图指的是没有自环和重边的图，也就是说每条边连接不同的两个顶点。而完全图则是指每对不同的顶点之间都有一条边相连的图。

下面是一个简单图的例子：

simple_graph

下面是一个完全图的例子：

complete_graph

图可以用多种方式来表示，包括邻接矩阵和邻接表等。

邻接矩阵是用一个二维数组来表示图的结构的方法。数组中的每个元素为1或0，表示两个顶点之间是否有边相连。

下面是一个7个节点的简单图的邻接矩阵：

Copy Code
   1 2 3 4 5 6 7
1  0 1 1 0 0 0 0
2  1 0 1 0 0 0 0
3  1 1 0 1 0 0 0
4  0 0 1 0 1 0 0
5  0 0 0 1 0 1 0
6  0 0 0 0 1 0 1
7  0 0 0 0 0 1 0

邻接表是用一个数组和链表来表示图的结构的方法。数组中的每个元素代表一个顶点，每一个元素对应的链表中包含了其与其他顶点相连的边。

下面是同样的7个节点的简单图的邻接表：

Copy Code
1 -> 2 -> 3
2 -> 1 -> 3
3 -> 1 -> 2 -> 4
4 -> 3 -> 5
5 -> 4 -> 6
6 -> 5 -> 7
7 -> 6

图论中有很多常见的算法，包括最短路径算法、最小生成树算法和拓扑排序算法等。下面简要介绍一些常见的算法。

最短路径算法用于在有向或无向带权图中找到从一个顶点到另一个顶点的最短路径。Dijkstra算法和Floyd算法是最常见的两种最短路径算法。

最小生成树算法用于在连通带权图中找到一个生成树，使得其所有边上权值之和最小。Kruskal算法和Prim算法都是常见的最小生成树算法。

拓扑排序算法用于有向无环图中，将图的所有顶点排成一个线性序列，使得对于任何一条边 (u,v)，顶点u都排在顶点v的前面。Kahn算法和DFS算法都是常见的拓扑排序算法。

以上是本次的图论学习笔记。图论是一门非常重要的学科，在计算机科学、运筹学、网络科学、物理学、生物学等领域有着广泛的应用。希望本文能够帮助读者更好地了解图论，并在实际问题解决中提供帮助。