首页 > 编程语言 >[C/C++]图的存储

[C/C++]图的存储

时间:2024-09-17 20:21:32浏览次数:11  
标签:存储 int 复杂度 dfs edge C++ 数组

一、图的存储方式

      图的存储主要分为五类:邻接矩阵、边集数组、邻接表、链式邻接表、链式前向星。

1.邻接矩阵

        用二维数组w[u][v]表示从u到v的边权

        时间复杂度:O(n^2)

        空间复杂度:O(n^2)

1.模板

//图的存储

for(int i=1;i<=m;++i){//m为边的数量
    cin>>a>>b>>c;
    w[a][b]=c;
    w[b][a]=c;//无向边时需反向存储
}

//图的遍历

void dfs(int u){
    vis[u]=1//标记访问过的点
    for(int v=1;v<=n;++i){
        if(w[u][v]{//有边才访问
            if(vis[v]) continue;//判重
            dfs(v);
        }    
}

注:邻接矩阵适用于点数不多的稠密图中

2.边集数组

         用结构体数组存储第i条边{起点u,终点v, 权值 w}

        时间复杂度:O(nm)

        空间复杂度:O(m)

1、模板

//建立数组

strcut edge{
    int u,v,w;//起点,终点,权值
}e[M];


//图的存储

for(int i=1;i<=m;++i){//m为边数
    cin>>a>>b>>c;
    e[i]={a,b,c}
    //e[i+1]={b,a,c}//无向边反向存储
}

//图的遍历

void dfs(int u){
    vis[u]=1;//标记访问过的边
    for(int i=1;i<=m;++i){
        if(e[i].u==u){
            if(vis[u]) continue;//判重
            dfs(e[i].v);
        }
}

注:复杂度过高,常用于Kruskal算法,需将边按边权排序存储。

3.邻接表

        用出边数组e[i]来存储{终点v,边权w}

        时间复杂度:O(n+m)

        空间复杂度:O(n+m)

1.模板

//建立数组

struct edge{
    int v,w;//终点,边权
};

vector<edge> e[N];//出边数组     尾插存入

//存储图

for(int i=1;i<=m;++i){
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].puah_back({a,c});//无向边反向存储
}


//图的遍历

void dfs(int u,int fa){//当前节点,父节点
    for(auto ed:e[u]){//遍历当前节点所连接的边    ==for(int i=0;i<sizeof(e[u]);++i)
        if(ed.u==fa) continue;//判重
        bfs(ed.v,u);
    }
}

注:不能用于含环的图的存储,不能处理反向边

4.链式邻接表

        用边集数组e[i]存储{起点u,终点v,边权w}  用表头数组h[i][j]存储每条边所以出边的编号

        时间复杂度:O(n+m)

        空间复杂度:O(n+m)

1、模板

//数组建立

struct edge{
    int u,v,w//起点,终点,边权
}
vector<edge> e;//边集数组--记录边的信息
vector<int> h[N];//表头数组--记录边的编号


// 图的存储

for(int i=1;i<=m;++i){
    cin>>a>>b>>c;
    add(a,b,c);
    add(b,a,c);//相邻存储--可用异或快速寻找反向边
}

void add(int a,int b,int c){
    e.push_back({a,b,c};
    h[a].push_back(e.size()+1);
}

//图的遍历

void dfs(int u,int fa){
    for(int i=1;i<=h[u].size();++i){
        int j=h[u][i];//边的编号
        int v=e[j].v;
        if(v==fa) continue;//判重
        dfs(v,u);
    }
}

注:能处理各种图和反向边

5.链式前向星

        边集数组e[i]存{终点v,边权w,下一条边编号ne}  表头数组h[i] 存储i号点的第一条出边,idx为边的编号

        时间复杂度:O(n+m)

        空间复杂度:O(n+m)

1、模板

//数组建立

struct edge{
    int v,w,ne;//终点,边权,下一条边的编号
}e[N];

int h[N],idx=0;//头插入

//边的存入

memset(h,-1,sizeof(h));//初始化表头数组
for(int i=1;i<=m;++i){
    cin>>a>>b>>c;
    add(a,b,c);
    add(b,a,c);
}

void add(int a,int b,int c){
    e[idx]={b,c,h[a]};
    h[a]=idx++;
}


//图的遍历

void dfs(int u,int fa){
    for(int i=h[u];~i;i=e[i].ne){
        int v=e[i].v;
        if(v==fa) continue;//判重
        dfs(v,u);
    }
}

注:能处理各种图,反向边

二、总结

 

临界矩阵边集数组邻接表链式邻接表链式前向星
定义

int w[N][N]

//边

struct edge{
int u,v,w;

}e[N];//边

struct edge{
int v,w;

}

vector<edge> e[N]//边

struct edge{

int u,v,w;

}

vector<int>h[N];//表头

vector<edge>e//边

struct edge{
int v,w,ne;

}e[N];//边

int h[N];//表头

建边w[a][b]=ce[i]={a,b,c}e[a]={b,c}

e.push_back({a,b,c});

h[a].push_back(e.size()+1)

e[idx]={b,c,h[a]};

h[a]=idx++

访问

按行列访问

for(int v=1;v<=m;++v){

        if(w[u][v]){

                vis[v];

                dfs(v);

          }

}

按边顺序访问

for(int i=1;i<=m;++i){

if(e[i].u==u){
if(vis[e[i].v]) continue;

dfs(e[i].v);

先插入后访问

for(auto ed:e[u]){

if(ed.v==fa) continue;

dfs(ed.v,u);

}

先插入后访问

for(int i=1;i<=h.size();++i){
int j=h[u][i];

if(e[j].v==fa) continue;

dfs(e[j].v,u);

先插入后访问

for(int i=h[u];~i;i=e[u].ne){
if(e[i].v==fa)continue;

dfs(e[i].v,u);

时间复杂度O(n^2)O(mn)O(n+m)O(n+m)O(n+m)
空间复杂度O(n^2)O(m)O(n+m)O(n+m)O(n+m)
应用稠密图Kruskal算法

各种图

不能处理反向边

各种图

能处理反向边

各种图

能处理反向边

标签:存储,int,复杂度,dfs,edge,C++,数组
From: https://blog.csdn.net/2401_87426938/article/details/142311555

相关文章

  • C++基础知识7 list
    list1.list的介绍及使用1.1list的介绍1.2list的使用1.2.1list的构造1.2.2listiterator的使用1.2.3listcapacity1.2.4listelementaccess1.2.5listmodifiers1.2.6list的迭代器失效2.1模拟实现list1.list的介绍及使用1.1list的介绍1.2list的使用1.......
  • 深入剖析:C++类对象的内存布局与优化
    深入剖析:C++类对象的内存布局与优化引言在C++编程中,理解类对象的内存布局对于优化内存使用和提高程序性能至关重要。本文将详细介绍C++类对象的内存布局,包括数据成员、虚函数表指针以及静态变量和静态方法在内存中的位置。通过这些知识,我们可以更好地设计和优化我们的类结......
  • C++ 带约束的Ceres形状拟合
    C++带约束的Ceres形状拟合一、CeresSolver1.定义问题2.添加残差AddResidualBlockAutoDiffCostFunction3.配置求解器4.求解5.检查结果二、基于Ceres的最佳拟合残差结构体拟合主函数三、带约束的Ceres拟合残差设计拟合区间限定四、拟合结果bestminmax五、完整代......
  • C++面试题整理 2
    8.C++11新特性又哪些自动类型推导auto,智能指指针(share_ptr,unique_ptr等),for循环简化,线程相关的(std::thread/std::mutex),空指针nullptr,lambda表达式,等等9.share_ptr是线程安全的吗share_ptr里包含引用计数和数据指针,引用计数是原子操作,线程安全的,但是改变数据指针的指向,......
  • C++前后缀分解
    相关知识点C++算法与数据结构打开打包代码的方法兼述单元测试这个算法很容易想到,学习了本文后,可以更快得想到。前后缀分解分治法的一种,将数组和字符串,拆分成前缀和后缀。字符串(数组)的前缀是字符串的前i个元素:s.substr(0,i-1),即s[0]......
  • C++类和对象
    1.类的定义1.1类的格式(1)class为定义的类关键字,Stack为类的名字,{}中为类的主体,注意类定义结束时后面要跟分号。(2)为了区分类中的成员变量,一般我们命名的时候会在前面加上_或m开头,这个不是硬性要求。(3)C++中也兼容struct的用法,struct升级成了类,但他仍兼容C语言的用法,同......
  • C++模板函数实现类型推导
    C++模板函数实现类型推导以快读函数举例说明无法类型推导的情况template<typenameT>inlineTread(){Tx=0;intf=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar(......
  • VScode快速配置c++(菜鸟版)
    1.vscode是什么VisualStdioCode简称VSCode,是一款跨平台的、免费且开源的现代轻量级代码编辑器,支持几乎主流开发语言的语法高亮、智能代码补全、自定义快捷键、括号匹配和颜色区分、代码片段提示、代码对比等特性,也拥有对git的开箱即用的支持。同时,它还支持插件扩展,通过丰......
  • C++内存管理详解:各类变量的存储区域
      在C++中,变量的存储位置取决于它们的类型和生命周期。那么不同的各个变量究竟存储在哪个区域呢?1.不同类型的变量我们首先从变量类型的不同来说明:1.全局变量和静态变量 -存储区:全局/静态区(静态区)-说明:全局变量(包括文件级和函数级的)和使用`static`关键字声明的变......
  • C++的类与对象下
    目录1.初始化列表2.隐式类型转换1.单参数2.多参数(C++11提供的新功能)3.static成员4.友元5.内部类6.匿名对象1.初始化列表C++祖师爷规定初始化列表是成员变量定义与初始化的地方。classTime{public: Time(inthour) :_hour(hour) { cout<<"Time()"<<......