자료구조의 한 종류, 정점(vertex)와 간선(edge)로 이루어진 자료구조.
즉. 점과 선으로 이루어진 자료구조. 트리는 부모노드와 자식노드가 간선으로 연결되어 있으므로, 그래프의 한 예시이다.
대표적으로 DFS와 BFS가 있다.
정점에서 한 간선을 통해 다른정점으로 이동한후, 다시 그 정점을 기준으로 다른 정점으로 점점더 깊이 이동하는 방식
최대한 넓게, 시작정점부터 이동할수 있는 간선을 통해 모두 이동한후, 다시 그 정점을 기준으로 이어져있는 모든 간선을 통해 이동한다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"
#define MAX 1000+1
int N, M, V;
int map[MAX][MAX];
bool visited[MAX];
queue<int> q;
void DFS(int v) {
visited[v] = true;
cout << v << " ";
for (int i = 1; i <= N; i++)
{
if (map[v][i] == 1 && visited[i]==0)
{
DFS(i);
}
}
}
void BFS(int v) {
q.push(v);
visited[v] = true;
cout << v << " ";
while (!q.empty())
{
v = q.front();
q.pop();
for (int w = 1; w <= N; w++)
{
if (map[v][w]==1 && visited[w] ==0)
{
q.push(w);
visited[w] = true;
cout << w << " ";
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
cin >> N >> M >> V;
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
map[a][b] = 1;
map[b][a] = 1;
}
memset(visited, 0, sizeof(int) * N);
DFS(V);
cout << endl;
memset(visited, 0, sizeof(int) * N);
BFS(V);
}
https://devuna.tistory.com/32
https://velog.io/@vagabondms/DFS-vs-BFS