存图方式【知识点】

2024-04-10 18:38
文章标签 知识点 方式 存图

本文主要是介绍存图方式【知识点】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

邻接矩阵


我们定义一个数组a[MAXN][MAXN]; 那么存图方式就是:
a[i][j]=val;
对于无向图,就代表i和j之间有一条权值为val的边,如果是
无权图,val=1。
对于有向图,就代表i->j(j->i你不清楚)有一条权值
为val的边,无权图的话val=1。
这样我们就能够用这样一个矩阵实现了图的存放,但是,如果点
的数量过大了怎么办呢?二维数组可是开不了很大的啊。比如
有50000个点。那么二位数组就存放不下了,那么我们就要借助
邻接表法了。

邻接表法


大家在前期的时候学STL的时候学过vector,而邻接表就是
用vector来进行存放的
代码实现(以无向图为例)
vector <int > e[ MAXN ]; // edge
vector <int > v[ MAXN ]; // val
cin >>a>>b>>c;
e[a]. push_back (b);
v[a]. push_back (c);
e[b]. push_back (a);
v[b]. push_back (c);

 

 

前向星.

 

前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,

并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.

 

用len[i]来记录所有以i为起点的边在数组中的存储长度.

用head[i]记录以i为边集在数组中的第一个存储位置.

 

那么对于下图:

 

 

 

我们输入边的顺序为:

 

1 2

2 3

3 4

1 3

4 1

1 5

4 5

 

那么排完序后就得到:

 

编号:     1      2      3      4      5      6      7

起点u:    1      1      1      2      3      4      4

终点v:    2      3      5      3      4      1      5

 

得到:

 

head[1] = 1    len[1] = 3

head[2] = 4    len[2] = 1

head[3] = 5    len[3] = 1

head[4] = 6    len[4] = 2

 

但是利用前向星会有排序操作,如果用快排时间至少为O(nlog(n))

链式前向星

我们用head[i]表示以i为起点的最后一条边的储存位置,
next[i]表示与第i条边同起点的上一条边的储存位置,e[i]表
示第i条边的终点。

 

 

我们输入边的顺序为:

 

1 2

2 3

3 4

1 3

4 1

1 5

4 5

加边
struct Edge
{
int next ;
int e;
int w;
} edge [ MAXN ];edge[i].next表示同起点的上一条边,edge[i].e代表这条边的终点,
edge[i].w为权值。void add (int u,int v,int w)
{
edge [cnt ].w = w;
edge [cnt ]. to = v;
edge [cnt ]. next = head [u];
head [u] = cnt ++;
}
cnt初始化为0,head初始化为-1。
边的遍历,遍历以u为起点的所有边
for (int i= head [u];~i;i= edge [i]. next )
{
cout <<u<<" ->" <<edge [i].e<< endl ;
}
倒序遍历
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10050
struct EDGE
{int w;//权值 int next;//与该边同起点的上一条边的位置 int e;//边的终点 
}edge[MAXN];
int cnt; 
int head[MAXN];//以i为起点的最后一条边
void add(int u,int v,int w)
{edge[cnt].w=w;edge[cnt].e=v;edge[cnt].next=head[u];head[u]=cnt++;
} int main()
{memset(head,0,sizeof(head));cnt=1;int n,a,b,c;cin>>n;for(int i=1;i<=n;i++){cin>>a>>b>>c;add(a,b,c);}int start;cin>>start;for(int i=head[start];i!=0;i=edge[i].next){cout<<start<<"->"<<edge[i].e<<" "<<edge[i].w<<endl;}return 0;
}

 

这篇关于存图方式【知识点】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/891830

相关文章

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

springboot security之前后端分离配置方式

《springbootsecurity之前后端分离配置方式》:本文主要介绍springbootsecurity之前后端分离配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的... 目录前言自定义配置认证失败自定义处理登录相关接口匿名访问前置文章总结前言spring boot secu

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》:本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties

Flutter打包APK的几种方式小结

《Flutter打包APK的几种方式小结》Flutter打包不同于RN,Flutter可以在AndroidStudio里编写Flutter代码并最终打包为APK,本篇主要阐述涉及到的几种打包方式,通... 目录前言1. android原生打包APK方式2. Flutter通过原生工程打包方式3. Futte

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Vue中组件之间传值的六种方式(完整版)

《Vue中组件之间传值的六种方式(完整版)》组件是vue.js最强大的功能之一,而组件实例的作用域是相互独立的,这就意味着不同组件之间的数据无法相互引用,针对不同的使用场景,如何选择行之有效的通信方式... 目录前言方法一、props/$emit1.父组件向子组件传值2.子组件向父组件传值(通过事件形式)方

Python实现Microsoft Office自动化的几种方式及对比详解

《Python实现MicrosoftOffice自动化的几种方式及对比详解》办公自动化是指利用现代化设备和技术,代替办公人员的部分手动或重复性业务活动,优质而高效地处理办公事务,实现对信息的高效利用... 目录一、基于COM接口的自动化(pywin32)二、独立文件操作库1. Word处理(python-d

Java 中实现异步的多种方式

《Java中实现异步的多种方式》文章介绍了Java中实现异步处理的几种常见方式,每种方式都有其特点和适用场景,通过选择合适的异步处理方式,可以提高程序的性能和可维护性,感兴趣的朋友一起看看吧... 目录1. 线程池(ExecutorService)2. CompletableFuture3. ForkJoi

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语