当前位置: article > 正文

无向图的邻接矩阵（数组表示法）

作者：weixin_40725706 | 2024-07-24 10:03:43

踩

无向图的邻接矩阵

图的逻辑结构：多对多

很难用多重链表表示

1.数组（邻接矩阵）表示法

一维数组Vexs[n]，叫顶点表，有n个，所以定义从0到n-1的数组，将n个顶点存储。

顶点之间哪两个有边，怎么表示呢？用二维数组arcs(边的意思）表示，把数组中任意一个元素定义成：如果存在一条弧，从i到j，用<>表示有序，或存在一条边，从i到j，用（）表示无序，那矩阵下标为ij的元素arcs[i][j]就为1，若不存在，就记为0，这就是邻接矩阵的定义

来看无向图的例子：这个邻接矩阵是几乘几？有几个顶点就几乘几,n是几，就是nxn的方阵

两个顶点存在邻接关系（有边），记为1；不存在，记为0

v1到v2有边，也认为v2到v1也有边；不存在边，记为0，还有自身没有边。

特点：

1.对角线上，每一个顶点和自身的关系，自身和自身没有邻接关系，所以为0

2.对称，互为邻接关系

如何计算顶点的度？即：和某一个顶点相关联的边的个数

对于v1,v2和它有边，v4也和它有边，即和他有邻接关系的有两个

这里完全图画错了

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/874023