算法之图论

这篇具有很好参考价值的文章主要介绍了算法之图论。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

定义

图通常以一个二元组 G=<V, E>表示,V表示节点集,E表示边集。节点集中元素的个数,称为图的阶。

若图G中的每条边都是没有方向的,称为无向图;每条边是由两个节点组成的无序对,例如节点V1和节点V2之间的边,记为算法之图论,算法,算法,图论算法之图论,算法,算法,图论
若图G中的每条边都是有方向的,称为有向图;有向边也称为弧,每条弧是有两个节点组成的有序对,例如节点V1和节点V2之间的弧,记为<V1, V2>
算法之图论,算法,算法,图论

定理

握手定理:所有节点的度数之和等于边数的两倍。

存储

邻接表是图的一种链式存储结构,包括两部分:节点和邻接点。
邻接点结构

struct LinkNode {
    int nodeIndex; // 节点下标
    // int weight; // 路径上有不同权重,可以使用
    LinkNode *next; // 下一个邻接点
};

节点

struct Node {
    char ch; // 节点名称,假定为单字符
    LinkNode *first; // 第一个邻接点
}

节点数组

Node nodes[26]; // 26个字符

示例:
有如下图:
算法之图论,算法,算法,图论
邻接表结构:
算法之图论,算法,算法,图论

图的搜索

广度优先搜索

广度优先搜索(Breadth First Search, BFS),又称为宽度优先搜索。即从某个节点(源点)出发,优先访问该节点的所有未被访问的邻接点,再依次从这些被访问的点出发,一层一层的访问,直到访问节点均已访问。如存储的示例图,访问顺序如下
算法之图论,算法,算法,图论

深度优先搜索

深度优先搜索(Depth First Search, DFS)。即优先沿着一条路径搜索,直到当前节点无未被访问的邻接点,则退回到上一个节点,继续访问其未被访问的邻接点,直到所有点均已访问。如存储的示例图,访问顺序如下
算法之图论,算法,算法,图论

图的连通性

  1. 无向图的连通分量
    在无向图中,如果从节点Vi到节点Vj有路径,则称节点Vi和节点Vj是连通的。如果途中任意两个节点都是连通的,则称图G为连通图。连通分量,即其子连通图。如下图,为连通图
    算法之图论,算法,算法,图论
  2. 有向图的强连通分量
    在有向图中,如果图中的任意两个节点从Vi到Vj都有路径,且从Vj到Vi也有路径,则称图G为强连通图。强连通分量,即其子强连通图。如下图,为强连通图
    算法之图论,算法,算法,图论算法之图论,算法,算法,图论
  3. 桥和割点
    如果去掉无向图G中的一条边Ei后,图G分裂为两个不相连的子图,那么Ei为图G的桥,或称割边;如果去掉无向图G中的一个节点Vi,及与Vi关联的所有边后,图G分裂为两个或两个以上不相连的子图,那么Vi称为图G的割点。
    存储的示例图,去掉d到e的边,则原图分裂为两个不连通的子图,因此,d到e的边,为图的
    算法之图论,算法,算法,图论
    存储的示例图,去掉节点d,及与d相连的边,则原图分裂为两个不连通的子图,因此,节点d为图的割点
    算法之图论,算法,算法,图论
    桥与割点的关系:有割点不一定有桥,有乔一定有割点;桥一定是割点依附的边
    桥与割点的算法:Tarjan算法
  4. 无向图的双连通分量(DCC)
    如果无向图中不存在桥,则称为边双连通图。图中任意两点之间都存在两条或两条以上的路径,且路径上的边互不重复。极大边双连通图,称为边双连通分量(e-DCC)。
    如果无向图中不存在割点,则称为点双连通图。图中,如果节点数大于2,则在任意两点间都存在两条或两条以上路径,且路径上的点互不重复。极大点双连通子图称为点双连通分量(v-DCC)。
  5. 双连通分量的缩点
    把每一个边双连通分量都看作一个点,把桥看作连接连个缩点的无向边,可得到一棵树,这种方法被称为边连通分量缩点。如图,虚线内看作一个节点
    算法之图论,算法,算法,图论
    把每一个点双连通分量都看作一个点,把割点看作一个点,每个割点都向包含它的点双连通分量连接一条边,得到一棵树,这种方法称为点双连通分量缩点。如图,虚线内看作一个节点
    算法之图论,算法,算法,图论

