文档章节

前向星和链式前向星

o
 osc_isezqdgg
发布于 2019/09/18 13:04
字数 734
阅读 11
收藏 0

精选30+云产品,助力企业轻松上云!>>>

在学最短路是就看见了这个东西,觉得会很难,今天终于开学这个知识了

前向星是一个存图的工具,一种特殊的边集数组 所以前向星数组对应的其实是边的信息,下标就是边的下标

前向星

前向星 把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大 并且记录下以某个点为起点的所有边在数组中的起始位置和存储长度 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 起点 1 1 1 2 3 4 4 终点 2 3 5 3 4 1 5 len[1]=3 head[1]=1 len[2]=1 head[2]=4 len[3]=1 head[3]=5 len[4]=2 head[4]=6

但是前向星会有排序操作,快排时间O(nlog(n))

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
int cnt=0;
int head[N];//存储起点为Vi的第一条边的位置
struct note{
    int from;
    int to;
    int w;
}edge[N];
bool cmp(note a,note b){//排序逻辑
    if(a.from==b.from&&a.to==b.to)return a.w<b.w;
    if(a.from==b.from)return a.to<b.to;
    return a.from<b.from;
}
void add(int u,int v,int w){
    edge[cnt].from=u;
    edge[cnt].to=v;
    edge[cnt++].w=w;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }

    sort(edge,edge+m,cmp);
    memset(head,-1,sizeof(head));
    head[edge[0].from]=0;
    for(int i=1;i<m;i++){
        if(edge[i].from!=edge[i-1].from)//确定起点为Vi的第一条边的位置
            head[edge[i].from]=i;
    }
    int start;
    scanf("%d",&start);//输出某个确定点的连接情况
    for(int k=head[start];edge[k].from==start&&k<m;k++){
        cout << edge[k].from<<" " << edge[k].to<<" "<< edge[k].w<<endl;
    }
    return 0;
}

链式前向星

/* 链式前向星 利用链式取储存图的情况 */

//不理解head和edge[cnt].from的含义
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e4+5;
int head[N];//链式地址
int cnt=0;//边的下标
struct node{
    int from;//表示与第cnt条边同起点的上一条边的储存位置
    int to;
    int w;
}edge[N];
void add(int u,int v,int w){
    edge[cnt].w=w;//第cnt条边的权值是w
    edge[cnt].to=v;//第cnt条边的终点是v
    edge[cnt].from=head[u];//head[i]表示以i起点的最后一条边的储存位置
    head[u]=cnt++;//head[];
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(head,0,sizeof(head));
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    int start;
    scanf("%d",&start);
    for(int i=head[start];i!=0;i=edge[i].from){//输出某个指定结点的连接情况
        cout<<start<<"->"<<edge[i].to<<" "<<edge[i].w<<endl;
    }
    return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
链式前向星

链式前向星 在之前先来看一下边集数组。 边集数组是图的表示法的一种,前向星是边集数组的一种,链式前向星是前向星的一种。 前向星 前向星是把边的起点从小到大排序,起点一样按同样的规则排...

小张人
2019/08/03
0
0
存图利器——链式前向星

存图的各种数据结构,复杂如下 邻接矩阵 O(1)(查询一条边) O(n)枚举出边 O(N*N)空间复杂度 前向星  O(n)(查询一条边) O(n)枚举出边 O(N)空间复杂度 (预处理时间复杂度(O(N...

osc_h4uembb3
2018/10/19
2
0
20190214Test(栈与队列)

完整链接 20190214Test(栈与队列) 一:关系网络(relationship) 考分:100 终分:100 难度:普及+ 题干: 将临接矩阵转化为STL的list链式前向星储存,将list排序,直接BFS从起点走到终点,不...

osc_3ij8s0nv
2019/02/15
2
0
前向星与链式前向星

这里借鉴了一些大佬的文章和代码,给出链接,谢谢 https://blog.csdn.net/ACdreamers/article/details/16902023 https://blog.csdn.net/wuhuajunbao/article/details/22589619 引言 一般来讲......

osc_u69w8vfw
2018/08/02
1
0
链式前向星

首先认识一下什么是“前向星”: 前向星是一个特殊的边集数组,通过将边集数组中的每条边按照起点排序(必要时起点相同的边再按终点排序),并记录下以某个点为起点的所有边在数组中的其实位...

卫莨
2017/10/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用命名管道承载gRPC

最近GRPC很火,感觉整RPC不用GRPC都快跟不上时髦了。 gRPC设计 gRPC是一种与语言无关的高性能远程过程调用 (RPC) 框架。刚好需要使用一个的RPC应用系统,自然而然就盯上了它,但是它真能够解...

osc_nq69o22c
26分钟前
16
0
06-敏捷开发框架-apis 脚本库 引用位置无关性设计

动态引入技术的设计,对我们来说非常重要。 同时也说明动态语言的使用对我们来说也是非常重要。 没有动态语言的支撑,有些想法可能不容易实现,或者有替代方案,可能会花更大的代价。 前端开...

osc_5zg9z6t1
28分钟前
21
0
(三)学习了解OrchardCore笔记——灵魂中间件ModularTenantContainerMiddleware的第一行①的模块部分

  了解到了OrchardCore主要由两个中间件(ModularTenantContainerMiddleware和ModularTenantRouterMiddleware)构成,下面开始了解ModularTenantContainerMiddleware中间件第一行代码。   ...

osc_kdarxvx0
29分钟前
15
0
50Mn18Cr4V锻锻环件

电机无磁护环怎么锻性能才能《高高》?50Mn18Cr4V高锰无磁钢在变形温度为900~1 100℃、应变速率为0.1 ~10s-1条件下的热变形行为. 结果,VC第二相的应变诱导析出对50Mn18Cr4V的热变形行为产生...

无磁钢
29分钟前
16
0
【遇见offer】一汽-大众实习生专场来啦!成长+学习+福利,一个也不能少~

在上次一汽-大众的社招直播之后,实习生的专场招聘也终于来啦! 针对2020年暑期,我们提供了非常多的实习岗位给大家选择。 如果你想得到大厂实习的宝贵经验,如果你想得到更快速的成长,如果...

osc_b88oux8w
31分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部