图的介绍#

一、引言#

前面我们学习了很多线性结构，以及树，接下来我们来看看同样是非线性结构的图。

对于树来说，有n-1个边（edges），因为每个孩子都有父亲，而图之间的节点是任意链接的。

可以说树就是一种特殊的图。

对于图的研究，通常被称为图论。

我们可以这么表示G=(V,E),V可以说是有序对中的第一个对象，E是第二个对象。第一个对象必须总是顶点集，第二个必须总是边集。

有序数对（a,b)不等于（b，a），除非a和b是相等的。

当然也有无序对，用{a,b}表示。

无序对中（a,b)等于（b，a）

二、思考#

我们来给这些节点命名，不代表顺序！

上图可以表示为V={v1,v2,v3,v4,v5,v6,v7,v8}

现在我们的边集是什么呢？为了回答这个问题，我们首先需要知道如何表示一条边。

一条边由它的两个端点来唯一标识。

Edges分为两种：

左边是单向的，右边是双向的。

一条有向边可以表示一个有序对。比如上图左边可以是(u,v)。起点u，终点v。

如果我们要表示（v，u），那么得从v画一条有向线段指向u。

无向的边可以表示一组无序对。比如右图就是{u，v}

所以我们现在知道该如何表达边集。

E={{v1,v2},{v1,v3},``````}后续就不写了，就是把每个无序对写下来喵😎

三、向图vs无向图#

有向图是一个图全是有向边，无向图是一个图全是无向边。

很多现实系统或者问题都可以用图来建模，图被用来表示具有某种组合对关系的对象的集合。

四、应用#

• 角色关系图
• 网络拓扑图
• 渣女备胎图
• 舔狗图
• Dns解析图

五、加权#

有时候在一个图中，所有链接不能被同等对待，有些链接比其他的更重要一些。

如下图是一个城市道路图。

这里肯定不能对边一视同仁。因为道路不一样长，那么我们就得把距离考虑在内。

在这种情况下，我们就需要对每条边赋予一定的权重。比如在图上面表上长度，我懒得表了🫨