Recognition and storage of Graphs

The understanding of graph

form

The graph is mainly composed of a two tuple G=<V,E>,V Represents a node set ,E Represents an edge set ,w Represents the weight on an edge （ Define your own ）

Direction

Graph Division Directed graph and undirected graph

Directed graph

All edge sets have directions , such as A->B,A You can go to B, however B Not to A;

Undirected graph

All edge sets have no direction , such as A<–>B,A You can go to B And B You can go to A.

Degrees

Undirected graph

The degree of a point in an undirected graph refers to the number of edges connected by this point , Undirected graph degree = The degree of

Directed graph

The degree of digraph is not necessarily equal to the degree

Figure of the storage

Points are very easy to store , But it's not easy to save , But we can turn the edge into two points .

Adjacency matrix

Storage principle

Adjacency matrix uses a two-dimensional array to store the edges of the graph ;
a [ i ] [ j ] Representation node i To the node j There is one side , A weight of a[ i ] [ j ]

The code template

// Undirected graph 
// Definition 
const int maxn=1e3+10;
int a[maxn][maxn];

//...
// Bordering 
for(int i=1;i<=m;i++){
    
	int u,v;
	scanf("%d%d",u,v);
	a[u][v]=1;
	a[v][u]=1;// According to the title requirements , Directed graph without this line of code 
}

Adjacency list

Storage principle

Adjacency table can be based on the requirements of the opposite side , Open space , Like a queue ;

The code template

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e3+10;
int n,m;
// Definition 
vector< pair<int,int> >e[maxn];
int main(){
    
	scanf("%d%d",&n,&m);
	// Bordering 
	for(int i=1;i<=m;i++){
    
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back(make_pair(v,w));
		e[v].push_back(make_pair(u,w));// According to the title requirements , Directed graph without this line of code 
	}
	// Call operation 
	for(int i=1;i<=n;i++){
    
		for(int j=0;j<e[i].size();j++){
    
			//…… 
		}
	}
	return 0;
}

Chain forward star

Storage principle

The edge that will be related to a point , Store in a linked list

The code template

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e3+10;
int n,m,tot;
// Definition 
int head[maxn];
struct node {
    
	int v,w,nxt;
}e[maxn];
void add(int u,int v,int w){
    
	e[++tot].v=v;// Update the number of edges and record the new edge arc head 
	e[tot].w=w;// Record weights 
	e[tot].nxt=head[u];// Insert the list 
	head[u]=tot;// Update pointer 
}
int main(){
    
	scanf("%d%d",&n,&m);
	// Bordering 
	for(int i=1;i<=m;i++){
    
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	return 0;
} 

Storage summary of graphs

1. Adjacency matrix
   Spatial complexity O(n^2)
   Time complexity of edge checking O(1)

2. Adjacency list
   Spatial complexity O(n)
   Time complexity of edge checking O(n)
   Space is unstable
   ps: Adjacency table space will generally double for you

3. Chain forward star
   Spatial complexity O(n）
   Edge checking complexity O(n)
   Spatial stability