数据结构 - 图形数据结构

图形是一组对象的图形表示,其中一些对象通过链接连接.互连对象由称为顶点的点表示,连接顶点的链接称为.

形式上,a图是一对(V,E),其中 V 是顶点集, E 是边集,连接顶点对.看看下面的图表 :

Graph Basics

In上图,

> V = {a,b,c,d,e}

E = {ab,ac,bd,cd,de}

图形数据结构

数学图表可以用数据结构表示.我们可以使用顶点数组和二维边数组来表示图形.在我们继续前进之前,让我们熟悉一些重要的术语;

  • Vertex : 图的每个节点表示为顶点.在以下示例中,标记的圆圈表示顶点.因此,A到G是顶点.我们可以使用数组来表示它们,如下图所示.这里A可以通过索引0来识别.B可以使用索引1来识别,依此类推.

  • Edge :  Edge表示两个顶点之间的路径或两个顶点之间的线.在以下示例中,从A到B,B到C等的线表示边.我们可以使用二维数组来表示数组,如下图所示.这里AB可以表示为1,第0行,第1列,BC为1,第1行,第2列,依此类推,保持其他组合为0.

  • 邻接 : 如果两个节点或顶点通过边缘相互连接,则它们相邻.在以下示例中,B与A相邻,C与B相邻,依此类推.

  • 路径 :  Path表示两个顶点之间的一系列边.在以下示例中,ABCD表示从A到D的路径.

graph

基本操作

以下是图表的基本主要操作 :

  • 添加顶点 : 向图表添加顶点.

  • 添加边 : 在图形的两个顶点之间添加边.

  • 显示顶点 : 显示图的顶点.

要了解有关Graph的更多信息.我们将在接下来的章节中学习如何遍历图表.