정의 :Vertices와Edges로 구성된 비선형 데이터 구조 : 그래프(G)는 정점(V)와 간선(E)로 표현 ->G=(V,E)
관련 용어
정점(또는 노드)
여러 가지 특성을 가질 수 있는 객체
V(G) : 그래프 G의 정점들의 집합
간선(또는 링크) - 정점들 간의 관계 - E(G) : 그래프 G의 간선들의 집합
📖 그래프 탐색 과정
그래프 탐색 : 하나의 정점에서 시작하여 모든 정점들을 차례대로 한번씩 방문하는 것
그래프 탐색 과정은BFS와DFS알고리즘을 바탕으로 이루어진다.
📍 BFS (Breadth-First Search)
정의 : 너비 우선 탐색
아래 예시로 제시된 그래프를 활용한 탐색 과정은 다음과 같다. (예시) (탐색 과정) -> b부터 탐색 시작 -> d와 a 방문 (이때 d,a는 큐로 enqueue) -> 큐에서 a를 dequeue, a에서 c로(이때 c는 큐로 enqueue) -> 큐에서 d를 dequeue, e와 f 방문(이때 f,e는 큐로 enqueue) -> 큐가 완전히 빌 때까지 큐에서 dequeue해서 방문하고 enqueue하는 과정을 반복 -> 마지막으로 g도 스택으로 enqueue된 후 dequeue되면서 종료
📍 DFS (Depth-First Search)
정의 : 깊이 우선 탐색
아래 예시로 제시된 그래프를 활용한 탐색 과정은 다음과 같다. (예시) (탐색 과정) -> a부터 탐색 시작 -> a에서 c로 (이때 a의 정보는 스택으로 이동) -> c에서 d로, d에서 f로, f에서 e로 (이때 c,d,f의 정보는 스택으로 이동) -> e에서 f로 (이때 f는 스택에서 pop) -> f에서 d로 (이때 d는 스택에서 pop) -> d에서 b로 (이때 d는 스택으로 push) -> b에서 d로, d에서 c로, c에서 a로(이때 a,c,d는 스택에서 pop)
📢 BFS와 DFS 차이점
💻 BFS 코드
class Graph
{
int V;
vector<list<int>> adj;
public:
Graph(int V);
void addEdge(int v, int w);
void BFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj.resize(V);
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::BFS(int s)
{
vector<bool> visited;
visited.resize(V,false);
list<int> queue;
visited[s] = true;
queue.push_back(s);
while(!queue.empty())
{
s = queue.front();
cout << s << " ";
queue.pop_front();
for (auto adjecent: adj[s])
{
if (!visited[adjecent])
{
visited[adjecent] = true;
queue.push_back(adjecent);
}
}
}
}
💻 DFS 코드
class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;
void addEdge(int v, int w);
void DFS(int v);
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFS(int v)
{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i);
}
💻 문제풀이
(강의자료)
문제1 •수거 로봇을 이용해 쓰레기를 수거합니다. •쓰레기 로봇이 충전할 수 있는 정착장이 있습니다. •쓰레기와 쓰레기 , 정착장과 쓰레기 거리는 모두 1km 로 동일합니다. •각 쓰레기가 정착장과 얼마나 떨어져 있는지 구하세요.
(코드)
class Graph {
int V;
bool* visited;
vector<int> dist;
vector<list<int>> adj;
public:
Graph(int _V);
~Graph();
void setUndirectEdges(int s, int d);
void setDirectEdges(int s, int d);
void BFS(int s);
};
Graph::Graph(int _V) {
this->V = _V;
visited = new bool[_V];
for (int i = 0; i < _V; ++i) {
visited[i] = false;
}
dist.resize(_V);
adj.resize(_V);
}
Graph::~Graph() {
delete visited;
}
void Graph::setUndirectEdges(int s, int d) {
adj[s].push_back(d);
adj[d].push_back(s);
}
void Graph::setDirectEdges(int s, int d) {
adj[s].push_back(d);
}
void Graph::BFS(int s) {
visited[s] = true;
queue<int> _queue;
_queue.push(s);
while (!_queue.empty()) {
s = _queue.front();
_queue.pop();
list<int>::iterator iter;
for (iter = adj[s].begin(); iter != adj[s].end(); ++iter) {
if (!visited[*iter]) {
visited[*iter] = true;
_queue.push(*iter);
dist[*iter] = dist[s] + 1;
}
}
}
문제2 •수거 로봇을 이용해 쓰레기를 수거합니다. •쓰레기 로봇이 충전할 수 있는 정착장이 2 개 이상 있습니다. •쓰레기와 쓰레기 , 정착장과 쓰레기 거리는 모두 1km 로 동일합니다. •각 쓰레기가 가장 가까운 정착장과 얼마나 떨어져 있는지 구하세요.
(코드)
class Graph {
private:
int V;
bool* visited;
vector<int> dist;
vector<list<int>> adj;
public:
Graph(int _V);
~Graph();
void setUndirectEdges(int s, int d);
void setDirectEdges(int s, int d);
void BFS(int s);
};
Graph::Graph(int _V) {
this->V = _V;
visited = new bool[_V];
for (int i = 0; i < _V; ++i) {
visited[i] = false;
}
dist.resize(_V);
adj.resize(_V);
}
Graph::~CGraph() {
delete visited;
}
void Graph::setUndirectEdges(int s, int d) {
adj[s].push_back(d);
adj[d].push_back(s);
}
void Graph::setDirectEdges(int s, int d) {
adj[s].push_back(d);
}
void Graph::BFS(vector<int> D) {
int _D = D.size();
queue<int> _queue;
for (int i = 0; i < _D; ++i) {
visited[D[i]] = true;
_queue.push(D[i]);
}
int s = 0;
while (!_queue.empty()) {
s = _queue.front();
_queue.pop();
list<int>::iterator iter;
for (iter = adj[s].begin(); iter != adj[s].end(); ++iter) {
if (!visited[*iter]) {
visited[*iter] = true;
_queue.push(*iter);
dist[*iter] = dist[s] + 1;
}
}
}
for (int i = 0; i < V; ++i) {
cout << i << " : " << dist[i] << endl;
}
}
BFS 관련 문제 (Leetcode 1971번)
문제 n개의 정점이 있는 양방향 그래프가 있으며, 각 정점은 0에서 n - 1(포함)까지 지정된다. 그래프의 간선은 2D 정수 배열 간선으로 표현되며, 각 간선 edges[i] = [ui, vi]는 정점 ui와 정점 vi 사이의 양방향 간선을 나타낸다. 정점 원본에서 정점 대상까지 유효한 경로가 있는지 확인하려고 한다. 대상 경로가 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.
풀이
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
vector<vector<int>> adj(n);
int s = edges.size();
for (int i = 0; i < s; ++i)
{
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
vector<bool> visited(n+5, 0);
queue<int> Q;
Q.push(source);
while (!Q.empty())
{
int f = Q.front();
if(f==destination)
return true;
Q.pop();
if (!visited[f])
{
for (int j = 0; j < adj[f].size(); ++j)
{
Q.push(adj[f][j]);
}
visited[f] = true;
}
}
return false;
}
};
