Storage of drawings (refined version)

Just finished Figure of the storage .

Blog and practice , Consolidate what you just learned qwq..

The blog features ： Describe the characteristics or advantages and disadvantages of different storage , More straightforward .

Front row notice ：

All directed edges are from u To v, Right to use q Express

This clarifies u,v,q The definition of .

The storage of graphs actually has Four ways , The first two are easy to understand , Then it involves stl Of vector So pre knowledge is needed , But it is also more widely used , They are as follows ：

1. Save the edge directly

One dimensional array + The structure has edges ,a[i].u,a[i].v,a[i].q

shortcoming ： Cannot save duplicate edges .

2. Adjacent edge matrix

Two dimensional array storage ( Point to the ) edge ,a[u][v]=q/0

shortcoming ： Because it's a two-dimensional array , Too much space is easy to explode , Cannot save duplicate edges .

advantage ： Inquire about O（1）【 This is very important , This storage method is used to query the card 】

3. Adjacency list

vector<int> a[n] Save edge （ myth ： This is similar to a two-dimensional array , because vector There is one dimension in itself ）

Put the edge on vector Inside ：a[u].push_back(v);

location ： All kinds of pictures are suitable for , Unless there is a special need （ If you need to quickly query whether an edge exists , And less points , have access to Adjacency matrix ）.

4. Chain forward star

stay Adjacency list Add the function similar to linked list on the basis of

This forward star is more complicated , At present, I don't fully grasp , Don't mislead readers , Readers can find other materials to study .

// C++ Version
// head[u]  and  cnt  The initial values of are  -1
void add(int u, int v) {
  nxt[++cnt] = head[u];  //  Successor of current edge 
  head[u] = cnt;         //  The starting point  u  The first side of 
  to[cnt] = v;           //  The end of the current edge 
}

//  Traverse  u  Out of the way 
for (int i = head[u]; ~i; i = nxt[i]) {  // ~i  Express  i != -1
  int v = to[i];
}

location ： All kinds of pictures are suitable for , It belongs to the golden mean of storage .