离散数学（微课版）第4章1. 引言在离散数学的第4章中，我们将讨论图论的基本概念和应用。
图论是研究图及其在现实生活中的应用的数学分支，它在计算机科学、网络设计、运筹学等领域中具有重要的应用价值。
本章将介绍图的定义、图的表示方法、图的遍历算法等内容。
2. 图的定义图由一组节点和一组节点之间的边构成。
节点通常表示现实世界中的对象，而边则表示对象之间的关系。
图可以用于描述各种问题，如社交网络中的用户关系、城市之间的交通网络等。
2.1 有向图和无向图图可以分为有向图和无向图两种类型。
在有向图中，边具有方向，表示节点之间的单向关系。
而在无向图中，边没有方向，表示节点之间的双向关系。
2.2 顶点和边图由顶点和边组成。
顶点是图的节点，用来表示对象。
边连接两个顶点，表示两个对象之间的关系。
2.3 路径和环路径是指在图中从一个顶点到另一个顶点的连接序列。
环是一条路径，其起点和终点相同。
3. 图的表示方法在计算机中，图可以用不同的数据结构来表示。
常见的表示方法包括：3.1 邻接矩阵邻接矩阵是用二维数组表示图的连接关系。
对于无向图，邻接矩阵是对称的，而对于有向图，则不对称。
A B CA010B101C010上述邻接矩阵表示了一个无向图，其中顶点A与顶点B相连，顶点B与顶点C相连。
3.2 邻接表邻接表是用链表表示图的连接关系。
对于每个顶点，邻接表保存了与其相连的其他顶点的信息。
A ->B -> NULLB -> A ->C -> NULLC -> B -> NULL上述邻接表表示了一个无向图，顶点A与顶点B相连，顶点B与顶点A、C相连，顶点C与顶点B相连。
4. 图的遍历算法图的遍历算法是指按照一定的方式访问图中的所有节点。
常见的图的遍历算法有深度优先搜索和广度优先搜索。
4.1 深度优先搜索深度优先搜索从起点开始，尽可能深地访问尚未访问的节点，直到无法继续深入为止，然后回溯到上一个节点，继续深入其他未访问的节点。
