그래프
객체와 객체 사이의 관계를 표현한 자료구조. 정점(vertices)이라고 불리는 노드들의 집합 V와 간선(edge)라고 불리는 정점의 쌍들의 집합 E를 사용하여 (V,E)로 나타냄.
용어
방향을 가진 간선(Directed edge)
방향을 가지지 않은 간선(Undireccted edge)
방향을 가지지 않는 그래프(Undirected graph)
방향을 가지는 그래프(directed graph)
그래프 어플리케이션
운송 네트워크 : 고속도로망, 비행 노선, 지하철
컴퓨터 네트워크 : 근거리 통신망, 인터넷, 웹
edge갯수에 따라 구현하는데
갯수가 적을 경우 -> 2차원배열
갯수가 많을 경우 -> 단일연결리스트
단일연결리스트로 구현된 그래프.
#include <stdio.h>
#include <stdlib.h>
#define NUM_VERTEX 5
struct node{
int v;
struct node *next;
};
struct node *graph[NUM_VERTEX]; //init with null
void addEdge(int v1,int v2, int doReverse){ //doReverse : 0-reverse 1-dontReverse
struct node *new_one = (struct node *)malloc(sizeof (struct node));
struct node *cur = graph[v1];
new_one->v = v2;
new_one->next = 0;
if(cur==0){
graph[v1] = new_one;
}else{ // else..
while(cur->next !=0){
cur = cur->next;
}
cur->next = new_one;
}
if(doReverse ==1){
addEdge(v2,v1,0);
}
return;
}
void showAdjacentVertex(int v){
struct node *cur = graph[v];
while(cur!=0){
printf("%d is the adjacent vertex\n",cur->v);
cur = cur->next;
}
}
그래프 탐색 알고리즘
-Depth first Search (깊이 우선)
강의 영상 : https://www.youtube.com/watch?v=C1j_IO_Ilz4
스택을 이용 - 새로운 경로로 갈 때 마다 push 갈 곳이 없으면 pop, 스택이 비었으면 종료.
visited Array라는 배열을 하나 생성해서 이미 방문한 곳인지 체크(다시 방문하지 않기 위해)
-Breadth First Search (넓이 우선)
강의 영상 : https://www.youtube.com/watch?v=6o5JH2m5cro
큐를 이용 - 디큐 할 때 다음경로의 노드를 인큐하고 visited Array에 방문했다고 체크 큐가 비면 종료
DFS,BFS 비교
DFS의 가장 큰 장점은 BFS보다 메모리를 조금 사용한다는 것
DFS는 각 레벨에서 모든 자녀들에 대한 포인터를 저장할 필요가 없기 때문임.
하지만 각 상황에따라 두가지 알고리즘을 잘 선택해야함. BFS는 마지막 레벨까지 도달하는데 시간이 많이 걸림.
찾는 값이 꼭대기 레벨 쪽에 위치하고 있다면 BFS, 바닥쪽에 위치하고 있다면 DFS가 좋은 방법임.
DFS , BFS 구현 (stack 부분은 DFS, queue부분은 BFS)
강의 영상 : https://www.youtube.com/watch?v=b78c9nt6Sfs
강의 영상 : https://www.youtube.com/watch?v=itNXPpLakdE
#include <stdio.h>
#include <stdlib.h>
#define NUM_VERTEX 5
struct node{
int v;
struct node *next;
};
struct node *graph[NUM_VERTEX]; //init with null
/*----------vertex visited--------------*/
//if visited[i] ==1 , visited
// 0 , dont visited
int visited[NUM_VERTEX] = {0};
/*---------- Stack related ------------*/
int stack[NUM_VERTEX];
int top = -1;
void push(int v){
if(top == NUM_VERTEX-1){
printf("----------- stack is full -----------\n");
return;
}
top++;
stack[top] = v;
}
int pop(){
int temp =0;
if(top == -1){
printf("----------- stack is empty -----------\n");
return -1;
}
temp = stack[top];
top--;
return temp;
}
// if the stack is empty : return 1
// 0 otherwise
int isStackEmpty(){
if( top==-1){
return 1;
}else{
return 0;
}
}
// return none visited node that linked v
// 연¯¡þ결Æa된ìE 노øe드ìa가Æ¢® 없ú©ª다¥U면¬e return -1
int findNextVertex(int v){
struct node *cur = graph[v];
while(cur!=0){
if(visited[cur->v]==0){
return cur->v;
}
cur = cur->next;
}
return -1;
}
void doDFS(int v){
printf("DFS visited %d\n",v);
visited[v] =1;
push(v);
while(isStackEmpty() ==0){
int next_vertex = -1;
next_vertex = findNextVertex(stack[top]);
if(next_vertex == -1){
pop();
}else{
printf("DFS visited %d\n",next_vertex);
visited[next_vertex]=1;
push(next_vertex);
}
}
}
/*---------- Stack related end------------*/
/*---------- Queue related ---------------*/
// 원¯©ª형u 큐¡Í
int head=0;
int tail=0;
int que[NUM_VERTEX];
void enque(int v){
if ((tail+1)%NUM_VERTEX==head){
printf("---------Queue full-----------\n");
return;
}
que[tail] = v;
tail = (tail+1)%NUM_VERTEX;
return;
}
// return 1 if the queue is empty
// 0 otherwise
int isQueEmpty(){
if(head==tail){
return 1;
}else{
return 0;
}
}
//return -1 if the queue is empty
int deque(){
int temp = -1;
if(isQueEmpty() ==0){
temp = que[head];
head = (head+1)%NUM_VERTEX;
}
return temp;
}
void addAdjacentNonVisitedVertexToQue(int v){
struct node *cur = graph[v];
while(cur!=0){
if(visited[cur->v]==0){
enque(cur->v);
}
cur = cur->next;
}
}
void doBFS(int v){
enque(v);
while(isQueEmpty() == 0){
int k = deque();
if(visited[k] ==0){
printf("BFS visited %d \n",k);
visited[k] = 1;
addAdjacentNonVisitedVertexToQue(k);
}
}
}
/*---------- Queue related end------------*/
void addEdge(int v1,int v2, int doReverse){ //doReverse : 0-reverse 1-dontReverse
struct node *new_one = (struct node *)malloc(sizeof (struct node));
struct node *cur = graph[v1];
new_one->v = v2;
new_one->next = 0;
if(cur==0){
graph[v1] = new_one;
}else{ // else..
while(cur->next !=0){
cur = cur->next;
}
cur->next = new_one;
}
if(doReverse ==1){
addEdge(v2,v1,0);
}
return;
}
void showAdjacentVertex(int v){
struct node *cur = graph[v];
while(cur!=0){
printf("%d is the adjacent vertex\n",cur->v);
cur = cur->next;
}
}
====================================================
addEdge(0,1,1);
addEdge(0,2,1);
addEdge(0,4,1);
addEdge(1,2,1);
addEdge(2,3,1);
addEdge(2,4,1);
addEdge(3,4,1);
를 해준후 알고리즘을 실행시킨 결과
Graph- Minimum Spanning Tree 알고리즘 (최소신장트리)
영상 강의 : https://www.youtube.com/watch?v=eSlHeXr4mkM
- 그래프의 모든 vertex를 최소 edge의 weight로 연결한 그래프
- 응용 ; 최소 비용으로 모든 도시 도로 연결
통신망 연결등.
Graph- Dijkstra 알고리즘
영상 강의 : https://www.youtube.com/watch?v=2F407IfchMQ
- 넓의 우선탐색의 확장(?)
- 최단거리 찾기 알고리즘
- 하나의 vertex로부터 시작
- 최단 거리의 vertex를 하나씩 추가
- 모든 vertex에 대한 최단거리를 찾을 때 까지 반복