图论基础知识(二)
2020/3/10 5:02:35
本文主要是介绍图论基础知识(二),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
本文转载自我的公众号文章,原文是 lee 神写的,已获原文作者授权。
本期继续更新图论基础知识的一部分总结。
图论的知识基本包括但不限于如下,其中是一两三四五点是面试常考知识点。
序. 图论基础概念
一. 一些图的搜索 BFS与DFS
两. 两种最小生成树MST
三. 三种最短路径
四. 公共祖先LCA
五. 拓扑排序 Toposort
六. 割顶桥
七. 匹配
八. 最大流
图论属于数学和计算机的交叉学科,是我们当今社会生活各个领域有广泛的应用。包括但不限于,交通运输,社交,互联网,工作安排等等。
树的充要条件的讨论 @zerotrac
对于一个包含 n 个节点 m 条边的无向图,如果它是一棵树,那么必须满足以下三个条件中的两个:
- m = n - 1
- 该无向图连通
- 该无向图无环
可以发现,第二个条件「该无向图连通」和第三个条件「该无向图无环」都需要我们对至少整个图进行一次遍历。
因此只统计图的出入度、边数等信息而不对整个图进行遍历的所有算法都是错误的。
很多民间流传的DFS和BFS的区别分析,惨不忍睹。个人认为BFS和DFS本身没什么可比性,两个都是面试必须掌握的知识,从来就不存在选择哪一个方法的问题。
下面看一道LeetCode原题
原贴和解释链接🔗如下:
https://leetcode.com/problems...
下一期,分享面试题中图常用几种表示形式。欢迎关注和赞赏。
欢迎关注小猪的公众号,查看小猪的更多文章!
小猪爱你们哟~
这篇关于图论基础知识(二)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15史上最强 AI 翻译诞生了!拳打谷歌,脚踢 DeepL
- 2024-05-29蓝桥杯大赛单片机比赛经验总结
- 2024-05-29AI 一键生成高清短视频,视频 UP 主们卷起来...
- 2024-05-29打造 AI “看牙”新体验,当 Serverless 遇上口腔医疗
- 2024-05-27取代或转型?人工智能对软件测试的影响(内附工具推荐)
- 2024-05-14让创意在幻觉中肆虐: 认识Illusion Diffusion AI
- 2024-05-08Sora从入门到入门-白话版1
- 2024-05-082024年github开源top100中文
- 2024-05-083、最大池化maxinmum pooling
- 2024-05-08动态规划基础思想