Introduction to graph theory
Establishment and storage of Graphs
Adjacency table
vector implements adjacency table
Adjacency table is an edge oriented data structure, so the content of the edge needs to be stored in a structure **
About vector
1,establish vector object vector<int> vec; 2,insert vec.insert(); 3,delete vec.erase(); 4,Tail insertion vec.push_back(); 5,empty vec.clear();
vector mapping
struct Edge{
int from;//Vertex sequence number
int to;//Vertex sequence number
int w;//Weight (side length)
//overloaded constructor
Edge(int f=0,int t=0, int _w=0):from(f),to(t),w(_w){}
//Overloaded comparison operator
bool operator < (const Edge &e) const{return w<e.w;}
};
vector <Edge> edge[N];//G[i] represents the edge starting from I, and there are edges in the vector
int n,m;
vector <int> G[N];
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++){
int uu,vv;
cin>>uu>>vv;
G[uu].push_back(vv);//Mapping
//G[u][i] represents the edge of u-i
}
}
Chain forward star construction map
const int N=100000;
struct node{
int v;//End
int w;//Weight
int next;//Label of the next edge
}edge[N];
int n,m;
int cnt=0;
int head[N];
//Head [i] stores the number of the last edge starting from I, because the head insertion method is used
void add(int u,int v,int w){
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int main(){
cin>>n>>m;
memset(head,-1,sizeof(head));
int u,v,w;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
/*
Add two-way edge
add(u,v,w);
add(v,u,w);
*/
}
//Ergodic function
for(int i = 1; i <= n; i++)//n starting points
{
cout << i << endl;
for(int j = head[i]; j != -1; j = edge[j].next)//Traverse the edge starting with i, starting from its last side
{
cout << i << " " << edge[j].v << " " << edge[j].w << endl;
}
cout << endl;
}
/*Operation content
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
result:
1 //A collection of edges starting from 1
1 5 6
1 3 4
1 2 1
2 //A collection of edges starting from 2
2 3 2
3 //A collection of edges starting from 3
3 4 3
4 //A collection of edges starting at 4
4 5 7
4 1 5
5 //The edge starting from 5 does not exist
*/
}
Explain next, head
For 1 2 1 edge: edge[0].to = 2; edge[0].next = -1; head[1] = 0; For 2 3 2 this edge: edge[1].to = 3; edge[1].next = -1; head[2] = 1; For the 3 4 3 edge: edge[2].to = 4; edge[2],next = -1; head[3] = 2; For 1 3 4 this edge: edge[3].to = 3; edge[3].next = 0; head[1] = 3; For the 4 1 5 edge: edge[4].to = 1; edge[4].next = -1; head[4] = 4; For the 1 5 6 edge: edge[5].to = 5; edge[5].next = 3; head[1] = 5; For the 4 5 7 edge: edge[6].to = 5; edge[6].next = 4; head[4] = 6;
adjacency matrix
Drawing with two-dimensional array
#include <bits/stdc++.h>
using namespace std;
using namespace std;
const int N=101;
const int INF=1e9+7;//Represents the maximum value of infinity
int g[N][N];
int w;//Weight
int main()
{
int n,m;//Row / column of graph
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i!=j)
g[i][j]=INF;//Initialization, for a graph without weight, g[i][j]=0 indicates that there is no edge connectivity.
//g[i][j]=0; The array defined in the global area is automatically initialized to 0 and can not be written
int e;//Number of sides
cin>>e;
for(int i=1;i<=e;i++){
int u,v,w;
cin>>u>>v>>w;//Start and end points and weights of edges
g[u][v]=w;//For a graph without weight, G [i] [J] = 1
/*
In order to satisfy the symmetry of undirected graphs, directed graphs do not need
g[j][i]=w;
*/
}
//Traversal output
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout<<g[i][j]<<"\t";
cout<<endl;
}
}
Traversal of Graphs
DFS
- Access tags avoid repetition and time stamp (dfn) to judge connectivity
- Judgment negative ring
Implementation of dfs with chained forward star
int vis[N];
memset(vis,0,sizeof(vis));
void dfs(int u,int v){
if(vis[u])
return;
vis[u] = true;
for(int i = head[u]; i!=-1; i=edge[i].nxt){
if(!vis[edge[i].to)
{
vis[edge[i].to]=true;
dfs(edge[i].to,v);
vis[edge[i].to]=false;
}
}
}
Implementing dfs with adjacency matrix
const int N=101;
int g[N][N];
int vis[N];//Global variables are directly initialized to 0 by default
void dfs(int u){
vis[u]=true;//Mark u access
cout<<u<<" ";
for(int i=1;i<=n;i++){
if(!vis[i] && g[u][i])//If there is a corresponding edge and the end of the edge is not accessed
dfs(i);
}
}
int main()
{
int n,m;//Number of vertices and edges
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>u>>v;
g[u][v]=1;//Mark that the edge exists
}
for(int i=1;i<=n;i++)
if(!vis[i])
dfs(i);
}
BFS (shortest path)
- Shortest path with edge weight of 1
- Establish hierarchical map
- The complexity is O(m), the difference is that the order of accessing vertices is different
Adjacency table implementation bfs
void bfs(){ q.push(1); vis[1]=true; while(!q.empty()){ int u = q.front(); q.pop(); cout<<u<<" "; //Access for (int i = 0; I < G [u]. Size(); I + +) {if (! Vis [g [u] [i]]) / / if {q.push (G [u] [i]); VIS [g [u] [i]] = true;}}}}
Topology sorting and DAG
Equivalent condition for topological sorting of graphs = = graphs are directed acyclic graphs (called DAG, hastu), which are naturally suitable for DP
When the topological order is unique, hastu satisfies the total order relation, that is, the line order relation.
Implementation of topology sorting
All maps are built by chain forward star
Kahn algorithm implemented with BFS
- Take out the point whose penetration is 0, and reduce the penetration of its adjacent node by one. Repeat this process until all points are taken out.
- Access all adjacent nodes (the same way as BFS, so just change the board of BFS slightly).
const int N=100000;struct node{ int v;//End point int next// Label of the next edge}edge[N];int in_degree[N];// Penetration degree int head [n]// Head [i] stores the number of the last edge starting from I, because the head interpolation queue < int > q is used// Queue q is used to save vertex vector < int > ans with penetration of 0// Save result int n, m; int cnt=0; void add(int u,int v){ edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++;} Bool kahn() {int count = 0; / / count while (! Q.empty()) {int TP = q.front(); / / take the point q.pop(); + + count; ans.push_back (TP); / / add the point to the result set for (int i = head [TP]; I! = - 1; I = edge [i]. Next) {-- in_degree [edge [i]. V]; / / subtract the degree of the end point if (! In_degree [edge[i]. v] ) {q.push (edge [i]. V); / / 0 after subtraction, then add the point to the queue}}} if (count = = n) return 1; return 0;// If there is a ring, there is no topological sorting} int main() {CIN > > n > > m; / / initialize while (! Q.empty()) q.pop(); memset (in_degree, 0, sizeof (in_degree)); memset (head, - 1, sizeof (head)); / / add edge int u, V; for (int i = 1; I < = m; I + +) {CIN > > U > > V; add (U, V); + + in_degree [v];} For (int i = 1; I < = n; I + +) if (! In_degree [i]) / / press all points with 0 into the queue q.push (I); kahn(); for(int i=0;i<n;i++) cout<<ans[i]<<endl; return 0;}
Topological order with minimum output dictionary order
Just change the queue in BFS into a priority queue.
priority_queue<int,vector<int>,greater<int> > q;//Minimum first out
Implemented with DFS
- After traversing graph G with DFS, we will find that the process of DFS traversal is the process of topology sorting - DFS is that we traverse deeply at a node u, and the deeper the node, the lower the priority.
- It should be noted that the output topological order at this time is the reverse topological order. There are many processing methods at this time. You can put the topological order on the stack and output it, or turn the whole graph back at the beginning.
#include <bits/stdc++. h>using namespace std; using namespace std; const int N=500005; Struct node {int V; / / end point int next; / / label of the next edge} edge [n]; int vis[N]; int head[N];// Head [i] stores the number of the last edge starting from I, because the head interpolation queue < int > q is used// Queue q is used to save vertex vector < int > ans with penetration of 0; int n,m; int cnt=0;// Because it stores edges with a single linked list, when the DFS function is about to exit, add the end point to the ANS set void DFS (int cur) {vis [cur] = 1; / / int k = head [cur]; for (int i = head [cur]; I! = - 1; I = edge [i]. Next) {if (! Vis [edge [i]. V]) DFS (edge [i]. V);} ans.push_ back(cur);} Int main() {CIN > > n > > m; / / initialize while (! Q.empty()) q.pop(); memset (VIS, 0, sizeof (VIS)); memset (head, - 1, sizeof (head)); / / edge int u, V; for (int i = 1; I < = m; I + +) {CIN > > U > > V; edge [CNT]. V = V; edge [CNT]. Next = head [u]; head [u] = cnt + +;} for(int i=1;i<=n;i++){ if(!vis[i]) dfs(i); } for(int i=n-1;i>=0;i--) cout<<ans[i]<<endl; return 0;}
Disjoint Set
Joint search set -- special analysis of algorithm competition
Classic application
- Connected subgraph
- Minimum spanning tree Kruskal algorithm
Initialization and merging of parallel query sets
Example: there are n people eating together. Some people know each other. People you know want to sit together rather than with strangers. For example, if A knows B and B knows C, then A, B and C will sit at the same table.
give someone you know and ask how many tables you need.
//A table is a set, merge friends #include < bits / STDC + + h>using namespace std; const int N=1050; int s[N]; void init_ Set() / / initialize {for (int i = 1; I < = n; I + +) s[i] = I; / / I is the element; s[i] is the set} int find_set(int x) / / find {return x==s[x]?x:find_set(s[x]);}void merge_set(int x,int y) / / merge {x = find_set (x); y = find_set (y); if (x! = y) s [x] = s [y]; / / merge x into y, and the root of Y becomes the root of X} int main() {int t, N, m, x, y; CIN > > t; while (T --) {CIN > > n > > m; init_set(); for (int i = 1; I < = m; I + +) {CIN > > x > > y; merge_set (x, y);} int ans = 0; For (int i = 1; I < = n; I + +) / / count the number of sets if (s[i] = = I) ans + +; cout << ans <<endl; } return 0;}
Path compression -- Query Optimization
Recursive compression optimization
int find_set(int x){ if(x != s[x]) s[x] = find_set(s[x]); return s[x];}
Non recursive compression optimization
int find_set(int x)//Find {int r = x; while (s [R]! = R) r = s [R]; / / find the root node int i = x, j; while (I! = R) {j = s [i]; / / temporary variable j record s[i] = r; / / change the set of elements on the path to the root node / / s [i] = s [R]; I = j;} return x;}