Adjacency list representation邻接表建图(vector版本)

In the adjacency list representation, each node x in the graph is assigned an adjacency list that consists of nodes to which there is an edge from x. Adjacency lists are the most popular way to represent graphs, and most algorithms can be efficiently implemented using them.

A convenient way to store the adjacency lists is to declare an array of vectors as follows:

  1.  vector<int> adj[N];

The constant N is chosen so that all adjacency lists can be stored. For example, the graph
image.png

  1. adj[1].push_back(2);
  2. adj[2].push_back(3);
  3. adj[2].push_back(4);
  4. adj[3].push_back(4);
  5. adj[4].push_back(1);

If the graph is undirected, it can be stored in a similar way, but each edge is added in both directions.

For a weighted graph, the structure can be extended as follows:

  1. //当边权不是1的时候，可以用pair维护
  2. vector<pair<int,int>> adj[N];

In this case, the adjacency list of node a contains the pair (b,w) always when there is an edge from node a to node b with weight w. For example, the graph can be stored as follows:
image.png

  1. adj[1].push_back({2,5});
  2. adj[2].push_back({3,7});
  3. adj[2].push_back({4,6});
  4. adj[3].push_back({4,5});
  5. adj[4].push_back({1,2});

The benefit of using adjacency lists is that we can efficiently find the nodes to which we can move from a given node through an edge. For example, the following loop goes through all nodes to which we can move from node s:

  1. //这是C++ 11的写法
  2. for (auto u : adj[s]) {
  3.     // process node u
  4. }
  6. //这样枚举就可以了，理解“散列边”这个概念
  7. for (int i = 0; i < adj[i].size(); i++)
  8. {
  10. }

Adjacency matrix representation邻接矩阵建图

An adjacency matrix is a two-dimensional array that indicates which edges the graph contains. We can efficiently check from an adjacency matrix if there is an edge between two nodes. The matrix can be stored as an array

  1. int adj[N][N];

where each value adj[a][b] indicates whether the graph contains an edge from node a to node b. If the edge is included in the graph, then adj[a][b] = 1, and otherwise adj[a][b] = 0. For example, the graph can be represented as follows:
image.png

image.png
If the graph is weighted, the adjacency matrix representation can be extended so that the matrix contains the weight of the edge if the edge exists. Using this representation, the graph corresponds to the following matrix:
image.png

image.png
The drawback of the adjacency matrix representation is that the matrix contains n^2 elements, and usually most of them are zero. For this reason, the representation cannot be used if the graph is large.

你看，这个邻接矩阵是不是就是一个矩阵，表示一个点和另外一个点的连通性

邻接矩阵不能存很大的图，因为受建立二维数组大小的限制。适合存稠密图邻接表可以存很大的图，也可以存很小的图。更适合存稀疏图

Adjacency list representation邻接表建图(一维数组版本)

我一般用这个模板

  1. int h[N], e[M], ne[M], idx; 
  3. void add(int a, int b)
  4. {
  5.     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
  6. }
  8. //调用
  9. scanf("%d%d", &a, &b);
  10. add(a, b), add(b, a);
  11. //双向表，就双向add，单向边就一个add
  12. //要注意一维数组开的大小问题，如果是无向图，M是N的两倍
  13. //如果是有边权的情况，就还需要开一个一维数组w[M]用来维护边权
  14. //理解“散列”的形状
  16. //枚举边
  17. for (int i = h[u]; i != -1; i = ne[i])
  18.     {
  19.         int j = e[i];
  20.         if (!st[j])
  21.         {
  22.             int s = dfs(j);
  23.             res = max(res, s); //所有子树的最大值
  24.             sum += s;          //累积求这个点的子树大小
  25.         }
  26.     }