图形是一组对象的图形表示,其中一些对象对通过链接连接,互连的对象由称为顶点的点表示,连接这些顶点的链接称为边。
形式上,图是一对集合(V,E),其中 V 是顶点集合,而 E 是边集合,连接成对的顶点。看一下下图-
在上图中,
V={a,b,c,d,e}
E={a,b,ac,bd,cd,at}
数学图可以用数据结构表示,我们可以使用顶点数组和边缘二维数组来表示图,在继续进行之前,让我们熟悉一些重要术语-
顶点 - 图形的每个节点都表示为一个顶点,在下面的示例中,标签的圆圈表示顶点,因此,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的路径。
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)