算法－图的强连通分量，图的最小生成树

1.图的强连通分量
(1). 定义
图的强连通分量是图论中的一个重要概念，主要在有向图中进行讨论。具体来说，如果在一个有向图G中，任意两个顶点vi和vj（其中vi大于vj）之间都存在一条从vi到vj的有向路径，同时也存在一条从vj到vi的有向路径，那么这两个顶点就被称为强连通。如果有向图G的每两个顶点都强连通，那么G就被称为一个强连通图。

进一步地，有向图G的极大强连通子图被称为强连通分量。这里，“极大”意味着如果添加任何额外的顶点，子图将不再保持强连通的属性。因此，强连通分量实际上是原图中满足强连通条件的最大的子图。

强连通分量在实际应用中有着重要的价值。例如，在复杂网络分析中，强连通分量可以帮助我们识别出网络中紧密连接、相互依赖的节点群体，这对于理解网络的结构和功能至关重要。此外，强连通分量还可以用于简化图的复杂度，将原图分解为多个更小的强连通分量，从而方便后续的分析和处理。

在算法实现上，有多种方法可以用来寻找有向图中的强连通分量，如Kosaraju算法、Tarjan算法和Gabow算法等。这些算法通常基于深度优先搜索（DFS）的思想，通过遍历图中的节点和边来识别强连通分量。

(2). Kosaraju算法求解图的强连通分量
Kosaraju算法是一种求解有向图强连通分量（Strongly Connected Components, SCC）的算法。这个算法的基本思想是分两步进行深度优先搜索（DFS）。首先，对原图进行DFS，并记录每个节点的完成时间（即退出DFS的时间）。然后，根据完成时间的逆序（从大到小），对节点进行第二次DFS，每次DFS找到的就是一个强连通分量。
(3). 实例
在这里插入图片描述
上述是一个图结构．利用Kosaraju算法可以求解其中每个强连通分量．

// 强连通分量
class NodeInfo{
public:
    char m_nName;
    bool m_bVisit = false;
    int32_t m_nTag = -1;
    int32_t m_nFirstTick;
    int32_t m_nLastTick;
};
template<class T>
class Node{
public:
    T m_nEle;
};
template<class EdgeInfo>
class Edge{
public:
    bool m_bValid = false;
};
Node<NodeInfo> stNodes[9];
Edge<int> stEdges[9][9];
Edge<int> stEdges2[9][9];
int nVisitTick = 0;
void Visit(int nCurIndex, int32_t nTag = -1);
 // 对节点按最后访问时间逆序排列
