基础图论问题算法总结

发布时间:2021-08-01 07:30:14

这里介绍了图论中常见算法的原理和实现,所有代码已打包,此处可以下载。


一、邻接表存图
用邻接矩阵表示稀疏图会浪费大量内存空间。而在邻接表中是通过把类似于“从顶点0出发有到顶点1、2、3、4的边”这样的信息保存在链表中来表示图的。这样只需要O(|V| + |E|)的内存空间。



  1. #include
  2. #include
  3. std::vector g[max_v];
  4. /**
  5. *边上有属性的情况
  6. *sturct edge{
  7. * int to, cost;
  8. *};
  9. *std::vector g[max_v];
  10. */
  11. int main(void)
  12. {
  13. int v, e;
  14. scanf("%d%d", &v, &e);
  15. for(int i = 0; i != e; ++i){
  16. int s, t;
  17. scanf("%d%d", &s, &t);
  18. g[s].push_back(t);
  19. //g[t].push_back(s);//无向图的情况
  20. }
  21. return 0;
  22. }

二、最短路问题
1.Bellman-Ford求单源最短路
记从起点s出发到顶点i的最短距离为d[i],则有d[i] = min{d[j] + (从j到i的边的权值) | e = (j ,i) ∈ E}。对于图中有圈的情况,设d[s] = 0, d[i] = INF则可以在有限次数内算出新的d。只要不存在从s可达到的负圈,最多在|V| - 1次循环后for(;;)就会break,因此复杂度是O(|V| × |E|)。也就是说,若存在负圈,在第|V|次循环也会更新d值,可以利用这个性质检查是否存在负圈。



  1. struct edge{
  2. int from;
  3. int to;
  4. int cost;
  5. };
  6. edge es[max_e];
  7. int d[max_v];
  8. int v, e;
  9. //从顶点s出发的单源最短路
  10. void bellman_ford(int s)
  11. {
  12. for(int i = 0; i != v; ++i)
  13. d[i] = INF;//无限大
  14. d[s] = 0;
  15. for(;;){
  16. bool update = false;
  17. for(int i = 0; i != e; ++i){
  18. edge e = es[i];
  19. if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
  20. d[e.to] = d[e.from] + e.cost;
  21. update = true;
  22. }
  23. }
  24. if(!update)
  25. break;
  26. }
  27. }
  28. //检查负圈,返回真为有
  29. bool find_negative_loop(void)
  30. {
  31. memset(d, 0, sizeof(d));
  32. for(int i = 0; i != v; ++i){
  33. for(int j = 0; j != e; ++j){
  34. edge e = es[j];
  35. if(d[e.to] > d[e.from] + e.cost){
  36. d[e.to] = d[e.from] + e.cost;
  37. //第n次仍更新则存在负圈
  38. if(i == v - 1)
  39. return true;
  40. }
  41. }
  42. }
  43. return false;
  44. }

2.Dijkstra求无负边的单源最短路
描述:①找到最短距离已经确定的顶点,从它出发更新相邻顶点的最短距离,此后不需要再关心“最短距离已经确定的顶点”。如何得到“最短距离已经确定的顶点”呢?在开始时,只有到起点的最短距离是确定的。在尚未使用过的顶点中,距离d[i]最小的顶点就是最短距离已经确定的顶点。下面给出时间复杂度为O(|V|?)使用邻接矩阵实现的Dijkstra算法。



  1. template
  2. inline t min(t a, t b)
  3. {
  4. return a < b ? a : b;
  5. }
  6. int cost[max_v][max_v];//存权值的邻接矩阵
  7. int d[max_v];//最短距离
  8. bool used[max_v];//已经使用过的图
  9. int v;//顶点数量
  10. void Dijkstra(int s)
  11. {
  12. for(int i = 0; i != v; ++i)
  13. d[i] = INF;
  14. for(int i = 0; i != v; ++i)
  15. used[i] = false;
  16. d[s] = 0;
  17. for(;;){
  18. int v = -1;
  19. //从未使用过的顶点中找出一个距离最小的顶点
  20. for(int u = 0; u != v; ++u)
  21. if(!used[u] && (v == -1 || d[u] < d[v]))
  22. v = u;
  23. if(-1 == v)
  24. break;
  25. for(int u = 0; u != v; ++u)
  26. d[u] = min(d[u], d[v] + cost[v][u]);
  27. }
  28. }

