Graph
Graph Representing
https://www.geeksforgeeks.org/graph-and-its-representations/
Adjacent Matrix
Adjacent List
Edges
Traversal
BFS
DFS
Pacific Atlantic Water Flow
- start from matrix
- start from occean
Clone Graph follow up: reverse if DAG
Evaluate Division
class Solution {
public:
double dfs(string cur, const string & dest, unordered_set<string> visited, unordered_map<string, unordered_map<string, double>> & edges) {
if (!edges.count(cur)) {
return -1.0;
}
if (cur == dest) {
return 1.0;
}
double temp = -1.0;
for (auto e : edges[cur]) {
string next = e.first;
if (visited.count(next)) continue;
visited.emplace(next);
double v = dfs(next, dest, visited, edges);
if (v != -1.0) {
temp = edges[cur][next] * v;
}
}
return temp;
}
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
int n = equations.size();
unordered_map<string, unordered_map<string, double>> edges; //edges[src][dst] = value
//build graph
for (int i = 0; i < n; i++) {
edges[equations[i].first][equations[i].second] = values[i];
edges[equations[i].second][equations[i].first] = 1.0 / values[i];
}
vector<double> res;
for (const auto & q : queries) {
unordered_set<string> visited = {q.first};
res.emplace_back(dfs(q.first, q.second, visited, edges));
}
return res;
}
};
Topological Sorting
DFS method
拓扑排序的常规方法是用DFS。DFS 有一个好处就是可以 backtracking 到所有的 solution。
https://www.geeksforgeeks.org/topological-sorting/
BFS
另一个方法 Kahn’s algorithm 用记录入度/出度的方式进行BFS, 相对容易记忆和实现
https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
More questions
用两个个hashmap记录所有的入度和出度。
用一个zeroInDegree的队列做BFS,没有入度意味着起点
在BFS过程中,不断的删除孩子的入度,然后把父亲节点从出度中删掉,这样就把这个点和所有和他连接的孩子的边都删掉了。
最后判断如果出度中还有点,说明还有边存在着。
// 0 -> 1, 0 -> 2, 1 -> 3, 2 - >3
// ->1\
// 3
// ->2/
class Solution {
public:
// pres[i].first <- pres[i].second
vector<int> findOrder(int n, vector<pair<int, int>>& pres) {
queue<int> zeroInDegree;
unordered_map<int, unordered_set<int>> inDegree;
unordered_map<int, unordered_set<int>> outDegree;
for (int i = 0; i < pres.size(); i++) {
inDegree[pres[i].first].emplace(pres[i].second);
outDegree[pres[i].second].emplace(pres[i].first);
}
for (int i = 0; i < n; i++) {
if (inDegree.count(i) == 0) {
zeroInDegree.push(i);
}
}
vector<int> order;
while (!zeroInDegree.empty()) {
int parent = zeroInDegree.front();
zeroInDegree.pop();
order.emplace_back(parent);
for (auto child : outDegree[parent]) {
if (inDegree[child].count(parent)) {
inDegree[child].erase(parent);
}
if (inDegree[child].empty()) {
inDegree.erase(child);
zeroInDegree.push(child);
}
}
outDegree.erase(parent);
}
if (!outDegree.empty()) {
return {};
}
return order;
}
};
Longest Increasing Path in a Matrix
class Solution {
public:
string alienOrder(vector<string>& words) {
queue<char> zeroInDegree;
unordered_map<char, unordered_set<char>> inDegree;
unordered_map<char, unordered_set<char>> outDegree;
unordered_set<char> nodes;
for(int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
nodes.emplace(words[i][j]);
}
}
//build graph
for (int i = 1; i < words.size(); i++) {
string curr = words[i];
string prev = words[i - 1];
int j = 0;
while (j < min(curr.size(), prev.size()) && curr[j] == prev[j]) {
j++;
}
if (j < min(curr.size(), prev.size())) {
inDegree[curr[j]].emplace(prev[j]);
outDegree[prev[j]].emplace(curr[j]);
}
}
//find entries for the graph
for (auto c : nodes) {
if (!inDegree.count(c)) {
zeroInDegree.push(c);
}
}
string order;
while (!zeroInDegree.empty()) {
char parent = zeroInDegree.front();
zeroInDegree.pop();
order.push_back(parent);
for (auto child : outDegree[parent]) {
inDegree[child].erase(parent);
if (inDegree[child].empty()) {
zeroInDegree.push(child);
}
}
outDegree.erase(parent);
}
if (!outDegree.empty()) {
return {};
}
return order;
}
};
All Topological sorts of a DAG | should use DFS
void Graph::dfs(vector<int> & order, vector<bool> & visited) {
bool flag = false;
for (int i = 0; i < V; i++) {
if (indegree[i] != 0 || visited[i]) continue;
for (auto iter = adj[i].begin(); auto != adj[i].end(); j++) {
indegree[*iter]--;
}
order.emplace_back(i);
visited[i] = true;
dfs(order, visited);
for (auto iter = adj[i].begin(); auto != adj[i].end(); j++) {
indegree[*iter]++;
}
visited[i] = false;
order.pop_back();
flag = true;
}
if ()
}
Connected Component
Connected components for undirected graph
Number of Connected Components
Strongly Connected Components
https://www.geeksforgeeks.org/strongly-connected-components/
https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/
https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/
Shortest Path
Maze I
bool hasPath(vector<vector<int>> & maze, vector<int> & start, vector<int> & dest) {
const vector<int> dx = {0, -1, 1, 0};
const vector<int> dy = {1, 0, 0, -1};
queue<pair<int, int>> q;
q.emplace(start[0], start[1]);
maze[start[0]][start[1]] = 2;
int m = maze.size();
int n = maze.front().size();
while (!q.empty()) {
auto cur = q.front();
q.pop();
int x = cur.first;
int y = cur.second;
if (x == dest[0] && y == dest[1]) {
return true;
}
for (int i = 0; i < 4; i++) {
int xx = x;
int yy = y;
while (xx >= 0 && xx < m && yy >= 0 && yy < n && maze[xx][yy] != 1) {
xx += dx[i];
yy += dy[i];
}
xx -= dx[i];
yy -= dy[i];
if (maze[xx][yy] == 0) {
maze[xx][yy] = 2;
q.emplace(xx, yy);
}
}
}
return false;
}
Maze II
struct Position {
int x, y, d;
Position(int x, int y, int d): x(x), y(y), d(d) {}
};
class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& dest) {
if (maze.empty()) {
return -1;
}
auto cmp = [](Position & p1, Position & p2) {return p1.d > p2.d;};
priority_queue<Position, vector<Position>, decltype(cmp)> pq(cmp);
pq.emplace(Position(start[0], start[1], 0));
int m = maze.size();
int n = maze.front().size();
vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
const vector<int> dx = {0, 1, -1, 0};
const vector<int> dy = {1, 0, 0, -1};
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int x = p.x;
int y = p.y;
int d = p.d;
if (x == dest[0] && y == dest[1]) {
return d;
}
dis[x][y] = d;
for (int i = 0; i < 4; i++) {
int nx = x;
int ny = y;
int nd = d;
while (nx + dx[i] < m && nx + dx[i] >= 0 && ny + dy[i] < n && ny + dy[i] >= 0
&& maze[nx + dx[i]][ny + dy[i]] == 0) {
nx += dx[i];
ny += dy[i];
nd++;
}
if (dis[nx][ny] > nd) {
dis[nx][ny] = nd;
pq.emplace(Position(nx, ny, nd));
}
}
}
return -1;
}
};
Maze III
struct State
{
int x;
int y;
int d;
State (int x, int y, int d) : x(x), y(y), d(d) {}
};
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, -1, 1};
const string dirs = "dulr";
class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
auto cmp = [](State & s1, State & s2) {
return s1.d > s2.d;
};
priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);
pq.emplace(ball[0], ball[1], 0);
int m = maze.size();
int n = maze.front().size();
//dis[x][y]=>maintain the shortest distance to the source so far
vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
//dir[x][y]=>maintain the lexicographically smallest way from the source so far
vector<vector<string>> way(m, vector<string>(n));
while(!pq.empty()) {
auto state = pq.top();
pq.pop();
int x = state.x;
int y = state.y;
int d = state.d;
if (d > dis[x][y]) {
continue;
}
string path = way[x][y];
dis[x][y] = d;
if (x == hole[0] && y == hole[1]) {
return way[x][y];
}
for (int i = 0; i < 4; i++) {
int nx = x;
int ny = y;
int nd = d;
string path = way[x][y] + dirs[i];
while (nx + dx[i] < m && nx + dx[i] >= 0 && ny + dy[i] < n && ny + dy[i] >= 0
&& maze[nx + dx[i]][ny + dy[i]] == 0) {
nx += dx[i];
ny += dy[i];
nd++;
if (nx == hole[0] && ny == hole[1]) {
break;
}
}
if (nd < dis[nx][ny]) {
dis[nx][ny] = nd;
way[nx][ny] = path;
pq.emplace(nx, ny, nd);
}
if (nd == dis[nx][ny]) {
if (path < way[nx][ny]) {
way[nx][ny] = path;
}
}
}
}
return "impossible";
}
};
Leetcode 317: Shortest Distance from All Buildings
找到一个点,从他开始到所有的buildings的距离最短的和,中间有障碍物。对每个点做BFS,然后加起来求一个最小值。这样的时间复杂度是 $O(m*n)[BFS] * O(m*n)[matrix] = O(m^2*n^2)$。优化:从building开始搜。那么时间复杂度为$O(k*m*n)$。 $k$ 是 building 的个数。
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int res = INT_MAX;
vector<vector<pair<int, int>>> dis(grid.size(), vector<pair<int, int>>(grid[0].size()));
//dis[i][j].first => total distance from k buildings to grid[i][j]
//dis[i][j].second => num of times search from k buildings and visited to grid[i][j] successfully (avoid dead end)
int m = grid.size();
int n = grid[0].size();
int num_buildings = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
bfs(grid, dis, i, j);
num_buildings++;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dis[i][j].second == num_buildings) {
res = min(res, dis[i][j].first);
}
}
}
return res == INT_MAX? -1 : res;
}
void bfs(const vector<vector<int>> & grid, vector<vector<pair<int, int>>> & dis, int i, int j) {
queue<pair<int, int>> q;
q.emplace(i, j);
int m = grid.size();
int n = grid[0].size();
deque<deque<bool>> visited(m, deque<bool>(n, false));
vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int level = 0; //distance to building in grid[i][j]
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (level != 0) {
dis[x][y].first += level;
dis[x][y].second++;
}
for (const auto & dir : dirs) {
int x_prime = x + dir.first;
int y_prime = y + dir.second;
if (x_prime < m && x_prime >= 0 && y_prime < n && y_prime >= 0 &&
grid[x_prime][y_prime] == 0 &&
visited[x_prime][y_prime] == false) {
q.emplace(x_prime, y_prime);
visited[x_prime][y_prime] = true;
}
}
}
level++;
}
}
};
Best Meeting Point
和上题一样的做法,只是可以在人所在的位置。做 BFS 标记 visited 的时候要注意。
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int res = INT_MAX;
vector<vector<int>> dis(grid.size(), vector<int>(grid[0].size()));
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
bfs(grid, dis, i, j);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = min(res, dis[i][j]);
}
}
return res == INT_MAX? -1 : res;
}
void bfs(const vector<vector<int>> & grid, vector<vector<int>> & dis, int i, int j) {
queue<pair<int, int>> q;
q.emplace(i, j);
int m = grid.size();
int n = grid[0].size();
deque<deque<bool>> visited(m, deque<bool>(n, false));
visited[i][j] = true;
vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int level = 0; //distance to grid[i][j]
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (level != 0) {
dis[x][y] += level;
}
for (const auto & dir : dirs) {
int x_prime = x + dir.first;
int y_prime = y + dir.second;
if (x_prime < m && x_prime >= 0 && y_prime < n && y_prime >= 0 &&
visited[x_prime][y_prime] == false) {
q.emplace(x_prime, y_prime);
visited[x_prime][y_prime] = true;
}
}
}
level++;
}
}
};
但超时啦。 答案里给的方法是算出median。并不适用有obstacle的情况(是嘛?)。
// Time: O(mn)
// Space: O(m+n)
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> x, y;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j]) {
x.emplace_back(i);
y.emplace_back(j);
}
}
}
nth_element(x.begin(), x.begin() + x.size() / 2, x.end());
nth_element(y.begin(), y.begin() + y.size() / 2, y.end());
const int mid_x = x[x.size() / 2];
const int mid_y = y[y.size() / 2];
int sum = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j]) {
sum += abs(mid_x - i) + abs(mid_y - j);
}
}
}
return sum;
}
};
- nth_element() 把按 comparator 排序的有第n个数放在 n 的位置,前面的都比它“小”, 后面的都比它“大”。 但其他并不保证有序,时间复杂度 $O(n)$ 比 sort 好一些。
Dijkstra
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/
https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
A star
https://github.com/pineal/-O_O-/blob/master/A_Star_Search/A_Star_Search.cpp