做网站建设费用,免费电子商务网站模板,做远程培训网站用什么系统,网站设计专业建站公司(꒪ꇴ꒪ )#xff0c;Hello我是祐言QAQ我的博客主页#xff1a;C/C语言#xff0c;Linux基础#xff0c;ARM开发板#xff0c;软件配置等领域博主#x1f30d;快上#x1f698;#xff0c;一起学习#xff0c;让我们成为一个强大的攻城狮#xff01;送给自己和读者的…(꒪ꇴ꒪ )Hello我是祐言QAQ我的博客主页C/C语言Linux基础ARM开发板软件配置等领域博主快上一起学习让我们成为一个强大的攻城狮送给自己和读者的一句鸡汤集中起来的意志可以击穿顽石!作者水平很有限如果发现错误可在评论区指正感谢 一、什么是图 图是一种由节点顶点和连接这些节点的边构成的非线性数据结构。每个节点可以表示一个实体而边则表示节点之间的关系。图的设计可以用于模拟现实世界中的各种复杂关系和连接从社交网络到通信网络都可以通过图来更好地理解和分析。
二、图的分类 图可以根据多个维度进行分类
有向图Directed Graph和无向图Undirected Graph 有向图中的边具有方向表示从一个节点指向另一个节点的关系而无向图中的边没有方向表示两个节点之间的对等关系。 有权图Weighted Graph和无权图Unweighted Graph 在有权图中每条边都有一个权重可以表示节点之间的某种度量如距离、成本等而在无权图中边没有权重只表示连接关系。 简单图和多重图Multigraph 简单图中不存在自环和重复的边而多重图允许自环和可能具有相同的边。
三、图的边 图的边是连接节点的实体它可以包含以下信息
权重Weight 如果是有权图每条边都有一个权重代表节点之间的某种度量。方向 在有向图中边从一个节点指向另一个节点有方向性在无向图中边没有方向表示双向关系。标签Label 可以为边添加标签表示连接的类型或特性。 有些图的边或弧具有与它相关的数字这种与图的边或弧相关的数叫做权表示从一个顶点到另一个顶点的距离或花费或时间。我们称这种带权的图为网。如下图所示即为网。 四、图的表达方式 图可以使用不同的数据结构来表示
邻接矩阵Adjacency Matrix 使用二维数组表示图的顶点之间的连接关系。矩阵的行和列分别代表顶点矩阵元素表示边的存在与否或权重。 图中 1 表示相连接0 表示不相连
邻接表Adjacency List 使用链表或数组表示图的顶点以及与其相邻的顶点。每个顶点对应一个列表包含与之相连的顶点。 五、图的遍历 图遍历是访问图中所有节点的方法有两种主要方法
深度优先搜索DFS 从起始节点开始沿着一条路径尽可能深入直到无法继续为止然后回溯到之前的节点继续探索其他路径。
1.遍历思路
访问顶点v从v的未被访问的邻接点中选取一个顶点w从w出发进行深度优先遍历重复上述两步直至图中所有和v有路径相通的顶点都被访问到。
2.列举 按深度优先遍历就是A B C D E F G H(此时这条线路已经走到尽头可是还有一个I顶点没有遍历所以回到G发现G的邻接点都遍历过了再回到F发现F的邻接点也都遍历过了直到D顶点发现I这个顶点没有遍历所以把I再遍历继续回溯最终回到起点A。 广度优先搜索BFS 从起始节点开始先访问所有与其直接相邻的节点然后逐层向外扩展确保先访问离起始节点近的节点。
1.遍历思路
从图中某个顶点V0出发并访问此顶点从V0出发访问V0的各个未曾访问的邻接点W1W2…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点重复步骤2直到全部顶点都被访问为止。 2.列举 六、图的算法 图的算法是一个重要的主题包括最短路径、连通性、最大流、最小生成树等问题。比如Dijkstra算法可以用于寻找图中的最短路径Kruskal算法和Prim算法可以用于求解最小生成树问题。这些算法的选择和应用取决于图的特性和问题的需求。
七、适用说明 图的应用范围广泛包括但不限于
社交网络分析 用于分析人际关系、社区发现、信息传播等。路线规划 帮助找到最短路径、最优路线应用于导航和交通规划。计算机网络 描述计算机之间的连接、拓扑结构用于网络设计和分析。编译器 用于构建控制流图、数据依赖图进行代码优化和分析。 图还可以用于生物信息学比如在蛋白质相互作用网中寻找功能模块、物联网比如在设备间建立最优的通信路径等领域。 总之图是一个强大的数据结构能够捕捉和表示各种实体之间的关系为解决各种复杂问题提供了有效的工具。不同类型的图和图遍历算法可以根据问题的性质和需求来选择使用。 更多C语言、Linux系统、ARM板实战和数据结构相关文章关注专栏 手撕C语言 玩转linux 脚踢数据结构 6818ARM开发板实战
写在最后
今天的分享就到这啦~觉得博主写的还不错的烦劳 一键三连喔~感谢关注