参考《算法训练营》文章来源地址https://www.toymoban.com/news/detail-601936.html

到了这里,关于算法之图论的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法之图结构

    图 (Graph)是一种复杂的非线性结构,在图结构中,每个元素都可以有零个或多个前驱,也可以有零个或多个后继,也就是说,元素之间的关系是任意的。 常用术语 : 术语 含义 顶点 图中的某个结点 边 顶点之间连线 相邻顶点 由同一条边连接在一起的顶点 度 一个顶点的相

    2024年02月09日
    浏览(12)
  • 【C++算法竞赛 · 图论】图论基础

    前言 图论基础 图的相关概念 图的定义 图的分类 按数量分类: 按边的类型分类: 边权 简单图 度 路径 连通 无向图 有向图 图的存储 方法概述 代码 复杂度 图论(Graph theory) ,是 OI 中的一样很大的一个模块,围绕它有很多高难度的算法以及高级的概念。 这篇文章将介绍关

    2024年04月12日
    浏览(18)
  • 图论与算法(1)图论概念

    在计算机科学中,图论与算法是两个重要且紧密相关的领域。图论研究图的性质和特征,而算法设计和分析解决问题的方法和步骤。图论提供了一种形式化的方法来描述和分析各种关系和连接,而算法则为解决图相关的问题提供了有效的解决方案。 图论是研究图的结构和性质

    2024年02月07日
    浏览(17)
  • 算法提高-图论-floyd算法及其扩展应用

    离散化 (只要用到200个点,但是题目给的点编号是1-1000)+ 倍增(快速幂)+ flyod变式(将递推公式改变了) 能用快速幂的原因是递推公式里面的两端路径两两之间相互独立,用结合律就可以用快速幂。矩阵乘法能用快速幂的原因也是矩阵乘法中两两矩阵之间具有结合律 帮助

    2024年02月09日
    浏览(17)
  • 【数据结构与算法】图论及其相关算法

    线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。 图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图:

    2024年02月09日
    浏览(20)
  • 【图论】kruskal算法

     Kruskal(克鲁斯卡尔)算法是一种用于解决最小生成树问题的贪心算法。 最小生成树是指在一个连通无向图中,选择一棵包含所有顶点且边权重之和最小的树。 下面是Kruskal算法的基本步骤: 将图中的所有边按照权重从小到大进行 排序 。 创建一个空的最小生成树 集合(并

    2024年02月15日
    浏览(15)
  • 算法题目题单+题解——图论

    本文为自己做的一部分图论题目,作为题单列出,持续更新。 题单由题目链接和题解两部分组成,题解部分提供简洁题意,代码仓库:Kaiser-Yang/OJProblems。 对于同一个一级标题下的题目,题目难度尽可能做到递增。 题目链接:Luogu P3547 [POI2013] CEN-Price List 题解: 题目链接:

    2024年02月19日
    浏览(12)
  • 算法提高-图论- 最小生成树

    和上题一摸一样,但是题意要求的out看起来需要特别处理,其实只要想清楚kruskal的性质就好 题意就是求最小生成树,因为边权都是正数,那么我们多选一条边必然会导致我们的代价增大 但如果题目说了边权为正或者负数,那么就不是最小生成树了,极端一点所有边都是负的

    2024年02月16日
    浏览(17)
  • 图论中的算法

    图论的概念 :图论是数学的一个分支,它是以图为研究对象,图论中的图是由若干个给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些实体之间的某种特定的关系,用点代表实体,用连接两点之间的线表示两个实体之间具有某种关系。 图的分类: 无权无向

    2024年02月08日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包