存图方式【知识点】

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

相关文章

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

JAVA保证HashMap线程安全的几种方式

《JAVA保证HashMap线程安全的几种方式》HashMap是线程不安全的,这意味着如果多个线程并发地访问和修改同一个HashMap实例,可能会导致数据不一致和其他线程安全问题,本文主要介绍了JAV... 目录1. 使用 Collections.synchronizedMap2. 使用 Concurren

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

springboot上传zip包并解压至服务器nginx目录方式

《springboot上传zip包并解压至服务器nginx目录方式》:本文主要介绍springboot上传zip包并解压至服务器nginx目录方式,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录springboot上传zip包并解压至服务器nginx目录1.首先需要引入zip相关jar包2.然

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

python logging模块详解及其日志定时清理方式

《pythonlogging模块详解及其日志定时清理方式》:本文主要介绍pythonlogging模块详解及其日志定时清理方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录python logging模块及日志定时清理1.创建logger对象2.logging.basicCo

C#TextBox设置提示文本方式(SetHintText)

《C#TextBox设置提示文本方式(SetHintText)》:本文主要介绍C#TextBox设置提示文本方式(SetHintText),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录C#TextBox设置提示文本效果展示核心代码总结C#TextBox设置提示文本效果展示核心代

SpringValidation数据校验之约束注解与分组校验方式

《SpringValidation数据校验之约束注解与分组校验方式》本文将深入探讨SpringValidation的核心功能,帮助开发者掌握约束注解的使用技巧和分组校验的高级应用,从而构建更加健壮和可... 目录引言一、Spring Validation基础架构1.1 jsR-380标准与Spring整合1

Android实现打开本地pdf文件的两种方式

《Android实现打开本地pdf文件的两种方式》在现代应用中,PDF格式因其跨平台、稳定性好、展示内容一致等特点,在Android平台上,如何高效地打开本地PDF文件,不仅关系到用户体验,也直接影响... 目录一、项目概述二、相关知识2.1 PDF文件基本概述2.2 android 文件访问与存储权限2.