重拾算法-3.1-图论-图的存储

为什么会突然想起要重拾算法呢？ 上次认真的学习、复习算法已经是3年以前了，那时候是为了校招，在这之后算法似乎变的不太重要。我只是矜矜业业地做好前端开发该做的工作，但在业务开发越来越熟练的时候，我发现自己的视野也会变的越来越窄。 做程序开发，广度和深度是同样重要的，也许现在的工作中不会直接用上，但是算法、设计模式等等这些底层的知识时候熟练掌握，是我们能不能走得更远的前提，我觉得是时候，再重拾起已经快遗忘的算法，为自己的下一个三年，储备更多的基础知识。 作为前端开发，本系列的算法代码实现，将全部用TypeScript实现，同时也会贴一些力扣的题目方便上手实践。

图的存储

本文主要介绍算法题中，有向图的存储方式。

1. 邻接矩阵

实现方式

图的结点编号为 1 ~ n

g[i][j] 表示点i到j的边权

若i到j没有边，g[i][j]视情况赋值-1、0、inf

存在问题：

​ 不能保存重边

​ 空间消耗太大O(n^2)

2. 邻接表 —— vector实现

实现方式

vector<int> g[], e[];

g[i][j] 保存以点i为起点的第j条边的终点

e[i][j] 保存相应边的边权

代码实现

添加边

void add( int u, int v, int c ) 
{
    g[u].push_back(v);
      e[u].push_back(c);
}

遍历以u为起点的边

for( int i = 0; i < g[u].size(); ++i ) 
{
    int v = g[u][i], c = e[u][i];
}

3. 邻接表 —— 数组实现

实现方式

结点编号 1 ~ n ， 边编号 0 ~ e-1

int first[], to[], nxt[], cost[], e;

first[u] ：以u为起点的第一条边的编号，初始为-1

to[i]： 边i的终点

nxt[i] ：与边i起点相同的下一条边 的编号

cost[i] ：边i的边权

e： 总边数

代码实现

添加边

void add( int u, int v, int c )
{
    to[e] = v; cost[e] = c;
    nxt[e] = first[u];
    first[u] = e++;
}

遍历以u为起点的边

for( int i = first[u]; i != -1; i = nxt[i] ) 
{
    int v = to[i], c = cost[i];
}

注意邻接表保存的是单向边，无向图需要插入两条有向

for( int i = 0; i < m; ++i ) {
    scanf( “%d%d”, &amp;u, &amp;v );
    add(u, v); add(v, u);
}