当使用邻接表时,更新最短距离只需要访问每条边1次,因此这部分的复杂度是O(|E|),但是查找顶点需要都枚举一次,最终复杂度还是*方级的。可以使用C++ STL的优先队列priority_queue来实现。在每次更新时往堆里插入当前最短距离和顶点的值对,当取出的最小值不是最短距离的话,就丢弃它。这样算法的复杂度优化到了O(|E|log|V|)。Dijkstra较Bellman-Ford效率更高,但无法应用于存在负边的图。



  1. #include
  2. #include
  3. #include
  4. struct edge{
  5. int to;
  6. int cost;
  7. };
  8. typedef std::pair P;//first 最短距离, second 顶点编号
  9. int v;
  10. std::vector g[max_v];
  11. int d[max_v];
  12. void Dijkstra(int s)
  13. {
  14. std::priority_queue, std::greater

    > que;

  15. for(int i = 0; i != v; ++i)
  16. d[i] = INF;
  17. d[s] = 0;
  18. que.push(P(0, s));
  19. while(!que.empty()){
  20. P p = que.top();
  21. que.pop();
  22. int v = p.second;
  23. if(d[v] < p.first)
  24. continue;
  25. for(unsigned int i = 0; i != g[v].size(); ++i){
  26. edge e = g[v][i];
  27. if(d[e.to] > d[v] + e.cost){
  28. d[e.to] = d[v] + e.cost;
  29. que.push(P(d[e.to], e.to));
  30. }
  31. }
  32. }
  33. }

3.适用于在各种图中求任意两点间距离的Floyd-Warshall
代码极短,十分有效,不解释原理。同样可用于判断是否存在负圈:检查是否存在d[i][i]是负数。复杂度:O(|V|^3)。



  1. template
  2. inline t min(t a, t b)
  3. {
  4. return a < b ? a : b;
  5. }
  6. int d[max_v][max_v];
  7. int v;
  8. void Floyd_Warshall(void)
  9. {
  10. for(int k = 0; k != v; ++k)
  11. for(int i = 0; i != v; ++i)
  12. for(int j = 0; j != v; ++j)
  13. d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  14. }

三、最小生成树问题
1.用于邻接矩阵的Prim
假设有一颗只包含一个顶点v的树T,贪心地选取T和其他顶点之间相连的最小权值的边并把它加入到T中。不断进行这个操作就可以得到生成树了。下面给出的算法时间复杂度是O(|V|?)。



  1. template
  2. inline t min(t a, t b)
  3. {
  4. return a < b ? a : b;
  5. }
  6. int cost[max_v][max_v];
  7. int mincost[max_v];//从集合X出发的边到每个顶点的最小权
  8. bool used[max_v] ;//顶点i是否包含在集合X中
  9. int v;
  10. int Prim(void)
  11. {
  12. for(int i = 0; i != v; ++i){
  13. mincost[i] = INF;
  14. used[i] = false;
  15. }
  16. mincost[0] = 0;
  17. int res = 0;
  18. for(;;){
  19. int v = -1;
  20. //从不属于集合X的顶点中选取从X到其权值最小的顶点
  21. for(int u = 0; u != v; ++u)
  22. if(!used[u] && (v == -1 || mincost[u] < mincost[v]))
  23. v = u;
  24. if(-1 == v)
  25. break;
  26. used[v] = true;//把顶点v加入集合X
  27. res += mincost[v];//把边的长度加入结果
  28. for(int u = 0; u != v; ++u)
  29. mincost[u] = min(mincost[u], cost[v][u]);
  30. }
  31. return res;
  32. }

