Graph
Breath First Search(BFS) for a Graph
트리에서의 Breath First Traversal과 비슷하지만 그래프에는 사이클이 있을 수 있다.
따라서 중복된 방문을 피하기 위해 visited라는 boolean array를 이용한다.
탐색해야 할 노드들이 저장된 큐를 만들고, 큐에 넣을 때마다 그 들어간 노드의 visited를 true로 한다.
그다음 큐가 빌 때까지 맨 앞의 노드를 뽑아내서 그 인접한 노드들을 탐색하며 !visited인 노드들을 큐에 넣으면서 visited = true로 바꾼다.
Depth First Search(DFS) for a Graph
마찬가지로 visited array가 필요하다.
Recursive하게 돌면서 visited array를 계속 넘겨준다.
하나의 recursion에서는 노드와 visited array를 받는데 그 노드를 visited로 바꾸고 그 인접 노드들 중에 unvisited가 있으면 그 노드에 대해 recursion함수를 부른다.
Shortest Path from Source to All Vertices: Dijkstra
Prim's algorithm for minimum spanning tree와 비슷하다.
한 set을 만든다. 최단 셋을 의미한다.
각 vertex마다 distance를 정의하고 출발점은 0, 나머지는 무한대로 설정한다.
set에 없으면서 가장 작은 distance를 갖고 있는 vertex u를 찾은 뒤 set에 넣는다.
그 u의 모든 인접 vertex의 distance를 업데이트한다. u의 distance와 그 사이 edge의 distance를 합한 것을 인접 vertex가 갖고 있던 기존의 distance와 비교해서 작은 값으로 바꾼다.
이 과정을 set가 모든 vertex를 포함하기 전까지 반복한다.
Negative edge가 있을 때는 Bellman-Ford algorithm이다.
Shortest Path from Every Vertex to Every Other Vertex: Floyd Warshall
처음에 n by n matrix를 만들어서 대각 성분은 모두 예외값으로 넣고 다른 성분들은 i->j로 가는 weight를 넣는다. edge가 없으면 무한대를 넣는다.
그다음 1부터 n까지, i번째 행과 열을 기준으로 작업을 한다.
n번의 작업이 끝나면 각 성분이 의미하는 게 i부터 j로 가는 최소 weight이다.
Time Complexity: O(V^3)
https://www.youtube.com/watch?v=t3mf2Vu9wA4
To Detect Cycle in a Graph: Union Find
Disjoint-set data structure(서로소 집합 자료구조)에서 사용된다.
Find: 그 원소가 어느 subset에 포함돼있는지를 알려준다. 이를 통해 어떤 두 원소가 같은 subset에 있는 지 알 수 있다.
Union: 두 subset을 하나의 subset으로 합친다.
Union-Find 알고리즘을 어떤 방향성 없는 그래프가 사이클을 갖는 지 확인하는 데에 적용할 수 있는데 이때 self loop이 없다는 가정이다.
각 edge마다 양쪽의 vertex정보가 들어간 subset을 만든다. 만약 같은 subset에 들어가는 게 있다면 사이클이 있는 것이다.
union()과 find()에 대한 naive time complexity는 O(n)인데 Union by Rank를 쓴다면 O(log n)까지 줄일 수 있다.
Minimum Spanning Tree: Prim
Greedy 알고리즘이다.
Spanning tree란 connected and undirected graph에서 모든 vertex가 연결된 subgraph이다.
이 spanning tree중 edge weight sum이 가장 작은 것이 minimum spanning tree이다.
두개의 set가 필요한데 set1은 이미 MST에 포함된 vertex를 저장하고 다른 set2는 아직 포함되지 않는 vertex를 저장한다.
이 두 set 사이의 모든 edge중 가장 작은 edge를 찾은 뒤 연결된 set2의 vertex를 set1에 포함시킨다.
먼저 시작점의 distance를 0으로 하고 나머지는 무한대로 초기 설정한다.
set1에 포함되지 않았으면서 가장 작은 distance를 갖고 있는 vertex u를 찾아서 set1에 포함시킨다.
u와 인접한 모든 vertex의 distance를 업데이트한다.
이 과정을 set1이 모든 vertex를 포함할 때까지 반복한다.
Minimum Spanning Tree: Kruskal
모든 edge를 non-decreasing 순서로 정렬한다.
가장 작은 edge를 고른 뒤 지금까지 만들어진 spanning tree에 cycle을 만드는 edge인 지 체크하고 만들지 않는다며 이 edge를 고른다. cycle을 만들면 버린다.
(V-1)개의 edge를 찾을 때까지 반복한다.
Topological Sort
DAG(Directed Acyclic Graph)에서 적용된다.
DFS는 어떤 vertex에서 그 인접 vertex에 대해 recursive하게 돌지만, topological sort는 인접 vertex를 돌리기 전에 자신을 먼저 print해야 한다.
스택을 이용해서 구현할 수 있다.
DFS처럼 가장 깊숙이 들어가서 스택에 넣고 나오면서 스택에 넣는다.
그러면 다 끝났을 때 스택의 맨 위에는 제일 처음의 시작점이 올라와있게 된다.
Time Complexity: O(V+E) same as DFS
Boggle(Find All Possible Words in a Board of Characters)
Matrix의 각 셀에는 문자 하나씩 있고 찾고자 하는 단어가 있다. 이때 같은 셀은 다시 방문하지 않으면서 찾고자 하는 단어를 만들 수 있는 지 체크하는 문제이다.
모든 문자에 대해 시작점으로 해서 depth first traversal으로 탐색한다.
Bridges in a Graph
bridge: undirected connected graph에서 어떤 edge를 없앴을 때 disconnected graph가 될 때 그 edge를 bridge라고 한다.
disconnected undirected graph에서도 어떤 edge를 없앴을 때 disconnected component의 수가 늘어날 때 그 edge를 bridge라고 한다.
Simple approach: 각 edge에 대해 하나 하나 다 없애보면서 connectedness를 따진다. O(E*(V+E))
O(V+E) approach: DFS traversal을 하는데 어떤 edge (u, v)에 대해 v rooted subtree에서 u나 u의 ancestor에 도달할 수 있는 다른 방법이 없을 때 그 edge는 bridge이다.
//동영상 참고하자.
--------------------------------------------
Reference
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/
트리에서의 Breath First Traversal과 비슷하지만 그래프에는 사이클이 있을 수 있다.
따라서 중복된 방문을 피하기 위해 visited라는 boolean array를 이용한다.
탐색해야 할 노드들이 저장된 큐를 만들고, 큐에 넣을 때마다 그 들어간 노드의 visited를 true로 한다.
그다음 큐가 빌 때까지 맨 앞의 노드를 뽑아내서 그 인접한 노드들을 탐색하며 !visited인 노드들을 큐에 넣으면서 visited = true로 바꾼다.
Depth First Search(DFS) for a Graph
마찬가지로 visited array가 필요하다.
Recursive하게 돌면서 visited array를 계속 넘겨준다.
하나의 recursion에서는 노드와 visited array를 받는데 그 노드를 visited로 바꾸고 그 인접 노드들 중에 unvisited가 있으면 그 노드에 대해 recursion함수를 부른다.
Shortest Path from Source to All Vertices: Dijkstra
Prim's algorithm for minimum spanning tree와 비슷하다.
한 set을 만든다. 최단 셋을 의미한다.
각 vertex마다 distance를 정의하고 출발점은 0, 나머지는 무한대로 설정한다.
set에 없으면서 가장 작은 distance를 갖고 있는 vertex u를 찾은 뒤 set에 넣는다.
그 u의 모든 인접 vertex의 distance를 업데이트한다. u의 distance와 그 사이 edge의 distance를 합한 것을 인접 vertex가 갖고 있던 기존의 distance와 비교해서 작은 값으로 바꾼다.
이 과정을 set가 모든 vertex를 포함하기 전까지 반복한다.
Negative edge가 있을 때는 Bellman-Ford algorithm이다.
Shortest Path from Every Vertex to Every Other Vertex: Floyd Warshall
처음에 n by n matrix를 만들어서 대각 성분은 모두 예외값으로 넣고 다른 성분들은 i->j로 가는 weight를 넣는다. edge가 없으면 무한대를 넣는다.
그다음 1부터 n까지, i번째 행과 열을 기준으로 작업을 한다.
n번의 작업이 끝나면 각 성분이 의미하는 게 i부터 j로 가는 최소 weight이다.
Time Complexity: O(V^3)
https://www.youtube.com/watch?v=t3mf2Vu9wA4
To Detect Cycle in a Graph: Union Find
Disjoint-set data structure(서로소 집합 자료구조)에서 사용된다.
Find: 그 원소가 어느 subset에 포함돼있는지를 알려준다. 이를 통해 어떤 두 원소가 같은 subset에 있는 지 알 수 있다.
Union: 두 subset을 하나의 subset으로 합친다.
Union-Find 알고리즘을 어떤 방향성 없는 그래프가 사이클을 갖는 지 확인하는 데에 적용할 수 있는데 이때 self loop이 없다는 가정이다.
각 edge마다 양쪽의 vertex정보가 들어간 subset을 만든다. 만약 같은 subset에 들어가는 게 있다면 사이클이 있는 것이다.
union()과 find()에 대한 naive time complexity는 O(n)인데 Union by Rank를 쓴다면 O(log n)까지 줄일 수 있다.
Minimum Spanning Tree: Prim
Greedy 알고리즘이다.
Spanning tree란 connected and undirected graph에서 모든 vertex가 연결된 subgraph이다.
이 spanning tree중 edge weight sum이 가장 작은 것이 minimum spanning tree이다.
두개의 set가 필요한데 set1은 이미 MST에 포함된 vertex를 저장하고 다른 set2는 아직 포함되지 않는 vertex를 저장한다.
이 두 set 사이의 모든 edge중 가장 작은 edge를 찾은 뒤 연결된 set2의 vertex를 set1에 포함시킨다.
먼저 시작점의 distance를 0으로 하고 나머지는 무한대로 초기 설정한다.
set1에 포함되지 않았으면서 가장 작은 distance를 갖고 있는 vertex u를 찾아서 set1에 포함시킨다.
u와 인접한 모든 vertex의 distance를 업데이트한다.
이 과정을 set1이 모든 vertex를 포함할 때까지 반복한다.
Minimum Spanning Tree: Kruskal
모든 edge를 non-decreasing 순서로 정렬한다.
가장 작은 edge를 고른 뒤 지금까지 만들어진 spanning tree에 cycle을 만드는 edge인 지 체크하고 만들지 않는다며 이 edge를 고른다. cycle을 만들면 버린다.
(V-1)개의 edge를 찾을 때까지 반복한다.
Topological Sort
DAG(Directed Acyclic Graph)에서 적용된다.
DFS는 어떤 vertex에서 그 인접 vertex에 대해 recursive하게 돌지만, topological sort는 인접 vertex를 돌리기 전에 자신을 먼저 print해야 한다.
스택을 이용해서 구현할 수 있다.
DFS처럼 가장 깊숙이 들어가서 스택에 넣고 나오면서 스택에 넣는다.
그러면 다 끝났을 때 스택의 맨 위에는 제일 처음의 시작점이 올라와있게 된다.
Time Complexity: O(V+E) same as DFS
Boggle(Find All Possible Words in a Board of Characters)
Matrix의 각 셀에는 문자 하나씩 있고 찾고자 하는 단어가 있다. 이때 같은 셀은 다시 방문하지 않으면서 찾고자 하는 단어를 만들 수 있는 지 체크하는 문제이다.
모든 문자에 대해 시작점으로 해서 depth first traversal으로 탐색한다.
Bridges in a Graph
bridge: undirected connected graph에서 어떤 edge를 없앴을 때 disconnected graph가 될 때 그 edge를 bridge라고 한다.
disconnected undirected graph에서도 어떤 edge를 없앴을 때 disconnected component의 수가 늘어날 때 그 edge를 bridge라고 한다.
Simple approach: 각 edge에 대해 하나 하나 다 없애보면서 connectedness를 따진다. O(E*(V+E))
O(V+E) approach: DFS traversal을 하는데 어떤 edge (u, v)에 대해 v rooted subtree에서 u나 u의 ancestor에 도달할 수 있는 다른 방법이 없을 때 그 edge는 bridge이다.
//동영상 참고하자.
--------------------------------------------
Reference
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/
댓글
댓글 쓰기