Graph
๊ทธ๋ํ๋ ์๋ฃ๊ตฌ์กฐ์ ์ผ์ข ์ผ๋ก ์ ์ (Node, Vertex)๊ณผ ๊ฐ์ (Edge)๋ก ์ด๋ฃจ์ด์ ธ์๋ค. ๊ฐ์ ์ ์ ์ ๊ฐ์ ๊ด๊ณ๋ฅผ ๋ํ๋ด๋ฉฐ, ์ ์ ์ฌ์ด๋ฅผ ์ฐ๊ฒฐํ๋ค.

G = (V,E)
๋ก ๋ํ๋ธ๋ค.
์ผ์์ํ์์ ๊ทธ๋ํ๋ฅผ ์๋ก ๋ค์ด๋ณด๋ฉด,
์งํ์ฒ ์ญ : ์ ์ / ์ญ์ฌ์ด : ๊ฐ์
๊ต์ฐจ๋ก : ์ ์ / ๋๋ก : ๊ฐ์
ํ์ด์ค๋ถ ์ฌ๋ : ์ ์ / ํ๋ก์ฐ : ๊ฐ์
์ด ์๋ค.
๋น์ ํ๊ตฌ์กฐ๋ i๋ฒ์งธ ์์๋ฅผ ํ์ํ ๋ค์ ๊ทธ ์์์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์์๋ฅผ ํ์ํ๋ ค๊ณ ํ ๋, ์ฌ๋ฌ ๊ฐ์ ์์๊ฐ ์กด์ฌํ๋ ํ์๊ตฌ์กฐ๋ฅผ ๋งํ๋ค. ๊ทธ๋ํ ๋ ๋น์ ํ ๊ตฌ์กฐ์ด๋ค.
์ฉ์ด
๋ ธ๋(Node) or ์ ์ (Vertex)
๊ฐ์ (Edge) or ๋งํฌ(link): ์ ์ ๊ฐ์ ๊ด๊ณ
๊ฒฝ๋ก(Path) : ์ ์ A์์ B๋ก๊ฐ๋ ๊ฒฝ๋ก
์๋์ฐจ ๋ค๋น๊ฒ์ด์ ๋น ๋ฅธ๊ธธ ์ฐพ๊ธฐ(์ต๋จ ๊ฒฝ๋ก)
์ฌ์ดํด(Cycle) or ํ๋ก : ์ ์ A์์ ๋ค์ A๋ก ๋์์ค๋ ๊ฒฝ๋ก (์์ ๋ ธ๋ == ๋์ฐฉ ๋ ธ๋)
๋จ์ ๊ฒฝ๋ก์ ๋จ์ ์ฌ์ดํด : ๊ฐ์ ์ ์ ์ ๋๋ฒ ์ด์ ๋ฐฉ๋ฌธํ์ง ์๋ ๊ฒฝ๋ก/์ฌ์ดํด
์ผ๋ฐ์ ์ผ๋ก ์ฌ์ฉํ๋ ๊ฒฝ๋ก์ ์ฌ์ดํด์ ๋จ์ ๊ฒฝ๋ก/์ฌ์ดํด์ด๋ค.
Directed Graph(๋ฐฉํฅ ์๋ ๊ทธ๋ํ)

Undirected Graph(๋ฐฉํฅ ์๋ ๊ทธ๋ํ ) == Bidirection Graph(์๋ฐฉํฅ ๊ทธ๋ํ)
A-E๋ AโE์ EโA๋ฅผ ๋ํ๋ธ๋ค.
์๋ฐฉํฅ ๊ทธ๋ํ๋ ๋ชจ๋ Directed Graph๋ก ๋ณ๊ฒฝํด์ ๋ฌธ์ ๋ฅผ ํ ์ ์๋ค.
์ผ๋ฐ์ ์ผ๋ก ๊ทธ๋ํ๋ผํ๋ฉด ๋ฐฉํฅ์ด์๋ ๊ทธ๋ํ๋ฅผ ๋งํ๋ ๊ฒ์ด๋ค.

Multiple Edge : ๋ ์ ์ ์ฌ์ด์ ๊ฐ์ ์ด ์ฌ๋ฌ ๊ฐ์ผ ์๋ ์๋ค.
a-c๋ ์ฐ๊ฒฐํ๋ ๊ฐ์ ์ด 2๊ฐ์ด๋ค.
๋ ๊ฐ์ ์ ์๋ก ๋ค๋ฅธ ๊ฐ์ ์ด๋ค.

