Introduction to graph theory -- drawing

background ：

I was too lazy to write anything I had learned before , However, it seems that the little apprentice has encountered a bottleneck in learning graph theory , Just write an article about .

Concept ：

First , We need to understand the definition of graph .
What is a graph? ？
A picture $G$ A binary consisting of two sets , Point set $V$ And side set $E$. namely $G=(V,E)$.

edge Is the connection point and the relationship between points , Divided into directed edge and undirected edge .
Undirected graph Is a graph that is all undirected .
Directed graph Is a graph composed of directed edges .
Among the specific topics , edge and spot It may be determined by the weight , That is to say Point right and Border right .

route Is a sequence of edges from one point to another .
Simple path A path that does not pass through a repeating edge .
Ring , Also called loop , It means that a point returns to itself through a simple path .

degree The number of edges connected by a point .
The degree of The number of edges connected by a point .
The degree of The number of edges connected by a point .

Heavy edge Are two edges with the same starting and ending points .
Self ring Connect yourself to your side , In theory, it is also called ring .
Because the existence of these two things is strange , Sometimes the title will specifically indicate that there is no double edge and self ring , If not, be careful .

There is also a kind of map commonly used in competitions Directed acyclic graph (Directed Acyclic Graph), seeing the name of a thing one thinks of its function , It's a directed graph without rings （ They are all directed edges , There is no undirected edge ）. Be commonly called DAG.

Another common kind of graph , Trees . Questions are too common , I won't introduce you here . A picture composed of several trees is called The forest , The name is very vivid .

also Bipartite graph , A graph is a bipartite graph. An important equivalent condition is that the graph has no odd rings .（ Odd ring ： A ring of odd numbers of points ）

There are also some high-level drawings that will give the title ： Chords , Base ring tree （ Base ring inward tree and base ring outward tree ）, cactus （ Round square tree ）.

Maybe there is ……

Drawing ：

Now that you know the picture , We need to learn how to build a diagram in code .

So what are the operations needed to build a diagram .
$1.$ Bordering ： We need to add an edge to the graph .
$2.$ Traverse the edges connected by a point .

The method of saving all edges with an array is not mentioned .
Here are three common methods of drawing construction .

One 、 Matrix storage

Is to use a two-dimensional array , The ranks represent points , The values in the matrix represent the edge weights .
So solve the above two problems , We're going to add an edge $(a,b)$, The boundary right is $w$, then $tu[a][b]=w$.（ The heavy side is not considered here ）
If it's an undirected edge , That's actually adding two directed edges ,$tu[a][b]=tu[b][a]=w$.

So another question , How to traverse a point $x$ Connected edge , In fact, No $x$ OK, sweep over .

int tu[maxn][maxn];// chart 

memset(tu,0,sizeof(tu));// Initialization diagram 

tu[a][b]=w;// Add one a To b The right of border is w The directed side of 

tu[a][b]=tu[a][b]=w;// Add one a To b The right of border is w The undirected edge of 

// Ergodic point x Connected edge 
for(int i=1;i<=n;i++)if(i!=x&&tu[x][i]!=0)
{
    
	printf(" spot x point-to-point %d, The boundary right is %d The edge of \n",i,tu[x][i]);
}

There are two defects in this way . One is the memory occupation $o(n^2)$, When the number of points is $10^5$ I can't drive it when I'm young . Second, the edge complexity of traversing a point connection is $o(n)$, But this point may not have enough edges $n$, It's a waste .
Of course, it's also good , For example, deleting and adding edges can o(1), You can also quickly find the edge between two points .

In order to meet the needs of the above two defects sometimes , There are the latter two ways of drawing .

Two 、vector Save map （ Adjacency table to store graph ）

The adjacency table storage map in the data structure class is to write the linked list honestly , Here we only introduce the commonly used .
Give me a general introduction Adjacency table to store graph , We build a node for each point $[a]$, When we want to add a directed edge (a,b) When , Just connect it to $[a]$ Behind .（ If it's an undirected edge , It would be $[a]$ and $[b]$ Followed by one , That is, add a directed edge (a,b) and (b,a)）

For example, join the directed edge $(a,b)$,$(a,c)$,$(a,d)$ after ,$[a]$ The situation is as follows .
$[a]->(b)->(c)->(d)$
$()$ The information inside represents the edge , If there is still edge power , It's like this .
$[a]->(b,wb)->(c,wc)->(d,wd)$
We put it in $vector$ Inside , Namely v [ a ] = { ( b , w b ) , ( c , w c ) , ( d , w d ) } v[a]=\{(b,wb),(c,wc),(d,wd)\} v[a]={ (b,wb),(c,wc),(d,wd)}.
Or don't want to write structures , You can also use two $vector$,
v [ a ] = { b , c , d } v[a]=\{b,c,d\} v[a]={ b,c,d}
g [ a ] = { w b , w c , w d } g[a]=\{wb,wc,wd\} g[a]={ wb,wc,wd}
One by one, the points correspond to the edge weight .

// The first way to write it , With the structure 

struct E
{
    
	int to,w;
};
vector<E>v[maxn];// chart 

for(int i=0;i<maxn;i++)v[i].clear();// Initialization diagram 

v[a].push_back(E{
    b,w});// Add one a To b The right of border is w The directed side of 

// Add one a To b The right of border is w The undirected edge of 
v[a].push_back(E{
    b,w});
v[b].push_back(E{
    a,w});

// Ergodic point x The edge of the company 
for(int i=0;i<v[x].size();i++)
{
    
	int to=v[x][i].to,w=v[x][i].w;
	printf(" spot x point-to-point %d, The boundary right is %d The edge of \n",to,w);
}

// The second way , No structure 

vector<int>v[maxn],g[maxn];// chart 

for(int i=0;i<maxn;i++)v[i].clear(),g[i].clear();// Initialization diagram 

v[a].push_back(b);// Add one a To b The right of border is w The directed side of 
g[a].push_back(w);

// Add one a To b The right of border is w The undirected edge of 
v[a].push_back(b);
g[a].push_back(w);
v[b].push_back(a);
g[b].push_back(w);

// Ergodic point x The edge of the company 
for(int i=0;i<v[x].size();i++)
{
    
	int to=v[x][i],w=g[x][i];
	printf(" spot x point-to-point %d, The boundary right is %d The edge of \n",to,w);
}

3、 ... and 、 Chain forward star

Save the map in the same way as before , It's all connected in the back .
But this is implemented with a linked list , When this is written, the linked list does not need pointers , Use subscript index to realize .
The specific understanding depends on the code .

struct 
{
    
	int to,w,next;
}edge[maxm];
int head[maxn],tot;// chart 
void init()// Initialization diagram 
{
    
	tot=0;
	memset(head,-1,sizeof(head));
}
void addedge(int a,int b,int w)// Add one a To b The boundary right is w The directed side of , Add one positive and one negative on the undirected side 
{
    
	edge[tot].to=b;
	edge[tot].w=w;
	edge[tot].next=head[a];
	head[a]=tot++;
}

// Ergodic point x The edge of the company 
for(int i=head[x];i!=-1;i=edge[i].next)
{
    
	int to=edge[i].to,w=edge[i].w;
	printf(" spot x point-to-point %d, The boundary right is %d The edge of \n",to,w);
}

Finished. .