数据结构重读 – 图的数组表示法(邻接矩阵)和DFS图遍历算法

可以用两个数组分别存储数据元素(顶点)、数据元素之间的关系(边或弧度)。

顶点数组不说了,表示弧的数组称为“邻接矩阵”AdjMatrix。

对于有向图:AdjMatrix[i][j]为0表示顶点i和顶点j之间无弧,1为i和j间有弧。

对于无向图:AdjMatrix[i][j]同样是1表示有弧,0无弧。单AdjMatrix[i][j]为1则一定有AdjMatrix[j][i]为1,因为弧是无方向对称的。

对于网(弧带权):AdjMatrix[i][j]上是w或者无穷大,w表示连通且有权值w。无穷大是不连通。

数据结构定义如下:

下面我们用上面的结构完成一个无向连通图的创建和DFS

测试数据:

输出结果:

 

Leave a Reply

Your email address will not be published.