数据结构&算法 图形数据结构

• 

  图形数据结构

  图形是一组对象的图形表示，其中一些对象对通过链接连接。相互连接的对象由称为顶点的点表示，连接这些顶点的链接称为边。形式上，图是一对集合（V，E），其中V是一组顶点，而E是一组边缘，连接这对顶点。看一下下图-

  

  在上图中，

  V = {a，b，c，d，e}

  E = {ab，ac，bd，cd，de}
• 

  图形数据结构

  数学图可以用数据结构表示。我们可以使用顶点数组和边缘二维数组来表示图。在继续进行之前，让我们熟悉一些重要术语-

  • 顶点 - 图形的每个节点都表示为一个顶点。在下面的示例中，标记的圆圈表示顶点。因此，A到G是顶点。我们可以使用下图所示的数组来表示它们。此处A可以通过索引0标识。B可以使用索引1标识，依此类推。
  • 边缘 - 边缘表示两个顶点之间的路径或两个顶点之间的线。在以下示例中，从A到B，B到C等的线表示边缘。我们可以使用二维数组来表示一个数组，如下图所示。在这里AB可以在第0行第1列表示为1，BC可以在第1行第2列表示为1，依此类推，将其他组合保持为0。
  • 邻接 - 如果两个节点或顶点通过一条边相互连接，则它们是相邻的。在下面的示例中，B与A相邻，C与B相邻，依此类推。
  • 路径 - 路径表示两个顶点之间的边序列。在以下示例中，ABCD表示从A到D的路径。

  
• 

  基本操作

  以下是图的基本主要操作-

  • 添加顶点 -将顶点添加到图形。
  • 添加边缘 -在图形的两个顶点之间添加一条边缘。
  • 显示顶点 -显示图形的顶点。