struct VisitInfo{
    int32_t nVisitTick;
    int32_t nIndex;
};
void Sort(VisitInfo* lpBegin, VisitInfo *lpEnd);
int main(){
    stNodes[0].m_nEle.m_nName = 'A';
    stNodes[1].m_nEle.m_nName = 'B';
    stNodes[2].m_nEle.m_nName = 'C';
    stNodes[3].m_nEle.m_nName = 'D';
    stNodes[4].m_nEle.m_nName = 'E';
    stNodes[5].m_nEle.m_nName = 'F';
    stNodes[6].m_nEle.m_nName = 'G';
    stNodes[7].m_nEle.m_nName = 'H';
    stNodes[8].m_nEle.m_nName = 'I';
    
    stEdges[0][1].m_bValid = true;
    stEdges[1][0].m_bValid = true;
    stEdges[1][2].m_bValid = true;
    stEdges[2][1].m_bValid = true;
    stEdges[4][5].m_bValid = true;
    stEdges[5][4].m_bValid = true;
    stEdges[4][3].m_bValid = true;
    stEdges[3][4].m_bValid = true;
    stEdges[4][6].m_bValid = true;
    stEdges[6][4].m_bValid = true;
    stEdges[6][8].m_bValid = true;
    stEdges[8][6].m_bValid = true;

    stEdges2[1][0].m_bValid = true;
    stEdges2[0][1].m_bValid = true;
    stEdges2[2][1].m_bValid = true;
    stEdges2[1][2].m_bValid = true;
    stEdges2[5][4].m_bValid = true;
    stEdges2[4][5].m_bValid = true;
    stEdges2[3][4].m_bValid = true;
    stEdges2[4][3].m_bValid = true;
    stEdges2[6][4].m_bValid = true;
    stEdges2[4][6].m_bValid = true;
    stEdges2[8][6].m_bValid = true;
    stEdges2[6][8].m_bValid = true;
    for(int i = 0; i < 9; i++){
        if(stNodes[i].m_nEle.m_bVisit == false){
            Visit(i);
        }
    }

    VisitInfo stArr[9];
    for(int32_t i = 0; i < 9; i++){
        stArr[i].nIndex = i;
        stArr[i].nVisitTick = stNodes[i].m_nEle.m_nLastTick;
    }
    // 按访问时间逆序排列数组元素
    Sort(stArr, stArr + 9);
    // 构造一个转置图，已经提前构建好．复用了原图的节点结构．深度优先前复位节点状态．
    for(int32_t i = 0; i < 9; i++){
        for(int32_t j = 0; j < 9; j++){
            stEdges[i][j] = stEdges2[i][j];
        }
    }
    for(int32_t i = 0; i < 9; i++){
        stNodes[i].m_nEle.m_bVisit = false;
        stNodes[i].m_nEle.m_nFirstTick = -1;
        stNodes[i].m_nEle.m_nLastTick = -1;
        stNodes[i].m_nEle.m_nTag = -1;
    }
    // 对转置图按排序后节点顺序再次执行深度搜索
    int32_t nTag = 0;
    for(int32_t i = 0; i < 9; i++){
        int32_t nNodeIndex = stArr[i].nIndex;
        if(stNodes[nNodeIndex].m_nEle.m_bVisit == false){
            Visit(nNodeIndex, nTag);
            nTag++;
        }
    }
    // 此时一次性求出了图的所有强连通分量．tag相同的节点位于同一个强连通分量．
    printf("strong connect num:%d\n", nTag);
    for(int32_t i = 0; i < nTag; i++){
        printf("%d:\n", i);
        for(int32_t k = 0; k < 9;  k++){
            if(stNodes[k].m_nEle.m_nTag == i){
                printf("%c ", stNodes[k].m_nEle.m_nName);
            }
        }
        printf("\n");
    }
    return 0;
}

void Sort(VisitInfo* lpBegin, VisitInfo *lpEnd){
    int32_t nNum = lpEnd - lpBegin;
    if(nNum <= 1){
        return;
    }

    // 归并排序
    int32_t nMid = nNum / 2;
    Sort(lpBegin, lpBegin+nMid);
    Sort(lpBegin+nMid,lpEnd);
   
    // 归并
    VisitInfo* lpArrTmp = (VisitInfo*)malloc(sizeof(VisitInfo) * nNum);
    int32_t nArrIndex = 0;
    int32_t nLeftIndex = 0;
    int32_t nRightIndex = 0;
    while(nLeftIndex < nMid && nRightIndex < (nNum - nMid)){
        if(lpBegin[nLeftIndex].nVisitTick >= lpBegin[nRightIndex+nMid].nVisitTick){
            lpArrTmp[nArrIndex] = lpBegin[nLeftIndex];
            nArrIndex++;
            nLeftIndex++;
        }
        else{
            lpArrTmp[nArrIndex] = lpBegin[nRightIndex+nMid];
            nArrIndex++;
            nRightIndex++;
        }
    }
    if(nLeftIndex < nMid){
        for(int32_t i = nLeftIndex; i < nMid; i++){
            lpArrTmp[nArrIndex] = lpBegin[i];
            nArrIndex++;
        }
    }
    else{
        for(int32_t i = nRightIndex; i < (nNum - nMid); i++){
            lpArrTmp[nArrIndex] = lpBegin[i+nMid];
            nArrIndex++;
        }
    }
    // 设置回去
    for(int32_t i = 0; i < nNum; i++){
        lpBegin[i] = lpArrTmp[i];
    }
}
// 基础的深度优先重点在于节点遍历．而不是，走完所有可能路径．
void Visit(int nCurIndex, int32_t nTag){
    nVisitTick++;
    stNodes[nCurIndex].m_nEle.m_bVisit = true;
    stNodes[nCurIndex].m_nEle.m_nFirstTick = nVisitTick;
    stNodes[nCurIndex].m_nEle.m_nTag = nTag;
    for(int i = 0; i < 9; i++){
        if(stEdges[nCurIndex][i].m_bValid && stNodes[i].m_nEle.m_bVisit == false){
            Visit(i, nTag);
        }
    }
    stNodes[nCurIndex].m_nEle.m_nLastTick = nVisitTick;
    nVisitTick++;// 用来保证LastTick不出现重复
}

