《图的定义和术语》课件

图的定义和术语什么是图？连接关系节点和边图是一种数据结构，用来表示图由节点（顶点）和边组成，对象之间复杂的关系边表示节点之间的连接关系应用广泛图在计算机科学、社会科学、工程学等领域有广泛应用图的定义图是一种数据结构，它用来表示对象之间的关系图由节点（顶点）和边组成，节点代表对象，边代表它们之间的关系图可以用来描述各种现实世界中的关系，例如社交网络、交通网络、信息网络等图的组成元素节点（顶点）边图中的基本单位，表示实体或对象连接节点的线段，表示节点之间的关系节点（顶点）定义示例图中的基本元素，代表图中的实体或对象社交网络中的用户、城市地图中的城市、电路图中的元件等边连接两个节点方向边是图中连接两个节点的线段，边可以是有向的，表示关系的方表示节点之间的关系向，也可以是无向的，表示关系的双向性权重一些边可以拥有权重，表示连接的强度或成本有向图和无向图有向图无向图边是有方向的，表示从一个节点到另边没有方向，表示两个节点之间的双一个节点的单向关系向关系有向边和无向边有向边无向边表示两个节点之间有方向性的关系，例如城市A到城市B的航表示两个节点之间没有方向性的关系，例如城市A和城市B之班间的公路简单图和多重图简单图多重图简单图是指在两个节点之间最多只有一条边，而且没有自环的多重图则允许在两个节点之间存在多条边，或者节点可以与自身图简单图是常见的图结构，它们易于理解和处理它们在各种相连形成自环多重图在描述复杂的连接关系方面更加灵活，例应用中都有使用，例如社会网络分析、交通规划和计算机科学中如交通网络中不同路线的表示，或者网络中不同类型的连接的算法设计稀疏图和稠密图稀疏图稠密图12边数远小于节点数的图边数接近节点数平方值的图权重图权重应用边上的权重代表两个节点之间的权重图广泛用于解决现实世界中关系强度或距离权重可以是数的问题，例如最短路径查找、旅字、字符串或其他类型的数据行商问题和社交网络分析连通图和不连通图连通图不连通图图中任意两个节点之间都存在路径，图中存在至少一对节点之间不存在路则称为连通图径，则称为不连通图子图定义包含关系例子一个图的子图是指该图中的一部分，子图包含在原图中，原图被称为父图例如，一个社交网络图中的所有用户它包含了原图中的一些节点和边，并或超图和他们之间的友谊关系就构成该社交满足这些节点和边仍然构成一个图网络图的一个子图极大连通子图定义特点在一个图中，一个连通子图如极大连通子图是图中的一个最果不能再包含任何图中的其他大连通子图，它不能被包含在顶点，那么它就称为该图的一任何更大的连通子图中个极大连通子图路径和回路路径回路从图中一个顶点到另一个顶点的一条顶点序列，每相邻两个顶点从图中一个顶点出发，经过若干条边，最后回到该顶点，称为回之间都有一条边，称为路径路简单路径和简单回路简单路径简单回路在路径中，除起点和终点外，每个顶点都只出现一次在回路中，除起点和终点外，每个顶点都只出现一次，并且起点和终点是同一个顶点树与森林树森林树是一种特殊的图，它包含**n**个节点和**n-1**条边，并森林是多个互不相连的树组成的集合它是一个无环的图，且没有环路树结构是许多算法的基础，因为它具有简单且但可以有多个连通分量森林可以用树的概念来理解和分高效的特点析，并应用于各种场景，比如文件系统管理等生成树定义性质应用生成树是图中一棵包含图中所有顶点的连生成树的边数等于顶点数减1，即E=V-1生成树在网络优化、最小生成树算法等领通子图，且该子图不包含回路域有广泛应用度和度分布度度分布节点的度是指与该节点相连的边的数量度分布描述了图中不同度数的节点数量分布情况入度和出度入度出度指向一个节点的边的数量从一个节点指向其他节点的边的数量顶点的邻接关系定义表示12如果两个顶点之间存在一条用邻接矩阵或邻接表来表示顶边，则称这两个顶点是相邻点之间的邻接关系的应用3在图的遍历和搜索算法中，邻接关系是至关重要的边的邻接关系共同顶点平行边如果两条边拥有同一个顶点，则称这两条边相互邻接如果两条边连接相同的两个顶点，则称这两条边相互平行图的存储表示邻接矩阵邻接表12使用二维数组存储图的顶点之使用链表存储图的每个顶点连间的关系，数组元素值表示边接的所有顶点是否存在十字链表3结合邻接矩阵和邻接表的优点，使用两个链表分别存储顶点和边信息邻接矩阵表示方法优点缺点用一个二维数组来表示图，数组的第i行简单直观，易于实现空间复杂度高，对于稀疏图浪费空间第j列元素表示顶点i到顶点j之间是否存在边邻接表存储结构使用一个数组来存储所有顶点，每个顶点对应一个链表，链表存储该顶点连接的所有边空间效率对于稀疏图，邻接表比邻接矩阵更节省空间时间效率查找一个顶点的所有邻居需要遍历对应的链表，时间复杂度为On十字链表节点结构邻接节点每个节点包含信息域、指向下一每个节点的邻接节点通过其邻接个结点的指针和指向第一个邻接指针链接在一起，形成一个线性节点的指针链表优势兼顾邻接矩阵和邻接表的优点，空间利用率高，方便查找和更新邻接节点图算法概述图算法是用于解决图论问题的一类算法，它们在计算机科学、运筹学和社会网络分析等领域有着广泛的应用图的遍历算法图的连通性算法12探索图中所有节点的一种方判断图中节点之间的连通关法系图的最短路径算法3寻找图中两点之间的最短路径图的遍历算法深度优先搜索DFS1从一个顶点开始，沿着一条路径一直走到底，再回溯到上一个节点，选择另一条路径继续走下去，直到所有节点都被访问广度优先搜索BFS2从一个顶点开始，先访问其所有直接相邻的节点，再访问这些节点的相邻节点，以此类推，直到所有节点都被访问图的连通性算法深度优先搜索DFS1从一个节点开始，沿着一条路径一直走到底，然后回溯到上一个节点，再沿着另一条路径继续探索广度优先搜索BFS2从一个节点开始，依次访问与该节点相邻的节点，然后依次访问这些节点的相邻节点，直到访问到所有节点连通分量3图中所有相互连通的节点构成一个连通分量，图的连通性是指图中连通分量的数量图的最短路径算法Dijkstra算法适用于非负权重的图，找到起点到所有其他节点的最短路径Bellman-Ford算法可处理负权重边，但不能处理负权重的回路Floyd-Warshall算法求解所有节点对之间的最短路径，适用于稠密图。