图的定义与操作：从有向图到最短路径

"本课件主要讲解了图的结构建立和销毁，包括图的基本概念、存储结构、遍历方法以及连通性问题。课程涵盖了有向图与无向图的定义，图的子图，有向网和无向网，以及图的度、出度和入度的概念。此外，还涉及了图的遍历算法，如深度优先搜索（DFS），以及图的插入和删除操作。" 在图论中，图是一种数据结构，由顶点集V和弧集R组成，通常表示为Graph=(V,R)。弧<v,w>代表从顶点v到顶点w的连接，v是弧尾，w是弧头。图可以是有向的，即弧具有方向，也可以是无向的，表示两个顶点之间的双向连接。有向图的弧集VR1示例包括<A,B>,<A,E>等，而无向图的边集VR2则包含(A,B), (A,E)等，表示两个顶点之间的连接。 图的子图是原图的一部分，包含原图的部分顶点和这些顶点间的所有边。如果图中的边或弧带有特定的值，我们称之为有向网或无向网，这些值可以表示某种权重或成本。 图的度是指与一个顶点相关的边数。对于无向图，顶点的度等于其出度与入度之和。出度是该顶点作为起点的边数，入度则是作为终点的边数。例如，在图G中，顶点B的出度为1，入度为2，因此总度为3。 图的遍历是图论中的重要概念，包括深度优先搜索（DFS）等算法。DFS是从一个顶点开始，尽可能深地探索图的分支，直到达到所有可达顶点。它在解决连通性问题、寻找路径等方面非常有用。 图的插入和删除操作涉及在图中添加或移除顶点和边。这些操作对于动态调整图的结构至关重要，比如在网络路由、社交网络分析等领域。 在实际应用中，图可以用来表示各种关系，如计算机网络中的节点和连接，交通网络中的城市和道路，或者人际关系网。理解图的建立、操作和遍历对于理解和设计算法，解决复杂问题具有基础性的作用。