特意说明下，这里的深度优先访问是最基础的深度优先版本．此版本主要侧重于对每个可达节点执行一次访问．

2.图的最小生成树
(1). 定义
图的最小生成树（Minimum Spanning Tree，MST）是一个在图论中常见的概念。给定一个加权连通图（即图的每条边都有一个权重，连通图是图中任意两点均可相互到达的意思），最小生成树是一个子图，它包含了原图中的所有顶点，且所有的边都属于原图的边，同时边的权值和在所有这样的子图中是最小的。换句话说，最小生成树是一个连通所有顶点的树，且所有边的权值和最小。（也可说成是代价最小的连通所有顶点的子图）

最小生成树问题是一个优化问题，它在网络设计、电路设计等领域有广泛的应用。例如，在构建通信网络时，我们可能希望以最小的成本连接所有的城市，这就可以通过求解最小生成树问题来实现。

求解最小生成树问题的常见算法有两种：普里姆算法（Prim's algorithm）和克鲁斯卡尔算法（Kruskal's algorithm）。

普里姆算法：
(1). 将源节点加入当前最小生成树．
(2). 对所有边按权重排序．
(3). 循环迭代：
a. 从所有边中选出跨越当前最小生成树，图剩余部分的权重最小的边．跨越意味着此边一个节点在当前最小生成树中，另一节点不在．
b. 将此边的另一节点也加入当前最小生成树．
(4). 树中所有节点均加入最小生成树后，迭代结束．获得最小生成树．

克鲁斯卡尔算法：
(1).对图中的所有边按照权值大小进行排序．
(2). 按照权值从小到大的顺序依次选择边。
在选择每一条边时，需要判断这条边的两个顶点是否已经在同一个连通分量中，如果是，则跳过这条边；如果不是，则将这条边加入最小生成树中，并更新连通分量的信息。

(2). 实例
在这里插入图片描述
可利用上述算法求解上图中的一颗最小生成树．

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/479127.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

解锁AI之门：协助探索Amazon Bedrock服务

解锁AI之门：协助探索Amazon Bedrock服务

AI愈加强大的功能和广泛的应用场景&#xff0c;正逐渐改变着我们的工作和生活方式。 Amazon Bedrock在AI的时代潮流中&#xff0c;也以其强大而灵活的功能特性&#xff0c;正在成为越来越多企业和个人的智能助手。 亚马逊云科技通过VERYCLOUD睿鸿股份的服务能力&#xff0c;使…
阅读更多...
PyTorch深度学习：如何提升遥感影像的地物分类精度？

PyTorch深度学习：如何提升遥感影像的地物分类精度？

我国高分辨率对地观测系统重大专项已全面启动&#xff0c;高空间、高光谱、高时间分辨率和宽地面覆盖于一体的全球天空地一体化立体对地观测网逐步形成&#xff0c;将成为保障国家安全的基础性和战略性资源。未来10年全球每天获取的观测数据将超过10PB&#xff0c;遥感大数据时…
阅读更多...
F. Microcycle（dfs 搜寻路径 + 并查集）

F. Microcycle（dfs 搜寻路径 + 并查集）

解析&#xff1a; 本题的意思是&#xff0c;求一个环的最小的那条边。 并且输出其这个环的点。 我们可以利用并查集&#xff0c;进行确定其是否有环路。在将所用的边从大到小排序。 利用 vector容器&#xff0c;pop_back() 和 push的特性。 起点为 u终点为 v寻找路径。 代…
阅读更多...
P2789 直线交点数题解

