怎样建单位的网站,wordpress怎么使用阿里图标,宜昌企业网站建设,已经做好的网站怎么维护数据结构6——图1#xff0c;概念 文章目录 数据结构6——图1#xff0c;概念基本概念图的分类图的表示方法 基本概念
由 顶点#xff08;Vertex#xff09; 和 边#xff08;Edge#xff09; 组成的集合。顶点表示图中的点#xff0c;而边表示顶点之间的连接。记为 G …数据结构6——图1概念 文章目录 数据结构6——图1概念基本概念图的分类图的表示方法 基本概念
由 顶点Vertex 和 边Edge 组成的集合。顶点表示图中的点而边表示顶点之间的连接。记为 G (V, E 基本组件包括 顶点Vertex图中的节点或点。每个顶点代表一个对象。 边Edge连接两个顶点的线段表示它们之间的关系。边可以是有向的或无向的。 权重Weight有些图的边附带权重表示边的成本、距离或其他量度。 邻接有边连接的两个节点的关系 ij没有先后顺序 ij有先后顺序 关联边和相连的节点的关系 顶点的度关联边的数目 路径Path图中从一个顶点到另一个顶点所经过的顶点序列。 简单路径Simple Path路径中所有的顶点都不重复。 环Cycle路径的起点和终点相同并且至少经过一个其他顶点。若图中存在环称为有环图否则称为无环图。 强连通图Strongly Connected Graph对于有向图如果对于每一对顶点 u 和v都存在从 u 到v 和从 v 到 u 的路径则该图是强连通的。 生成树Spanning Tree一个无环的子图包含图中的所有顶点且是连通的。 生成森林Spanning Forest由多个生成树组成的集合每个生成树包含图中一部分顶点。 子图Subgraph图中的一部分顶点和边的集合这些顶点和边也构成一个图。
图的分类 无向图Undirected Graph图中的边没有方向即如果顶点A与顶点B之间有一条边那么它表示A和B之间是相互连接的。 有向图Directed Graph图中的边有方向称为弧Arc。如果顶点A与顶点B之间有一条有向边它表示从一个顶点指向另一个顶点的单向连接。 加权图Weighted Graph图中的边被赋予了权重Weight这些权重可以表示距离、成本、时间等。 无权图Unweighted Graph图中的边没有权重或者所有边的权重相同。 简单图Simple Graph图中不包含重复的边且不允许顶点与自己相连自环。 多重图Multigraph图中可以有多条边连接相同的一对顶点。 完全图Complete Graph图中的每对顶点之间都恰好有一条边。 稀疏图Sparse Graph边的数量远小于顶点对的数量。边很少 密集图Dense Graph边的数量接近顶点对的最大数量。 连通图Connected Graph在无向图中如果任意两个顶点之间都存在路径则称该图为连通图。在有向图中如果任意两个顶点之间都存在方向路径则称该图为强连通图。 网边带权值的图
图的表示方法
邻接矩阵Adjacency Matrix 定义一个二维数组 matrix[i][j] 表示顶点 i 和顶点 j 之间的边。如果 matrix[i][j] 非零则存在边。 优点快速查询是否存在边适用于稠密图。 缺点空间复杂度为 O(V^2)其中 V 是顶点数量适用于大部分稠密图。 假设有一个无向图包含 4 个顶点A, B, C, D和以下边 A - B A - C B - C C - D A B C D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 1, 0 ]
C [ 1, 1, 0, 1 ]
D [ 0, 0, 1, 0 ]
邻接表Adjacency List不唯一 定义每个顶点维护一个列表列出与其相邻的所有顶点。l链表 优点节省空间适用于稀疏图。 缺点查询边的操作较慢空间复杂度为 O(V E)其中 E 是边的数量。
A: B - C
B: A - C
C: A - B - D
D: C
. 边列表Edge List 边列表使用一个列表存储图中的所有边。每个元素是一个元组表示一条边及其两个端点。 [(A, B), (A, C), (B, C), (C, D)]
