C++基础算法教程|图论入门（一）

👩‍💻博客主页：沾花把玖的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由沾花把玖原创，csdn首发！

😘系列专栏：C++基础算法教程

🎨你的收入跟你的不可替代成正比

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

一、什么是图

很简单，点用边连起来就叫做图。严格意义上讲，图是一种数据结构，定义为：gragh=(V,E)。V是一个非空有限集合，代表结点，E代表边的集合。

二、图的一些定义和概念

1.有向图：图的边有方向，只能按箭头方向从一点到另一点。

2.无向图：图的边没有方向，可以双向。

 

3.结点的度：无向图中与结点相连的边的数目。

4.结点的入度：在有向图中，以这个结点为终点的有向边的数目。

5.结点的出度：在有向图中，以这个结点为起点的有向边的数目。

6.权值：可以理解为边的长度。

7.连通：如果图中结点U、V之间存在一条从U通过若干条边、点到达V的通路，则称U、V是连通的。

8.回路：起点好终点相同的路径，也称为“环”。

9.完全图：一个n阶的完全无向图含有n*(n-1)/2条边；一个n阶的完全有向图含有n*(n-1)条边。

    稠密图：一个边数接近完全图的图。

    稀疏图：一个边数远远少于完全图的图。

10.强连通分量：有向图中任意两点都连通的最大子图。如下图，1-2-5构成一个强连通分量。特别地，单个点也算一个强连通分量，所以下图中有3个强连通分量：1-2-5，3，4。

---

本文内容为小编自己汇总，内容可能会有错误或疏漏，感谢大家的提议！

记得点赞和关注哦~