P2789 直线交点数题解

题目 假设平面上有N条直线&#xff0c;且无三线共点&#xff0c;那么这些直线一共能有多少不同的交点数&#xff1f; 输入输出格式 输入格式 一行&#xff0c;一个整数N&#xff0c;代表有N条直线。 输出格式 一行&#xff0c;一个整数&#xff0c;表示方案总数。 输入输…
阅读更多...
金融知识分享系列之：出场信号RSI指标

金融知识分享系列之：出场信号RSI指标

金融知识分享系列之&#xff1a;出场信号RSI指标 一、出场信号RSI指标二、RSI指标原理三、 指标用法四、RSI指标总结 一、出场信号RSI指标 名称&#xff1a;相对强弱指标参数&#xff1a;(默认14)组成&#xff1a;RSI线以及30轴、50轴、70轴构成 0-30是极弱&#xff1a;0-30的…
阅读更多...
天天爱掼蛋规则

天天爱掼蛋规则

一、牌型 1、单张&#xff1a;任意一张单牌&#xff1b; 2、对子&#xff1a;任意两张点数相同的牌&#xff0c;如33、44&#xff1b; 3、三同张&#xff1a;三张牌点相同的牌型&#xff0c;如555&#xff1b; 4、三同连张&#xff08;也叫钢板&#xff09;&#xff1a;两组…
阅读更多...
蓝桥杯单片机快速开发笔记——特训2 按键的长按与短按

蓝桥杯单片机快速开发笔记——特训2 按键的长按与短按

一、题目要求 在CT107D单片机综合训练平台上&#xff0c;通过I/O模式编写代码&#xff0c;实现以下功能&#xff1a; 系统上电后&#xff0c;关闭蜂鸣器、继电器和全部指示灯&#xff0c;数码管显示初始值为28&#xff0c;仅显示数码管最右边两位。利用定时器0实现10ms间隔定…
阅读更多...
分享基于PDF.js的pdf阅读器代码

分享基于PDF.js的pdf阅读器代码

一、前言 有时候开发PC端web页面的时候会遇到PDF预览、下载等功能&#xff0c;为了兼容浏览器&#xff0c;需要找一款前端插件进行开发。比较好的PDF插件&#xff0c;就是mozilla的pdf.js&#xff08;注意是mozilla&#xff0c;如果你百度遇到需要收费的&#xff0c;那应该是下…
阅读更多...
使用clion开发tftlcd屏，移植驱动时遇到的问题记录

使用clion开发tftlcd屏，移植驱动时遇到的问题记录

问题现象 屏幕只有一半屏在刷新 问题出现的情况(在CLION开发时遇到过) 总结
阅读更多...
构造函数和析构函数两兄弟的作用是什么

构造函数和析构函数两兄弟的作用是什么

[TOP] &#xff08;1&#xff09;构造函数 1.1 概念 对于以下Date类&#xff1a; class Date { public:void Init(int year, int month, int day){_year year;_month month;_day day;}void Print(){cout << _year << "-" << _month << …
阅读更多...
【综述】二维半导体和晶体管在集成电路未来应用

【综述】二维半导体和晶体管在集成电路未来应用

一篇关于二维半导体和晶体管在集成电路未来应用的综述文章。 文章由Lei Yin、Ruiqing Cheng、Jiahui Ding、Jian Jiang、Yutang Hou、Xiaoqiang Feng、Yao Wen和Jun He*共同撰写&#xff0c;发表在《ACS Nano》2024年第18卷上。 Figure 1: CMOS晶体管的演变 描述了CMOS晶体管…
阅读更多...
Mysql数据库事务

Mysql数据库事务

目录 一、Mysql数据库事务的概念 1.事务的定义 2.事务的特点 2.1原子性 2.2一致性 2.3隔离性 2.4持久性 3.事务之间的相互影响 3.1脏读 3.2不可重复读 3.3幻读 3.4丢失更新 4.如何解决事务的干扰 4.1read uncommitted——读取尚未提交的数据 4.2read committed—…
阅读更多...
ros time 时间戳改为机器开机时间

