邻接表

59percent · 2019-07-14 17:24:43 · 个人记录

1、邻接表

用邻接矩阵来表示图，需要用到二维数组，其中很多没有连接的边也都需要占位，占内存比较大，另外对图进行访问的时候也会消耗更多的循环次数。 另外一种方式就是使用邻接表，只存储每个顶点连接的边（边的个数不定）。这样对于大的稀疏图就可以节约大量的内存，同时访问起来更加快速。 邻接表核心结构：

• 顶点用一维数组存储
• 每个顶点的所有邻接边构成一个长度不定的线性表 由于邻接边的动态特性，一般都使用结构体＋指针（单向链表）的方式来实现邻接表，但如果对链表知识没有掌握的同学，也可以采用其它方法实现动态线性表，例如Vector、甚至数组等。

  2、邻接表案例

  邻接表内容：	顶点	边1	边2	......
  A	2	5
  B	3	4
  C	4
  D	5
  E	2

  2、Vector实现

  Vector是c++ stl库提供的可变大小的序列容器，基本操作：

• 头文件：#include <vector>
• 声明变量：vector<int> vec
• 增加元素：vec.push_back(a)
• 下标访问：vec[i]，从0开始到vec.size()-1 可变大小的特性用来实现邻接表非常合适

  2.1 邻接表定义

  vector<int> g[N];//存储n个顶点对应的边，每个是一个vector

  如果加权图，可用一个结构体，例如：

  struct Edge {
  int y; //边连接的顶点
  int w; //权
  };
  vector<Edge> g[N];

  2.2 建边

  cin>>x>>y; //输入一条边
  g[x].push_back(y);  //新增一条边
  //加权图增加结构体：g[x].push_back({y, w}); 
  //无向图一条边加两次：g[y].push_back(x);

  2.3 遍历

  for(int j=0; j<g[i].size();  j++)
  //访问 g[i][j];

  3、指针单链表实现

  把同一个顶点连接的所有边以单链表的方式连接起来，访问的时候按照next元素循环读取。 常见的实现是用结构体＋指针实现单链表。 相比较vector的实现，单链表理解起来要晦涩一些，因此我们建议用vector方式更好，当然如果是超大图存在内存与时间要求的，使用单链表会有性能的优势。

  3.1 邻接表定义

  struct Edge {
  int end;
  Edge *next;
  };
  Edge* g[N];

  3.2 建边

  Edge* e = new Edge;
    e->end = y[i];
    e->next = g[x[i]];
    g[x[i]] = e;
  }

  以上主要是把新的边作为第一条边，其next指向旧的第一条边。

  3.3 遍历

  for(Edge* e=g[i]; e!=NULL; e=e->next)
    //访问e

  4、链式前向星实现

  这是用静态数组实现单链表的一种技巧，将每个边用结构体的形态存储成一个边集（数组），每个边的next指向同一起点的下一条边在边集里的的序号，事实上就是一个链表。g[N]为邻接表，存储每个顶点连接的第一条边（在边集里的序号）。 4.1 定义

  struct Edge {
  int to;
  int next;
  } e[maxn];

  4.2 建边

  int head[maxn];
  int cnt = 1;
  void add(int from, int t) {
  e[cnt].to = t;
  e[cnt].next = head[from];
  head[from] = cnt++;
  }

4.3 遍历

for(int i=head[x];i!=0;i=edge[i].next)