그래프

그래프 용어정리

정점(node,vertex)

간선(edge) - 정점간의 관계

 

 

경로 .정점 a에서 b로가는 경로

사이클- 시작과 도착이 같은 곳(정점 a에서 다시 a로 돌아오는 경로

 

단순 경로/단순 사이클

1.경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클

2.특별한 말이 없으면 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말함

 

방향 있는 그래프

a → b 이면 b→a 는 없다.

방향 없는 그래프(양방향 그래프)

a - b 두 정점사이의 방향이 없다.

a → b  ,   b→a  두개를 다 나타난다.

 

루프

간선의 양 끝 점이 같은 경우

a → a 

 

가중치

간선에 가중치가 있는 경우 

ex) a에서 b로 이동하는 거리, 이동하는데 필요한 시간 등등 ...

 

차수

정점과 연결되어 있는 간선의 개수

단, 방향이 있는 그래프는 들어오는 간선이랑 나가는 간선 다르게 세야한다.

 

그래프를 표현 하는 방법        e=모서리 v는 정점

1. 인접행렬           예를 들어 5개의 정점이 있고 간선이 있을 떄 이어진 간선들을

   1 2 3 4 5            1을 해줘 간선과 정점을 저장하는 방식  (2차원배열 이용) 

1 0 1 0 0 0                     *양방향일 경우 대칭임

2 1 0 0 1 1          가중치가 있을 경우에는 1 대신 가중치 대입

3 0 0 0 1 0

4 0 1 1 0 0

5 0 1 0 0 0

2.인접 리스트          공간복잡도:  (인접리스트)v[e]< v(v2}(인접행렬)

링크드 리스트를 이용해서 구현    인접행렬에 비해 공간복잡도 효율성이 있음 

A[i] = i 와 연결된 정접

A[1]  2  5     :정점 1에 2 와 5가 연결됨을 의미 (메모리의 효율)

A[2]  1 3 4 5           링크드 리스트는 포인터로 구현 즉 오래걸림

A[3]  2  4                → 주로 VECTOR 이용해서 구현

A[4]  3  5 2 6              ex) vector<int> a[10] 

A[5] 1  2 4                가중치가 있을경우는 정점과 가중치를 연결리스트에 저장

A[6] 4                     pair를 이용해서 정점(간선)과 가중치  저장

                            ex) vector<pair<int,int>> a[10]

3.간선 리스트

배열을 이용해서 구현

간선을 모두 저장         v[e]

e[0] 1 2 

e[1] 2 3

e[2] 1 3 등등

 

 

그래프의 탐색   :  모든 정점을 1번씩 방문

1.DFS (깊이 우선 탐색) → 최대한 깊숙히 많이    :스택 사용

2.BFS (너비 우선 탐색) → 최대한 넓게 가는것     :큐 사용  장점: 모든 가중치 1 이면 최단거리

깊이 우선탐색  DFS

1.스택을 이용해서 갈 수 있는 만큼 최대한 많이간다

2.갈 수 없으면 이전으로 돌아온다

void dfs(int x){           //x를 방문
	check[x]=true;          //방문했으니 true
    printf("%d ",x);
    for(int i=1;i<=n;i++){          //다음 정점
    	if(a[x][i]==1&&check[i]==false){ //방문이 안되었고 간선이 연결되었으면
        	dfs(i);
         }
     }
 }
 인접 행렬 이용
 void dfs(int x){           //x를 방문
	cheak[x]=true;          //방문했으니 true
    printf("%d ",x);
    for(int i=1;i<a[x].size();i++){          //다음 정점 비교 a[x]:x와 연결된 정점
    	int y=a[x][i];
        if(check[y]==false){
        	dfs(y);
         }
     }
 }
 인접 리스트를 이용

 

너비 우선 탐색 BFS

1.큐를 이용해서 지금 위치에서 갈수 있는 것을 모두 큐에 넣는 방식

2.큐에 넣을때 방문했다고 체크

queue<int> q;
check[1]=true;q.push(1);
while(!q.empty()){
	int x=q.front();q.pop();   
    printf("%d ",x);
    for(int i=1;i<=n;i++){
    	if(a[x][i]==1 && check[i]==false){
        	check[i]=true;
            q.push;
            }
        }
    }
}//인접행렬로 만든 너비우선탐색
queue<int> q;
check[1]=true;q.push(1);
while(!q.empty()){
	int x=q.front();q.pop();   
    printf("%d ",x);
    for(int i=1;i<a[x].size();i++){
    	int y=a[x][i];
    	if(check[y]==false){
            check[y]=true;q.push;
            }
        }
    }
}//인접 리스트로 만든 너비우선탐색