2.用于邻接表的Kruskal
按照边的权值的顺序从小到大查看一遍(需要排序),若不产生圈或重边,就把这条边加入到生成树中。
如何判断是否产生圈:若要把连接u和v的边e加入到生成树中,只要加入之前u和v不在同一个连通分量里,加入e就不会产生圈,若在就一定会产生圈。引入并查集就可以做到,并查集的实现包含在代码包里。Kruskal最耗时的操作是对边的排序,时间复杂度:O(|E|log|V|)。



  1. #include
  2. #include "Union_Find.cpp"
  3. struct edge{
  4. int u, v, cost;
  5. };
  6. bool comp(const edge &a, const edge &b)
  7. {
  8. return a.cost < b.cost;
  9. }
  10. edge es[max_e];
  11. int v, e;
  12. int Kruskal(void)
  13. {
  14. std::sort(es, es + e, comp);
  15. init(v);//初始化并查集
  16. int res = 0;
  17. for(int i = 0; i != e; ++i){
  18. edge e = es[i];
  19. if(!same(e.u, e.v)){
  20. unite(e.u, e.v);
  21. res += e.cost;
  22. }
  23. }
  24. return res;
  25. }


转载于:https://www.cnblogs.com/tham/p/6827284.html






相关资源:acm图论基本概念和常用算法归纳比较

