当前位置：首页 > news >正文

湘潭哪里做网站电话长春seo公司

news 2025/7/21 13:03:11

湘潭哪里做网站电话,长春seo公司,广州黄埔做网站的公司哪家好,广州信科做网站前言图的存储邻接矩阵方法复杂度应用例题题解邻接表方法复杂度应用前言上一篇文章中（【C算法竞赛图论】图论基础），介绍了图论相关的概念和一种图的存储的方法，这篇文章将会介绍剩下的两种方法&#xff…

前言

图的存储

邻接矩阵

方法

复杂度

应用

例题

题解

邻接表

方法

复杂度

应用

前言

上一篇文章中（【C++算法竞赛 · 图论】图论基础），介绍了图论相关的概念和一种图的存储的方法，这篇文章将会介绍剩下的两种方法，话不多说，步入正题——

图的存储

邻接矩阵

方法

使用一个二维数组 G 来存边，其中 G[u][v] 为 1 表示存在 u 到 v 的边，为 0 表示不存在。如果是带边权的图，可以在 G[u][v] 中存储 u 到 v 的边的边权。

复杂度

查询是否存在某条边：O(1) 。

遍历一个点的所有出边：O(n) 。

遍历整张图： $O(n^{2})$ 。

空间复杂度： $O(n^{2})$ 。

应用

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以 O(1) 查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

例题

题目描述

给定一张 N 个顶点 M 条边的简单无向图。顶点编号为 1 ... N。

第 i 条边 (1 <= i <= M) 连接顶点 U_i 和顶点 V_i 。

请求出满足以下所有条件的三元组 (a, b, c) 组的总数。

1 <= a, b, c <= N
存在连接顶点 a 和顶点 b 的边。
存在连接顶点 a 和顶点 c 的边。
存在连接顶点 b 和顶点 c 的边。

3 <= N <= 100

输入格式

N M

U_1 V_1

...

U_M V_M

输出格式

输出答案。

样例

输入样例 1

5 6
1 5
4 5
2 3
1 4
3 5
2 5

输出样例 1

2

输入样例 2

3 1

1 2

输出样例 2

0

输入样例 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

输出样例 3

4

题解

这题很简单，直接用二维数组去存储，然后枚举三个节点（数据量很小）判断是否都有边连接就行了。

#include <bits/stdc++.h>
using namespace std;int G[110][110];int main() {memset(G, 0, sizeof(G));int n, m;cin >> n >> m;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;G[u][v] = 1;G[v][u] = 1;}int cnt = 0;for (int a = 1; a <= n; a++) {for (int b = a + 1; b <= n; b++) {for (int c = b + 1; c <= n; c++) {if (G[a][b] == 1 && G[a][c] == 1 && G[b][c] == 1) {cnt++;}}}}cout << cnt;return 0;
}