首页 > 试题广场 >

对于有n个顶点的无向图,采用邻接矩阵表示,如何判断以下问题:

[问答题]
对于有n个顶点的无向图,采用邻接矩阵表示,如何判断以下问题:
(1)图中有多少条边?
(2)任意两个顶点i和j之间是否有边相连?
(3)任意一个顶点的度是多少?
领接矩阵:n*n的0,1矩阵
发表于 2019-04-19 20:18:00 回复(0)

(1)定义一个计数器,每读到一条边,计数器+1
(2)开一个二维bool形数组

vis[i][j] = true;
vis[j][i] = true;

表示有一条从i到j(j到i)的边
(3)开一个记录度的数组,每读到一条边,两点的度数组+1

int du[1000];
//记录点的度数的数组
cin >> x >> y;
//读入边
du[x]++, du[y]++;
//点的度数++
编辑于 2019-05-28 15:48:48 回复(0)
(1)对于无向图,顶点i的度等于邻接矩阵的第i行(或第i列)非零元素的个数。 (2)要判断顶点i和j之间是否存在边,只需测试邻接矩阵中相应位置的元素arc[i] [j],若其值为1,则有边。否则无边。 (3)根据定义,邻接矩阵是一个n×n的方阵。
发表于 2018-12-08 20:46:16 回复(0)