Summary of mapping methods (chain mapping method using hash map)

Abstract

This article will introduce the use of hashes map The method of drawing creation , Use C++STL：unordered_map To build a map . This method has some limitations , But it can be applied to most graph theory . Compared with adjacency table mapping method , Easier to understand and get started .

Principle analysis

choice unordered_map Because it is relative to map, Search faster , It can reduce the time complexity when traversing the graph . The mapping principle is similar to adjacency table , Mapping a collection by an element . Realize the correspondence between parent node and child node set .

This method is often stored with linear structure in the definition , For a general graph , Collocation vector Initialize to ： unordered_map<int,vector<int>>  mp; 

 < Key value > Use int Represents a node ,< It's worth it > Use vector Store a collection of all child nodes of this node .

Mapping and traversal

• Drawing

After defining the above structure , You can create a graph structure in units of edges .

Suppose a graph exists 4 Nodes 5 side , have （1,2）（1,3）（1,4）（2,3）（4,3） Structure , namely

You can create the drawing by  mp[1] .push_bak(2) operation , Incoming node 1 Add nodes to the corresponding child node set 2 . Continue this operation , bring mp It's inside < 1,  {2,3,4} > The data of , Then the node 1 And its child nodes . Allied , You can save the whole picture .

 

For test points n Nodes ,m side , The code for drawing creation is as follows ：

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
unordered_map<int, vector<int>> mp;
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;        // from a Point to b One side of 
		cin >> a >> b;
		mp[a].push_back(b);        // If you need to create an undirected graph , Reconstruction mp[b].push_back(a) The relationship between ; 
	}
}

 

• Traverse

If you want to traverse all the child nodes of a point , You can use the iterator method to iterate .

As for the above example , Traverse 1 All child nodes of . May adopt

for(auto i : mp[1])
{
   cout << i;  // That is, child nodes 
}

  Iterate over nodes using iterators 1 Referred to vector All elements in the array , The element is the child node . 

From this we can see that , This traversal method is much simpler than the adjacency table mapping method supported by arrays , It is also conducive to understanding and analyzing memory .

DFS The traversal code is as follows ：

void DFS(int u)
{
	cout << u << " ";
	st[u] = 1;        // Whether the record has been traversed ;
	for (auto i : mp[u])
	{
		if (!st[i]) DFS(i);        // Search for child points that have not been traversed .
	}
}

BFS The traversal code is as follows ：

void BFS(int u)
{
	memset(st, 0, sizeof st);
	cout << u << " ";
	queue<int> q;
	q.push(u);
	st[u] = 1;
	while (!q.empty())
	{
		int temp = q.front();
		q.pop();
		for (auto i : mp[temp])    // Get the child node set of the header element in the queue 
		{
			if (!st[i])
			{
				cout << i << " ";
                st[i]=1;
				q.push(i);
			}
		}
	}
}

Analysis of advantages and disadvantages

• advantage ：

The advantage of using this method is that the mapping relationship is easy to understand , Mapping and traversal operations are very simple , It is more convenient for beginners to use graph theory . A lot less code . And because of the use of STL Store , You can change the element type at will .

• shortcoming ：

because unordered_map It takes a lot of time to create . Therefore, compared with the adjacency table mapping using array implementation, it is slower .

expand ...

If the title requires Create weighted graph , Then you can change mp Definition of data structure .

Use

unordered_map<int,vector<pair<int,int>>>  mp; 

During drawing creation , With a Point to b The length of is c The edge of can be expressed as

mp[a].push_back({b,c});

In traversal time , Need to be right vector In the process of iteration , take pair Elemental first You can get the child nodes , take second You can get the distance between the current node and the child nodes . 

    
    for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		mp[a].push_back({ b,c });
	}


void DFS(int u)
{
	memset(st, 0, sizeof st);
	cout << u << " ";
	st[u] = 1;
	for (auto i : mp[u])
	{
		int j = i.first;
        int len = i.second;
		if (!st[j]) DFS(j);
	}
}

meanwhile , Hash map It can also simulate Adjacency matrix The idea of building a map , by comparison , Can store the adjacency matrix can not store the sparse graph , Graphs with a large number of nodes can also be stored , The method is ;

unordered_map<int, unordered_map<int, int>>mp;

The mapping operation is mp[a][b]=c;  It can directly express a To b Distance of c;

Traversal operation and vector and pair The operation of the combined structure is similar to , Its advantage is that any two points can be taken directly ：a To b Distance of , By manipulating the mp[a].find(b) Realization . If the return value is true , It means that there is such an edge . The time complexity of finding edges can be reduced to O(1).