ros time 时间戳改为机器开机时间

一、问题描述 因项目需要,需要"ros::Time::now()" 改成获取机器开机时间,此处针对rospy的机器时间修改。 二、修改方法 修改ros源码的文件 /opt/ros/noetic/lib/python3/dist-packages/rospy/rostime.py 修改如下: 定位到 get_rostime() &#xff0c;并将 float_…
阅读更多...
面试笔记——MySQL（事务：事务特性、并发事务、事务隔离、Redo Log与Undo Log、MVCC）

面试笔记——MySQL（事务：事务特性、并发事务、事务隔离、Redo Log与Undo Log、MVCC）

事务 概念与特性 事务&#xff08;Transaction&#xff09;指的是一组数据库操作&#xff0c;这些操作要么全部成功执行&#xff0c;要么全部不执行&#xff0c;保证了数据库的一致性和完整性&#xff0c;它使得数据库操作可以按照逻辑上的单元进行组织和执行&#xff0c;提高…
阅读更多...
视频号小店入口在哪？怎么运营？全流程分享！

视频号小店入口在哪？怎么运营？全流程分享！

我是电商珠珠 视频号小店是视频号在22年7月宣布的电商平台&#xff0c;是供商家做店所使用。到现在也发展了不过一年的时间&#xff0c;所以有很多商家都想要往这个平台上转&#xff0c;其中包括新手。因为这个平台属于初期&#xff0c;所以红利比较大&#xff0c;规则限制没有…
阅读更多...
CDMP认证是一个什么样的证书？有必要参加CDMP培训吗？通过率高不高？

CDMP认证是一个什么样的证书？有必要参加CDMP培训吗？通过率高不高？

在当前数字化时代&#xff0c;数据管理变得愈发重要。为了满足社会对数据管理人才的紧迫需求&#xff0c;DAMA国际于2004年推出了CDMP数据管理专业认证。这是一项综合资格认证&#xff0c;涵盖学历教育、工作经验和专业知识考试。CDMP认证是全球唯一的数据管理方面权威性认证&a…
阅读更多...
[Rust] 使用vscode实现HelloWorld程序并进行debug

[Rust] 使用vscode实现HelloWorld程序并进行debug

一、简介 本文介绍了如何使用vscode编写rust&#xff0c;实现打印"Hello, world!"的程序。 二、工具安装 0. 环境介绍&#xff1a; Linux &#xff08;或者windowswsl&#xff09; 1. 安装rust编译器rustc和包管理器cargo。 请参考连接&#xff1a;Rust 程序设…
阅读更多...
wy的leetcode刷题记录_Day92

wy的leetcode刷题记录_Day92

wy的leetcode刷题记录_Day92 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间&#xff1a;2024-3-22 前言 目录 wy的leetcode刷题记录_Day92声明前言2617. 网格图中最少访问的格子数题目介绍思路代码收获 695. 岛屿的最大面积题目介绍思路代码收获 2…
阅读更多...
java网络原理（二）------TCP确认应答和超时重传

java网络原理（二）------TCP确认应答和超时重传

一Tcp协议 TCP&#xff0c;即Transmission Control Protocol&#xff0c;传输控制协议。人如其名&#xff0c;要对数据的传输进行一个详细的控制。 二.TCP协议段格式 知道了端口号才能进一步确认这个数据报交给了哪一个程序。16为端口号是2字节&#xff0c;范围是0到65535.如…
阅读更多...
牛，The O-one ——通过语音交互控制电脑的开源语言模型

牛，The O-one ——通过语音交互控制电脑的开源语言模型

模型介绍 The O-one &#xff1a;一个创新的开源语言模型计算机 可以让你通过语音交互来和你的计算机进行对话&#xff0c;完成询问、指令下达等任务。灵感居然来自Andrej Karpathy 的 LLM 操作系统。O1运行一个代码解释语言模型&#xff0c;并在计算机内核发生特定事件时调用…
阅读更多...
最新文章

Copyright @ 2022~2023