:)
그래프 (1) 본문
📖 그래프
- 정의
: 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;
}
};
'Data structure' 카테고리의 다른 글
그래프 (3) (1) | 2024.09.11 |
---|---|
그래프 (2) (1) | 2024.09.11 |
Augmentation (1) | 2024.09.11 |
이진탐색트리 (0) | 2024.09.11 |
우선순위 큐와 힙 (0) | 2024.09.11 |