简单易记图解数据结构与算法——图论若干定义

图的定义，图是指边（弧）和点的集合：

file

点对是有序的就叫做有向图：

file

有时边（弧）有相应的权或值：

file

路径是一个顶点序列w1,w2,w3,w4,w5,...,wn，使得（wi,wi+1）∈E,1 ≤i ＜n，例如w1到w4的一条路径，这条路径有三段边（弧），称这条路径的长度为3，如果路径上所有顶点都是互异的，但第一个和最后一个顶点有可能相同，那么这条路径成为简单路径：

file

一个顶点从自身出发经过一条路径后回到自身，这条路径称之为环：

file

有向图中的圈，是指满足w1 = wn，且至少为1的一条路径，如果该路径是简单路径，我们称之为简单圈。如果一个图没有圈，则称之为无圈图，有向无圈图也成为DAG。

file

无向图中任意顶点都可以通过某一条路径到达拎一个顶点，则称该无向图为连通的，具有该特征的有向图则称之为强连通的：

file

如果有向图不是强连通的，但是去掉方向后的图是连通的，则称之为弱连通图：

file

完全图是指其每一对顶点间都存在一条边（弧）的图：

file

现实生活中机场之间的通达关系、交通路线等都可以用图来描述。

本文由博客群发一文多发等运营工具平台 OpenWrite 发布