图的两种存储方式

图的两种存储方式

1. 邻接矩阵

• 常用于存储稠密图（边数远大于点）

• 存储方式：

  g [a] [b]存储边 a->b

  #include <iostream>
  #include <cstring>
  using namespace std;
  
  const int N = 510;
  
  int n, m; //n为点数，m为边数
  int g[N][N]; //存储稠密图
  
  int main()
  {
      //邻接矩阵初始化为正无穷
      memset(g, 0x3f, sizeof g);
  
      int a, b, w;
      //可能有重边
      g[a][b] = min(w, g[a][b]);
  
      return 0;
  }

2.邻接表

• 常用于存储非稠密图

• 存储方式：（存储a->b的一条边）

  1. 新节点存储 b 的值
  2. 新节点指向原来头结点所指向的
  3. 头结点指向新节点
  4. idx ++

  #include <iostream>
  using namespace std;
  
  const int N = 1e5 + 10, M = 2e5 + 10;
  
  int n, m; //n为点数，m为边数
  int h[N];
  int e[M], ne[M];
  int idx;
  
  //存储a->b的一条边
  void add(int a, int b)
  {
      //1.新节点存储b的值，2.新节点指向原来的头节点所指向的，3.新节点成为新的头节点，4.idx++
      e[idx] = b, ne[idx] = h[a], h[a] = idx, idx ++ ;
  }
  
  int main()
  {
  	add(a, b);
      return 0;
  }