网站空间怎么做,做美食网站有哪些,山东济南网站建设公司哪家好,东莞软件前言
图的存储
邻接矩阵
方法
复杂度
应用
例题
题解
邻接表
方法
复杂度
应用 前言 上一篇文章中#xff08;【C算法竞赛 图论】图论基础#xff09;#xff0c;介绍了图论相关的概念和一种图的存储的方法#xff0c;这篇文章将会介绍剩下的两种方法#xff…前言
图的存储
邻接矩阵
方法
复杂度
应用
例题
题解
邻接表
方法
复杂度
应用 前言 上一篇文章中【C算法竞赛 · 图论】图论基础介绍了图论相关的概念和一种图的存储的方法这篇文章将会介绍剩下的两种方法话不多说步入正题—— 图的存储
邻接矩阵
方法
使用一个二维数组 G 来存边其中 G[u][v] 为 1 表示存在 u 到 v 的边为 0 表示不存在。如果是带边权的图可以在 G[u][v] 中存储 u 到 v 的边的边权。
复杂度
查询是否存在某条边O(1) 。
遍历一个点的所有出边O(n) 。
遍历整张图。
空间复杂度。
应用
邻接矩阵只适用于没有重边或重边可以忽略的情况。
其最显著的优点是可以 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;
}
邻接表
方法
使用一个支持动态增加元素的数据结构构成的数组如 vectorint adj[n 1] 来存边其中 adj[u] 存储的是点 u 的所有出边的相关信息终点、边权等。
复杂度
查询是否存在 u 到 v 的边如果事先进行了排序就可以使用 二分查找 做到 。
遍历点 u 的所有出边。
遍历整张图。
空间复杂度。
应用
存各种图都很适合除非有特殊需求如需要快速查询一条边是否存在且点数较少可以使用邻接矩阵。
尤其适用于需要对一个点的所有出边进行排序的场合。 本文就到这里了如果有帮助的话记得点赞收藏下次再见啦
