图的存储

佚名 6年前 (2020-02-03) 算法 1032人围观抢沙发百度已收录

1.邻接矩阵

g[N][N]二维数组存储，一般是稠密图

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

注意数据范围，点的数目N不能太大

2.邻接表

一般用于稀疏图

static int N= , M=2*N;
static int h[]=new int[N];
static int e[]=new int[N]; //M 无向边 ; N 有向边
static int ne[]=new int[N];//M
static int w[]=new int[N];
static int idx;
static void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

Arrays.fill(h,-1);