最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界视讯！图论之存图

来源：博客园


(资料图片仅供参考)

图论之存图 2023.4.25

概述

  • 主要有四种
  • 每种都有不同的用途
  • 为方便，下文记点集为 \(|V|\), 大小为 \(n\);
  • 边集为 \(|E|\), 大小为 \(m\)。

01 直接存边

时间复杂度：
  • 遍历（DFS，BFS） \(\Theta(\infin)\)
  • 判断是否存在 \(\Theta(m)\)
空间复杂度：
  • \(\Theta(m)\)

代码

struct Edge{    int u,v,w;    Edge(int a,int b,int c){u=a,v=b,w=c;}}edge[100010];int cnt=1;void addedge(int u,int v,int w){    edge[cnt++](u,v,w);}

优点

  • 可能在某些算法里会用到
  • 如 Krustal,Bellman-Ford

缺点

  • 无法快速的判断是否存在 \((u,v)\) 边
  • 无法DFS或BFS（即无法遍历图）

02 邻接矩阵

时间复杂度：
  • 遍历（DFS，BFS） \(\Theta(n^2)\)
  • 判断是否存在 \(\Theta(1)\)
空间复杂度：
  • \(\Theta(n^2)\)

代码

#define inf 0x3f3f3f3fint d[101][101];void addedge(int u,int v,int w){    d[u][v]=w;}void dfs(int u,int fa){    for(int i=1;i<=n;i++){        if(d[u][i]!=inf){            cout<"<优点
  • 适合稠密图
  • 可以快速判断一条 \((u,v)\) 边是否存在
缺点
  • \(\Theta(n^2)\)还是慢了些
  • 不支持重边
03 vector
vector YYDS
时间复杂度：
  • 遍历（DFS，BFS） \(\Theta(n+m)\)
  • 判断是否存在 \(\Theta(m)\)
空间复杂度：
  • \(\Theta(m)\)
代码
struct Edge{    int v,w;    Edge(int b,int c){v=b,w=c;}};vectoredge[100010];void addedge(int u,int v,int w){    edge[u].push_back(Edge(v,w));}void bianli(){//用的循环    for(int i=1;i<=n;i++){        if(!a[i].empty()){            for(int j=0;j"<
优点
  • 适合稀疏图
  • 时间复杂度优秀
  • 好写 （最主要的
缺点
  • 无法快速的判断是否存在 \((u,v)\) 边
04 链式前向星（邻接表）
好多种叫法。
时间复杂度：
  • 遍历（DFS，BFS） \(\Theta(n+m)\)
  • 判断是否存在 \(\Theta(m)\)
空间复杂度：
  • \(\Theta(m+n)\)
代码
const int maxn=1001,maxm=100001;struct Edge{    int next;//后继结点    int v;    int val;};Edge edge[maxm*2+5];int first[maxn];//头指针int vis[maxn];int cnt,ans,n,m;void addedge(int u,int v,int w){    cnt++;    edge[cnt].next=first[u];//(1)    edge[cnt].v=v;    edge[cnt].val=w;    first[u]=cnt;//(2)}
这里其实是和 vector差不多的链表思路，但是这里使用了定长数组实现。代码中巧妙的地方在于他插入时插入了链表的头部而不是尾部（ (1),(2)处），避免了遍历整个链表的时间。
优点
  • 速度快
  • 如果是无向图，则 \(\texttt{这条边的编号}\oplus1=\texttt{这条边的反边编号}\)
缺点
  • 还是稍微复杂了点
  • 没有 vector简洁
                 

关键词：