5 篇

数据结构与算法(二十三)——有向图

定义

一幅有方向性的图(有向图)是由一组顶点和一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点。

在一幅有向图中,一个顶点的出度为由该顶点指出的边的总数;一个顶点的入度为指向该顶点的边的总数。

一条有向边的第一个顶点称为它的,第二个顶点则被称为它的

继续阅读

数据结构与算法(二十二)——广度优先搜索

定义

给定一幅图和一个起点S,找到从S到给定目的顶点V的一条最短路径。

使用一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将顶点加入队列,然后重复以下步骤直到队列为空:

  • 取队列中的下一个顶点V并标记它。
  • 将与V相邻的所有未被标记过的顶点加入队列。

继续阅读

数据结构与算法(二十)——无向图

定义

图是由一组顶点和一组能够将两个顶点相连的边组成的。

enter image description here

当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并称该连接依附于这两个顶点。

某个顶点的度数即为依附于它的边的总和。子图是由一幅图的所有边的一个子集组成的图。

路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。是一条至少含有一条边且起点和终点相同的路径。简单环是一条不含有重复顶点和边的环。路径或环的长度为其中所包含的边数。

继续阅读