Loop(๋ฃจํ) : ๊ฐ์ ์ ์ ๋ ์ ์ด ๊ฐ์ ๊ฒฝ์ฐ(4๋ฒ)

๊ฐ์ค์น(Weight) : ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ์๋ ๊ฒฝ์ฐ์ด๋ค.
์ด๋ ๊ฑฐ๋ฆฌ, ์ด๋ํ๋๋ฐ ํ์ํ ์๊ฐ, ํ์ํ ๋น์ฉ ๋ฑ๋ฑ๋ฑ
๊ฐ์ค์น๊ฐ ์๋ ๊ฒฝ์ฐ์๋ 1์ด๋ผ๊ณ ์๊ฐํ๋ฉด๋๋ค.

์ฐจ์(degree) : ์ ์ ๊ณผ ์ฐ๊ฒฐ๋์ด ์๋ ๊ฐ์ ์ ๊ฐ์์ด๋ค.
์์ ๊ฐ์ค์น ๊ทธ๋ฆผ์ผ๋ก ์๋ฅผ ๋ค์ด๋ณด์๋ฉด
1์ ์ฐจ์ : 2
2์ ์ฐจ์ : 4
Directed Graph์ ๊ฒฝ์ฐ์๋ ์ฐจ์๊ฐ ๋๊ฐ์ง๊ฐ ์๋ค.
in-degree(์ ์ ์ผ๋ก ๋ค์ด์ค๋ ๊ฐ์ ์ ์)
out-degree(์ ์ ์์ ๋๊ฐ๋ ๊ฐ์ ์ ์)
๊ทธ๋ํ์ ํํ
๊ทธ๋ํ์ ํํ์ ๊ทธ๋ํ๋ฅผ ์ ์ฅํ๋ ๋ฐฉ์์ด๋ค. ์ด๋ ์ ์ ์ ์๋ ์ ์๋ก ์ ์ฅํ๊ฒ ๋๊ณ , ๊ฐ์ ์ ์ ์ ์ฌ์ด์ ๊ด๊ณ๋ฅผ ์ ์ฅํ๋ค. ๊ทธ๋ฌ๋ฏ๋ก ๊ฐ์ ์ ์ ์ฅํ๋ ๊ฒ์ด ๊ทธ๋ํ๋ฅผ ์ ์ฅํ๋ ๊ฒ์ด๋ค.

๋ณดํต ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์์๋ ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์(n)๊ณผ ๊ฐ์ ์ ๊ฐ์(m)์ ์ ๋ ฅ ๋ฐ๊ณ ๊ฐ์ ์ ๊ฐ์๋งํผ ๋์งธ ์ค๋ถํฐ ๊ฐ์ ์ ์ ๋ณด๋ฅผ ์ ๋ ฅ ๋ฐ๋๋ค.
// ์๋ฐฉํฅ์ธ ๊ฒฝ์ฐ
5 6
A B
A E
B D
C D
C E
D E
๋ฐฉํฅ์ด ์๋ ๊ทธ๋ํ๋ผ๋ฉด ์ธ์ ํ๋ ฌ์ ๋น๋์นญ์ด๋ค.
์ธ์ ํ๋ ฌ(adjacency matrix)
๊ทธ๋ํ์์ ์ ์ (node)๊ณผ ๊ฐ์ (edge)๋ค์ ์ฐ๊ฒฐ๊ด๊ณ๋ฅผ ์ ์ฌ๊ฐ ํ๋ ฌ๋ก ํํํ ๊ฒ์ด๋ค.
๊ทธ๋ํ G = (V, E)๋ฅผ n >= 1
(n์ ์ ์ ์ด ์)์ ์ ์ ์ ๊ฐ์ง ๊ทธ๋ํ๋ผ๊ณ ํ์์ ๋ ๊ทธ๋ํ G์ ๋ํ ์ธ์ ํ๋ ฌ์ ํฌ๊ธฐ๋ n * n
์ด๋ฉฐ a[n, n]
ํฌ๊ธฐ์ 2์ฐจ์ ๋ฐฐ์ด๋ก ํํ๋๋ค. ์ด๋ a[n, n]์์ a[i, j] โ E(G)
๋ผ๋ฉด 1๊ฐ์ ์๋๋ผ๋ฉด 0์ ๊ฐ์ ๊ฐ์ง๊ฒ ๋๋ค.

