设无向图以邻接矩阵表示，设计算法求该无向图中边的数目

假设邻接矩阵为 $A$，那么该无向图中边的数目就是邻接矩阵 $A$ 中非零元素的个数除以 $2$。

具体实现可以遍历邻接矩阵 $A$，统计非零元素的个数，然后除以 $2$ 即可得到边的数目。以下是 Python 代码示例：

def edge_count(adj_matrix):
    count = 0
    n = len(adj_matrix)
    for i in range(n):
        for j in range(i+1, n):
            if adj_matrix[i][j] != 0:
                count += 1
    return count

其中 `adj_matrix` 是邻接矩阵，`n` 是矩阵的大小，遍历时只需遍历矩阵的上三角即可。最后返回的 `count` 就是边的数目。

相关问题

设图G用邻接矩阵存储，设计算法以判断G是否是无向图

判断一个邻接矩阵表示的图G是否是无向图，可以检查矩阵是否对称。

具体算法如下：

1. 遍历矩阵的所有行和列。
2. 对于每个元素A[i][j]，检查是否与A[j][i]相等。
3. 如果所有元素都满足A[i][j] = A[j][i]，则该图是无向图；否则，该图是有向图。

以下是Python代码实现：

def is_undirected(adj_matrix):
    n = len(adj_matrix)
    for i in range(n):
        for j in range(n):
            if adj_matrix[i][j] != adj_matrix[j][i]:
                return False
    return True

其中，adj_matrix为邻接矩阵。如果返回True，则表示该图是无向图；否则，表示该图是有向图。

设计一个算法将无向图的邻接矩阵转为对应邻接表的算法

算法步骤如下：

1. 创建一个空的邻接表，其中包含与无向图中顶点数相同的链表。

2. 遍历无向图的邻接矩阵，对于每个非零元素，将其对应的行和列所代表的顶点加入到邻接表中。

3. 对于每个顶点，将其邻接矩阵中对应的行或列中非零元素所代表的顶点加入到该顶点对应的链表中。

4. 返回生成的邻接表。

例如，对于以下无向图的邻接矩阵：

 1 1 
1  1 1
1 1  1
 1 1 

生成的邻接表如下：

 -> 1 -> 2
1 ->  -> 2 -> 3
2 ->  -> 1 -> 3
3 -> 1 -> 2

其中，每个数字代表一个顶点，箭头表示该顶点所连接的其他顶点。