相关文档

  • 儿童画婚纱简笔画
  • 绍兴周边自驾游可以去哪里
  • 文学名著经典句子
  • 红米redmi3s是全网通吗
  • activeMQ高并发发送消息异常解决方法
  • 三星s换机助手如何使用
  • 展望未来的句子示例
  • 保护城市环境的建议书合集
  • cmos存储器中存放了_CMOS存储器中存放了计算机的一些参数和信息,其中不包含在内的是( )。_学小易找答案...
  • RocketMQ源码分析之Message消费与拉取(下Consume的拉取消费)
  • 大四学生预备党员总结
  • 2020年陕西高考地方专项计划B段理科投档分数线
  • Android TextView的drawLeft无法与文字一起居中解决方案
  • 对联常识ppt
  • 什么是4:4:4、4:2:2、4:2:0?
  • 无锡工资扣税标准2017
  • 暴雨中的秀屏山
  • 高三生物复习知识:基因的分离规律
  • 2020mysql下载教程_2020个人实践版MySQL安装教程
  • 银发帅气动漫帅哥图片
  • 我只想,邀你坐下,喝一杯茶
  • 服务器系统分类
  • 宁夏镇北堡西部影城精选
  • 实习报告的写作标准
  • 街道社区党建工作总结
  • 旅夜书怀杜甫
  • 有关六年级数学教学计划范文
  • 学生深刻自我反省检讨书范本
  • “云生态梦之队”集结完毕 百度与移动、电信、联通达成多项合作
  • 酝 酿
  • 猜你喜欢

  • 孕妈妈如何提高免疫力防流产?
  • 湘教版高中地理必修一第二章第三节《大气环境》优质课件(共35张PPT)
  • 企业网络营销的必然选择 效益型网站建设
  • 原平市利达建材有限公司企业信用报告-天眼查
  • 苏州鹤立恒新材料科技有限公司企业信用报告-天眼查
  • kaios系统有微信吗
  • 第9章操作系统的安全
  • 长春市华洋建材经销处企业信用报告-天眼查
  • 2015年沈阳市中考英语试题及答案解析(Word版)
  • docker volumes-from 使用
  • 七年级道德与法治下册 第三单元 在集体中成长 第六课“我”和“我们”第2框 集体生活成就我课件2 新人教版
  • 高校财务预算绩效管理中平衡计分卡的运用
  • 有余数的除法新人教版小学三年级数学上册2
  • 2018_2019学年高中物理第一章运动的描述第4节实验:用打点计时器测速度课时跟踪检测新人教版必修144
  • 园长秋季开学典礼致辞
  • 【最新2018】幼儿园家长会演讲稿范本-word范文 (2页)
  • 时间轴商务风市场专员求职简历Word模板.docx
  • 心理素质在歌唱中所起的积极作用
  • 水泥谕旨构件项目可行性研究报告环评用(评审版)
  • 2016年秋季广东省广州市番禺区教师资格认定公告
  • 单接口压测和多接口压测tps区别_性能压测-让你了解我们公司真实的过程
  • 微分方程建模详解
  • 最新-竞选岗位演讲稿 公司广告总监岗位竞职演讲稿精选 精品
  • 内蒙古中西部剪纸艺术的典型代表和林格尔剪纸艺术审美价值探究
  • 多媒体启发式教学设计
  • 深氮氲继濞上海)有限公司(企业信用报告)- 天眼查
  • 五年级学生上学期拓展素质评语
  • 【主持词范文】八一建军节战友聚会主持词范本
  • 党课心得体会专题1(5篇)与党课心得体会总结汇编
  • 易拉罐形状和尺寸的最优设计
  • 【最新文档】小学班主任控辍工作计划-word范文模板 (4页)
  • 最新硬件工程师瑟肽旯ぷ髯芙狒呦掳肽旯ぷ骷苹?PT模板
  • 简洁清新毕业论文答辩PPT模板
  • 创造基于能力的企业文化
  • 平顶山市2013—2014学年第一学期期末调研考试九年级化学
  • 简析新时代背景下川剧高腔曲牌的改革变迁
  • 人教版二年级下册数学*题课件-2、表内除法(一)第 3 课时 *均分(3)
  • 精彩的“阅兵式”
  • 中国极片切耳机行业市场调查研究报告(目录)
  • C++程序的内存格局通常分为哪几个区
  • 数学教学工作总结范例
  • 某x司班组机械车工岗位行为规范
  • 2019届高三数学课标一轮复*课件6.1 数列的概念与简单表示法
  • 【最新文档】三年级上册第六单元作文:家乡的美景400字作文-优秀word范文 (3页)
  • 2018西安画室排名前十位哪个画室比较好
  • 为自己喝彩的作文400字
  • 畜牧业机械零件项目可行性研究报告
  • 北京祥虹家用电器修理部企业信用报告-天眼查
  • 数据结构与算法分析第七章 排序
  • 2020年高考语文复*第一编现代文阅读专题一微案一论述类文本阅读学案(含解析)
  • 渗透生活教育理念 促使学生主动学*
  • 如何体面地送礼
  • 小学一年级上学期体育教学总结
  • 美国南方社会的暴力研究——《去吧,摩西》中的暴力主题分析
  • 在线排课系统(论文范文,JSP,JAVA,毕业设计)
  • 连城县新泉供销合作社良福村农资供应网点企业信用报告-天眼查
  • 财务的报表英文翻译大全(含资产负债表、现金流量表、利润表等等)
  • [人教版]小学三年级数学上册第五单元试题
  • 2020届北师大版九年级数学下册: 1 锐角三角函数 第1课时 锐角三角函数(一)
  • 村委会旱情调查报告(1)
  • 关于生活如此精彩的作文
  • 2017-2018九年级班主任工作总结与2017-2018二年级上册语文教学工作总结汇编.doc
  • 宝宝学*说话是一件很神奇的事情
  • 苏教初中语文八下《5紫藤萝瀑布》PPT课件 (5)
  • 「最新」大班幼小衔接工作计划
  • C#课程设计-简单人事管理系统的设计与实现
  • 云南瑞林投资有限公司企业信用报告-天眼查
  • 三年级作文:运动会作文350字_2
  • 创新创业宣传标语大全
  • 2019-2020年度重点小学六年级语文下学期开学考试试卷苏教版 附答案
  • 扫黑除恶工作汇报模板大全
  • 惠州市肉蛋水产批发企业名录152家
  • 市政广场的秋天
  • 信息编码的学习体会
  • 母亲生日讲话稿3分钟
  • 送给朋友的中秋祝福语大全
  • 精选人教版过关练*题五年级下学期小学语文期末模拟试卷IV卷-标准版
  • 长沙格思企业管理咨询有限公司企业信息报告-天眼查
  • 影城服务礼仪培训专题培训课件
  • 【精品资料首发】中国传统建筑体系有哪些要点?
  • 圣安德鲁斯大学计算机科学本科
  • 无形资产课件 第四章 企业专利权管理PPT资料26页
  • 用双眼发现生活的美经典文章
  • 沈阳市冠丰不锈钢有限公司企业信用报告-天眼查
  • 电脑版