Graphs.md

Graphs.md

A set of vertices and edges. It can be represented like an adjacent list.

	const int N = 5;
	vector<int> G[N];
	int vis[N];

DFS

void dfs(int a){
	vis[a] = 1;
	printf("V: %d\n", a);
	for(auto &e: G[a]) if(!vis[e]) dfs(e);
}

BFS

void bfs(int a){
	queue<int> q;
	q.push(a);
	while(!q.empty()){
		int r = q.front(); q.pop();
		vis[r] = 1;
		printf("V: %d\n", r);
		for(auto &e: G[r]) if(!vis[e]) q.push(e);
	}
}

Graph with weights, and vector of distances:

vector<pair<int,int> > G[N]; // Edge: i-G[i].0, Weight: G[i].1
int dist[N]; for(auto &e: dist) e = INF;

DIJKSTRA

void djk(int a){
	d[a] = 0;
	priority_queue<pair<ll, int> > pq; // [distance, vertice]
	pq.emplace(0, a);
	while(pq.size()){
		pair<ll, int> ndist = pq.top().first, u = pq.top().second;
		pq.pop();
		if(-ndist > d[u]) continue;
		for(pair<ll,int> idx_u:g[u]){
			d[idx_u.first] = d[u] + idx_u.second;
			pq.emplace(-d[idx_u.first], idx_u.first);
		}
	}
} // O(m log(n))

bellmanford kosaraju kruskal eulerPath EulerTour floydwarshall

vector<pair<ll,int>> dist[N]; // dist = G
void fw(){
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) dist[i].first = ((i==j)?0:INF);
	for(int k=0;k<n;++k) for(int i=0;i<n;++i) for(int j=0;j<n;++j) min(dist[i][j], G[i][k]+G[k][j]); 
}

tarjan * toposort *