【图】(三)顶点度的计算 |
您所在的位置:网站首页 › 邻接矩阵求度数 › 【图】(三)顶点度的计算 |
图相关文章: 1. 图的建立 - 邻接矩阵与邻接表 目录 顶点度的计算 1 邻接矩阵计算顶点的度 2 邻接表计算顶点的度 顶点度的计算对于无向图来说,顶点的度 首先介绍一下邻接矩阵的特点: 邻接矩阵中包含了以下信息: ① G的顶点数p就是G的邻接矩阵A的阶数。 ② G的边数q就是A中1的个数的一半。 ③ 顶点 ④ 若A的第i行上的全部元素都为0,则 ⑤ A是对称且对角线上全部元素为0 (反自反且对称)。 ⑥ 若两个图的邻接矩阵相等或通过交换某些行和列后相同,则这两个图是同构的。 其中,我们可以通过这一条来进行计算: 顶点 显然,只需要统计矩阵某一行上非-1元的个数,便是该顶点的度。程序比较容易,请读者自行实现。 2 邻接表计算顶点的度由邻接表的定义可以知道: 使用指针数组G[N],G[i]代表以第i个顶点为头结点的链表,只存与之邻接的顶点。 G[i]链表的长度(除去头结点-自身)即为顶点的度。程序比较容易,代码如下: /* 计算邻接表个顶点的度 */ void CalcDegree_L(AdjList L, int arr[][MaxVertexNum]) { int i, count; LGNode pMove = NULL; for (i = 0; i < L->numV; i++) { count = -1; // 除去自身 pMove = &(L->list[i]); while (pMove) { count++; pMove = pMove->next; } arr[0][i] = i; arr[1][i] = count; } } |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |