Python数据结构与算法-第5章-图

一案例：社交网络中的关系处理案例：社交网络中的关系处理案例描述社交网络是指通过互联网或其他信息通信技术构建的、以人际关系为基础的社交结构。它是一种基于人际关系的社会网络，通过构建和维护人际关系，实现人与人之间的信息交流和资源共享。如微信、QQ、Facebook等。在社交网络中，每个人都有自己的账号和好友列表，通过这些好友可以进行信息的交流和共享，形成一个庞大的社交网络，如右图所示。现在假设我们有一个社交网络，其中每个人都有自己的账号和好友列表。大家可以思考一下如何来解决以下问题：1.两个人是否为好友关系？2.两个人之间的关系紧密程度，即两个人的最短关系路径是多少？上图为“社交网络的简单示意图”案例：社交网络中的关系处理案例实现实现形式（具体见课本案例）定义一个Person类来表示每个人和他们的好友列表，并准备理论Person类构建社交网络。为了解决如何判断两人的好友关系的问题，我们需要定义一个函数来检查两个人是否为好友关系。为了判定两个人之间的关系紧密程度，我们需要定义一个函数来查找两个人之间的最短路径。为了实现这个功能，我们在代码实现中引入广度优先搜索算法（BFS），关于图中的广度优先搜索算法。二图的概念图的概念图的定义上图为“图的示例”图（Graph）是一种非线性数据结构，我们可以将图抽象为由一组有穷非空的顶点（Vertex）集合和一组顶点之间边（Edge）集合组合而成。图的表示方法为：G={V,E}，其中G表示一个图，V表示图G中所有的顶点集合，E表示图G中所有边的集合。图的概念图的分类与常用术语无向图和有向图无向边有向边路径简单路径路径中存在回路或者环连通图和非连通图连通图非连通图无权图和有权图无权图有权图度入度出度邻接邻接连通但是不邻接三图的实现及基本操作图的实现及基本操作图的实现上图为“图的不同逻辑表达形式”图的实现及基本操作图的基本操作01添加边02删除边0304添加顶点删除顶点二叉树的实现及基本操作二叉树的操作基于邻接矩阵的图基本操作（具体见课本案例）（具体见课本案例）基于邻接表的图基本操作四图的遍历图的遍历图遍历的概念图遍历是一种访问和检查图中所有顶点和边的过程。树本质上是一种特殊的图，也就是说树的遍历操作本质上也是图的遍历操作的一种特例。所以图的遍历策略也包含广度优先（Breadth-First）策略和深度优先（Depth-First）策略上图为“图和树的对比”图的遍历广度优先遍历广度优先遍历上图为“广度优先遍历中的顶点访问顺序示例”图的遍历深度优先遍历深度优先遍历上图为“深度优先遍历中的递归调用过程示意”五图的应用图的应用1网络设计和分析2数据库设计3编译器设计4人工智能和机器学习5电路设计6地理信息系统（GIS）7生物信息学8交通规划9项目管理和进度图六小结与习题小结与习题本章小结1图的基本概念234图的分类常用术语图的表示与实现5图的遍历小结与习题习题

？有向图和无向图的区别在于?A.顶点的数量

B.边的方向C.边的权重

D.节点的度

？在图的遍历中，广度优先搜索（BFS）通常使用的数据结构是?A.队列

B.栈C.堆

D.图

？有向图和无向图的区别在于?A.顶点的数量

B.边的方向C.边的权重

D.节点的度小结与习题习题×/√连通图是指图中的每两个节点之间都存在路径。×/√在图的邻接表实现中，每个顶点的邻接顶点都存在图对应的邻接列表中。×/√有向图的邻接矩阵一定是对称的。×/√有向图中，如果存在一条路径从顶点A到顶点B，那么一定存在一条路径从顶点B到顶点A。七实训任务实训任务任务

假设存在一个迷宫，用图的形式表示。迷宫由房间和通道组成，房间表示顶点，每个通道代表一个边，房间和房间之间由通道链接，房间里上可