On the adjacency matrix and adjacency table of graph storage

Adjacency matrix a matrix that represents the relationship between vertices , The storage method is ： A two-dimensional array stores the adjacency relationship between vertices in the graph .

In an undirected graph , If there is a connection between two nodes , So we initialize map[i][j]=map[j][i]=1, If not connected, set it to 0.

Give me a picture ：

 

According to the above initialization method, the representation of its adjacency matrix ：

                             

If it's a weighted graph , Then give him a weight , Generally, nodes that are not connected are assigned INF(0x3f3f3f3f)

Storage advantages of adjacency matrix ： Quickly determine whether there is a connection between the two nodes , Quickly calculate the degree between nodes . Adjacency matrix is the simplest and most common storage method in my opinion

-------------------------------------------------------------- Next, let's look at the adjacency table ----------------------------------------

Adjacency list is a chain storage method of graph , It contains two parts, vertex and adjacency . The vertices Contains vertex information and a pointer to the first adjacent node . Adjacency point Contains its own subscript and pointer to the next adjacent node .

Their structure is as follows ：

 

  Ideas ： We regard each node as the head node , The nodes it points to build a single linked list in reverse order .

Code ：

struct node
{
	int v;// Adjacency subscript 
	node* next;// Point to the next adjacent point 
}
node* head[maxn];
void adde(int u, int v)// Insert an edge , Refer to the reverse linked list creation process 
{
	node* s = new node;
	s->v = v;
	s->next = head[u];
	head[u] = s;
}
void creat()
{
	char x, y;
	int i, u, v;
	cin >> n >> m;
	for (i = 0; i < m; i++)
	{
		cin >> x >> y;
		u = x - 'a';
		v = y - 'a';// Convert character numbers to numeric numbers 
		adde(u, v);
	}
}