๊ฐ์ค์น ์๋ ๊ฒฝ์ฐ
์ ์ ์ ๊ฐ์๋ฅผ V๊ฐ๋ผ๊ณ ํ์ ๋, V*V
ํฌ๊ธฐ์ ์ด์ฐจ์ ๋ฐฐ์ด์ ์ด์ฉํ๋ค.
// i์์ j๋ก ๊ฐ๋ ๊ฐ์ ์ด ์์ ๋
A[i][j] = 1
// i์์ j๋ก ๊ฐ๋ ๊ฐ์ ์ด ์์ ๋
A[i][j] = 0
//์์ ์๋ฐฉํฅ ๊ทธ๋ํ(B)
0 1 0 0 1
1 0 0 1 0
0 0 0 1 1
0 1 1 0 1
1 0 1 1 0
Undirected Graph ์์๋
A[i][j] == A[j][i]
์ด๋ค.์๋ ๊ฐ์ ๋ ์ ์ฅํ๊ธฐ ๋๋ฌธ์ ์ ์ฌ์ฉํ์ง ์๋๋ค.(์ฌ์ด ๋ฌธ์ ๋ฅผ ํ ๋ ์ฌ์ฉ)
#include <cstdio>
int a[10][10];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d %d",&u,&v);
a[u][v]=a[v][u]=1; // ์๋ฐฉํฅ
//๋จ๋ฐฉํฅ์ธ ๊ฒฝ์ฐ์๋ a[u][v]=1;๋ง ํด์ฃผ๋ฉด๋๋ค.
}
}
๊ฐ์ค์น ์๋ ๊ฒฝ์ฐ
๊ฐ์ค์น๊ฐ ์์ ๊ฒฝ์ฐ์๋ ๊ฐ์ค์น๋ ๊ฐ์ด ์ ์ฅํด์ฃผ๋ฉด๋๋ค.
// i์์ j๋ก ๊ฐ๋ ๊ฐ์ ์ด ์์ ๋
A[i][j] = w
// i์์ j๋ก ๊ฐ๋ ๊ฐ์ ์ด ์์ ๋
A[i][j] = 0
๋ง์ฝ ๊ฐ์ค์น๊ฐ 0<=w์ผ ๊ฒฝ์ฐ์๋ ๊ฐ์ ์ด ์๋ ๊ฒฝ์ฐ์๋ -1์ ์ ์ฅํด์ฃผ๋ฉด๋๋ค.
ํ์ง๋ง ๊ฐ์ค์น์ ๋ฒ์๊ฐ ์ ์๋ผ๋ฉด! 1. ๊ฐ์ ์ ์กด์ฌ ์ฌ๋ถ(1,0)๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด 2. ๊ฐ์ค์น ์ ๋ณด๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด ์ ์กฐํฉํด์ ์ฌ์ฉํ ์ ์๋ค.
//์์ ์๋ฐฉํฅ ๊ทธ๋ํ
0 6 0 0 1
6 0 0 8 0
0 0 0 2 3
0 8 2 0 4
1 0 3 4 0
#include <cstdio>
int a[10][10];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
a[u][v]=a[v][u]=w;
}
}
๊ณต๊ฐ๋ณต์ก๋
O(V^2)
์๊ฐ๋ณต์ก๋
์ด๋ค ๋ ธ๋ v์ ์ธ์ ํ ๋ชจ๋ ๋ ธ๋ ์ฐพ๊ธฐ O(n)์๊ฐ
์ด๋ค ์์ง(u,v)๊ฐ ์กด์ฌํ๋์ง ๊ฒ์ฌ O(1)
์ธ์ ๋ฆฌ์คํธ(adjacency list)
์ธ์ ํ๋ ฌ์ ํํํ ๋ ์ฐ๊ฒฐ๋์ง ์์๋ ๋ถ๋ถ๊น์ง ๋ชจ๋ ํํ์ด ๋๋ค. (์ฐ๊ฒฐ๋์ง ์์ ๋ถ๋ถ์ 0์ผ๋ก ํํํ๋ค.) ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ ๋์๋ 0๊น์ง ๋ชจ๋ ์กฐ์ฌ๋ฅผ ํด์ผํ๋ฏ๋ก ํจ์จ์ด ๋จ์ด์ง๋ ๊ฒฝ์ฐ๊ฐ ๋ง์๋ฐ ์ธ์ ๋ฆฌ์คํธ๋ ์ด๋ฌํ ๋จ์ ์ ๊ทน๋ณตํ๋ค.
std::vector()
๋ฅผ ์ด์ฉํ์ฌ ๊ฐ๋จํ๊ฒ ๊ตฌํํ ์ ์๋ค. ( vector ์์๋ณด๊ธฐ )์ด๋ ์ธ์ ํ๋ ฌ๋ก ๊ตฌํํ๋ ๊ฒ๋ณด๋ค ๊ณต๊ฐ์ ์ ๊ฒ ์ฌ์ฉํ๋ค. ๊ฐ ์ ์ ์์ ์ฐ๊ฒฐ๋๋ ๋ฆฌ์คํธ์ ์์๋ ์ค์ํ์ง ์๋ค.
๊ฐ์ค์น ์๋ ๊ฒฝ์ฐ(c++)
linked list๋ฅผ ์ด์ฉํด์ ๊ตฌํํ๋ค. ์ด ๋ A[i]๋ i์ ์ฐ๊ฒฐ๋ ์ ์ ์ linked list๋ก ํฌํจํ๊ณ ์๋ค.(i์ ์ฐ๊ฒฐ๋ ์ ์ ์ด ์ด ๋ช๊ฐ์ธ์ง ์ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.)
A[1] B E
A[2] A D
A[3] D E
A[4] B C E
A[5] A C D
์ด๋ ์ฐ๊ฒฐ๋ ์ ์ ์ ์ ์ฅํ๋ฏ๋ก ๊ฐ์ ์ ๋ํ๋ด๊ฒ ๋๋ค. ๋ชจ๋ ๊ฐ์ ์ด ํ๋ฒ ์ฉ ์ ์ฅ(O(E)=๊ฐ์ ์ ์)๋๋ค.
vector๋ก ๊ตฌํํ๊ธฐ
๊ทธ๋ฐ๋ฐ, linked list๋ ๊ตฌํํ๋๋ฐ ์๊ฐ์ด ์ค๋๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์, ์ฃผ๋ก vector์ ๊ฐ์ด ๊ธธ์ด๋ฅผ ๋ณ๊ฒฝํ ์ ์๋ ๋ฐฐ์ด์ ์ด์ฉํด์ ๊ตฌํํ๋ค.
#include <cstdio>
#include <vector>
using namespace std;
vector<int> a[10];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d %d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
}
์ฃผ์ํ ์ ์ด ํ๊ฐ์ง ์๋ค. cpp์์ vector์ ํํ์ ์ฃผ์ํด์ํ๋ค.
vector<int> a(10)
์ ํฌ๊ธฐ๊ฐ 10์ธ 1์ฐจ์ ๋ฐฐ์ด์ ์๋ฏธํ๋ค. (=int a[10]
)vector<int> a[10]
์ int a๋ฐฐ์ด์ด 10๊ฐ๊ฐ ์๋ค๋ ๊ฒ์ ์๋ฏธํ๋ค.
#include <cstdio>
#include <vector>
using namespace std;
int main(){
int n,m;
scanf("%d %d",&n,&m);
vector<vector<int>> a(n+1);
for(int i=0;i<m;i++){
int u,v;
scanf("%d %d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
}
๊ฐ์ค์น ์๋ ๊ฒฝ์ฐ(c)
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int vertext;
struct node * next;
}Node;
typedef struct graph{
int num_vertex; //vertex ์
Node ** adjList;
}Graph;
Node * new_node(int v){
Node * new = (Node *)malloc(sizeof(Node));
new->vertext = v;
new->next = NULL;
return new;
}
Graph * create_graph(int verNum){
Graph * g = (Graph *)malloc(sizeof(Graph));
g->num_vertex = verNum;
// verNum๊ฐ์ ์ ์ ์ ๊ฐ์ง๋ ์ธ์ ๋ฆฌ์คํธ
g->adjList = malloc(verNum*sizeof(Node));
for(int i=0;i<verNum;i++)g->adjList[i] = NULL;
return g;
}
void add_edge(Graph * g, int src, int dest){
// src์์ dest๋ก๊ฐ๋ edge ์ถ๊ฐ
Node * new = new_node(dest);
new->next = g->adjList[src];
g->adjList[src] = new;
// dest์์ src๋ก ๊ฐ๋ edge์ถ๊ฐ
new = new_node(src);
new->next = g->adjList[dest];
g->adjList[dest] = new;
}
void print_graph(Graph * g){
int v;
for(v=0;v<g->num_vertex;v++){
Node * tmp = g->adjList[v];
printf("์ธ์ ๋ฆฌ์คํธ %d ์ ์ \n",v);
while(tmp){
printf(" -> %d",tmp->vertext);
tmp=tmp->next;
}
printf("\n");
}
}
int main(int argc, const char * argv[]) {
Graph* graph = create_graph(6);
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 2);
add_edge(graph, 1, 4);
add_edge(graph, 1, 3);
add_edge(graph, 2, 4);
add_edge(graph, 3, 4);
add_edge(graph, 4, 6);
add_edge(graph, 5, 1);
add_edge(graph, 5, 6);
print_graph(graph);
return 0;
}
์ธ์ ๋ฆฌ์คํธ 0 ์ ์
-> 2 -> 1
์ธ์ ๋ฆฌ์คํธ 1 ์ ์
-> 5 -> 3 -> 4 -> 2 -> 0
์ธ์ ๋ฆฌ์คํธ 2 ์ ์
-> 4 -> 1 -> 0
์ธ์ ๋ฆฌ์คํธ 3 ์ ์
-> 4 -> 1
์ธ์ ๋ฆฌ์คํธ 4 ์ ์
-> 6 -> 3 -> 2 -> 1
์ธ์ ๋ฆฌ์คํธ 5 ์ ์
-> 6 -> 1
๊ฐ์ค์น ์๋ ๊ฒฝ์ฐ
A[i]๋ i์ ์ฐ๊ฒฐ๋ ์ ์ ๊ณผ ๊ทธ ๊ฐ์ ์ ๊ฐ์ค์น๋ฅผ linked list๋ก ํฌํจํ๋ค. ์ด๋ vector ์ปจํ ์ด๋์ ํ์ ์ผ๋ก pair๋ฅผ ์ฌ์ฉํ๋ค.( pair ์์๋ณด๊ธฐ )
A[1] (B,6) (E,1)
A[2] (A,1) (D,8)
A[3] (D,2) (E,3)
A[4] (B,8) (C,2) (E,4)
A[5] (A,1) (C,3) (D,4)
#include <cstdio>
#include <vector>
using namespace std;
vector<pair<int,int>> a[10];
int main(){
int n,m;
scanf("%d %d",&n,&m);
;
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
a[u].push_back(make_pair(v,w);
a[v].push_back(make_pair(u,w);
}
}
๊ณต๊ฐ๋ณต์ก๋
O(E)
์๊ฐ๋ณต์ก๋
์ด๋ค ๋ ธ๋ v์ ์ธ์ ํ ๋ชจ๋ ๋ ธ๋ ์ฐพ๊ธฐ O(degree(v))
์ด๋ค ์ฃ์ง(u,v)๊ฐ ์กด์ฌํ๋ ์ง ๊ฒ์ฌ O(degree(u))
๊ฐ์ ๋ฆฌ์คํธ
STL, array list๋ฅผ ์ฌ์ฉํ ์ ์๋ ๊ฒฝ์ฐ์๋ ๊ฐ์ ๋ฆฌ์คํธ๋ก ๊ทธ๋ํ๋ฅผ ์ ์ฅํ ์ ์๋ค.
๊ฐ์ ๋ฆฌ์คํธ๋ ๋ฐฐ์ด์ ์ด์ฉํด์ ๊ตฌํํ๋ฉฐ, ๊ฐ์ ์ ๋ชจ๋ ์ ์ฅํ๋ค.
์ ์ ์ ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ
E[0] = A B
E[1] = A E
E[2] = B A
E[3] = B D
E[4] = C D
E[5] = C E
E[6] = D B
E[7] = D C
E[8] = D E
E[9] = E A
E[10] = E C
E[11] = E D
๊ฐ ๊ฐ์ ์ ์ ์ ์ ์ ๊ธฐ์ค์ผ๋ก ๊ฐ์๋ฅผ ์ผ๋ค.
i
0
1
2
3
4
5
cnt[i]
0
2
2
2
3
3
๊ฐ ์ ์ ์ ๊ฐ์ ์์ ๋์ ํฉ์ ๊ตฌํ๋ค.
i
0
1
2
3
4
5
cnt[i]
0
2
4
6
9
12
i๋ฒ๊ณผ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ E[cnt[i-1]]๋ถํฐ E[cnt[i]-1]๊น์ง ์ด๋ค.
3๋ฒ๊ณผ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ E[4]~E[6-1]๊น์ง
๊ณต๊ฐ๋ณต์ก๋
O(E)
์ฐธ์กฐํ์ด์ง
Last updated
Was this helpful?