Apart from the well-known BFS and DFS algorithms, I find the following algorithms useful for Coding Interview.

##### Topology sort & circle check
• Given directed graph, sort the nodes in graph so that, if exist an edge (u->v), v comes after u in the sorted array.
• We cannot sort if there is at least 1 circle in the graph, (u->v->u), so we need to check whether there is at least 1 circle in the graph.
``````    vector<vector<int>> adj;
vector<bool> visited;
vector<bool> inDfs;
// the sorted order of node
vector<int> q;
int id = n;
bool ok;

void dfs(int u) {
visited[u] = true;
inDfs[u] = true;
for(int i = 0; i < adj[u].size(); i++) {
if (!visited[v]) {
dfs(v);
} else if (inDfs[v]) {
ok = false;
return;
}
}
q[id--] = u;
inDfs[u] = false;
}
``````

Runtime: O(n+m)
Practice:

##### Dijkstra

Finding the shortest distance between 2 nodes in non-negative weights graph

``````    int dijstra(vector<vector<int>>& edges, int N, int Source) {
vector<ii> a[N+1];
for(auto e: edges) {
int u = e, v = e, w = e;
a[u].push_back(ii(v, w));
}
priority_queue<ii, vector<ii>, greater<ii> > q;
int fx[N+1];
for(int i = 1; i <= N; i++) fx[i] = INT_MAX;
fx[Source] = 0;
q.push(ii(0, Source));

while (q.size()) {
int u = q.top().second;
q.pop();
for(auto pair: a[u]) {
int v = pair.first;
int w = pair.second;
if (fx[v] > fx[u] + w) {
fx[v] = fx[u] + w;
q.push(ii(fx[v], v));
}
}
}
}
``````

Runtime: O(n + m log n)
Practice: https://leetcode.com/problems/network-delay-time

##### 0-1 BFS

Finding the shortest distance between 2 nodes in weights graph, if the weight of each edge is either 0 or 1.

``````    deque<int> q;
q.push_front(s);
vector<int> fx(n, INT_MAX);
fx[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop_front();
int v = edge.first;
int w = edge.second;
if (fx[v] > fx[u] + w) {
fx[v] = fx[u] + w;
if (w == 0) {
q.push_front(v);
} else {
q.push_back(v);
}
}
}
}
``````

Runtime: O(n + m)
Practice: https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid

##### Euler circle finding
• An Eulerian cycle exists if and only if the degrees of all vertices are even
• An Eulerian path exists if and only if the number of vertices with odd degrees is two
``````    vector<int> circle;
unordered_set<int> g;

void dfs(int u) {
while (!g[u].empty()) {
int v = *g[u].begin();
g[u].erase(v);
g[v].erase(u);
dfs(v);
}

circle.push_back(u);
}
``````

Runtime: O(m)
Practice:

##### Kruskal - finding Minimum Spaning Tree
``````    int p;
int r;

int find(int i) {
if (i == p[i]) return i;
return (find(p[i]));
}

void merge(int i, int j) {
if (r[i] > r[j]) {
p[j] = i;
} else {
p[i] = j;
if (r[i] == r[j]) r[j]++;
}
}

int kruskal(int n, vector<vector<int>>& connections) {
vector<pair<int, pair<int, int>>> a;
for(auto e: connections) {
int w = e;
int u = e;
int v = e;
a.push_back(make_pair(w, make_pair(u, v)));
}
sort(a.begin(), a.end());
for(int i = 0; i < n; i++) {
p[i] = i;
r[i] = 0;
}

int res = 0;
int count = 0;
for(int i = 0; i < a.size(); i++) {
int u = a[i].second.first;
int v = a[i].second.second;
int uRoot = find(u);
int vRoot = find(v);
if (uRoot != vRoot) {
res += a[i].first;
count++;
merge(uRoot, vRoot);
}
}
return count == n-1 ? res : -1;
}
``````

Runtime: O(m log m)
Practice:

##### Bipartite Graph Check

Bipartite Graph is a special graph with the following characteristics: The set of vertices V can be partitioned into two disjoint sets V1 and V2 and all edges in (u,v) ∈ E has the property that u ∈ V1 and v ∈ V2.

``````    vector<bool> visit;
vector<bool> color;

bool dfs(int u, bool c) {
visit[u] = true;
color[u] = c;
for(int v: a[u]) {
if (!visit[v]) {
if (!dfs(v, !c)) return false;
} else {
if (color[u] == color[v]) return false;
}
}
return true;
}
``````

Runtime: O(n+m)
Practice: https://leetcode.com/problems/possible-bipartition/

##### Check if a node is in circle in graph

The idea is to colour node with 3 colors: 0, 1, 2.
If the node is not visited, its color is 0
If the node is in the process of visiting by DFS, its color is 1
If the node dfs process is completed, its color is 2.

``````    int color;
vector<vector<int>> g;
/*
0: white
1: grey
2: black
*/
bool dfs(int u) {
if (color[u] != 0) return color[u] == 2;

color[u] = 1;
for(int v: g[u]) {
if (color[v] != 2) {
if (color[v] == 1 || !dfs(v)) return false;
}
}
color[u] = 2;
return true;
}
``````

Runtime: O(n+m)
Practice: https://leetcode.com/problems/find-eventual-safe-states/