GRAPH - BFS , DFS

그래프 G =(V,E)

V: 노드 node , 정점vertex

E: 노드쌍을 연결하는 edge 혹은 link

n=|V| = 8

m=|E| = 11

방향 그래프 directed Graph

가중치(Weighted) 그래프 : 에지마다 가중치가 지정된다

 

인접행렬 adjacency matrix

당연히 대칭 행열

n*n 행렬

A = (a ij)

edge있으면 1 없으면 0

저장공간 O(n^2)

어떤 노드 v에 인접한 모든 노드 찾기 O(n)

어떤 에지 (u,v)가 존재하는지 검사 O(1) 

 

인접 리스트 (adjacency list)

2*edge개수

정점 집합을 표현하는 하나의 배열과

각 정점마다 인접한 정점들의 연결리스트 

비대칭

저장공간 O(n+m)

어떤 노드 v에 인접한 모든 노드 찾기 O(degree(V))  degree(v): 최악의 경우 n ,행렬보다 더좋음

어떤 에지 (u,v)가 존재하는지 검사 O(degree(U)) O(n) ,행렬보다 더 나쁨

 

가중치 그래프의 인접 행렬 표현

에지의 존재를 나타내는 값으로 에지의 가중치를 저장 1대신에

 

경로와 연결성

무방향 그래프 G = (V,E)에서 노드 u와 노드 v를 연결하는 경로 path가 존재할때 v와 u는 서로 연결되어 있다

노드 쌍들이 서로 연결된 그래프를 연결된 그래프라고 한다

연결 요소 connected component

 

그래프 순회 - 모든 노드들을 방문하는 일

너비우선순회 - BFS (Breadth First Search)

동심원의 형태로 순회

L0 = {s} 여기서 s는 출발노드

L1 = L0의 모든 이웃 노드들

L2 = L1의 이웃들 중 L0에 속하지 않는 노드들

 

1.check the start node

2. insert the start node into the queue.

while the queue is not empty do 

     remove a node v from queue

for each unchecked neighbour w of v do

check and insert w into the queue

 

 

 

3을 제거하고 3의 인접노드 1 5 7 8 중 체크안된 7 8을 체크하고 큐에 7 8 을 넣습니당

노드 방문 순서 : 1 2 3 4 5 7 8 6 (유일하지않음)

 

     BFS(G,s)
Q <- 공집합
Enqueue (Q,s); //출발노드를 Q에 넣는다
while Q!=공집합 do
u <- Dequeue(Q) // Q에서 꺼내기
	for each v adjacent to u do
		if v is unvisited then 
    		mark v as visited;
        	Enqueue(Q,v);
    	end
	end
end

최단 경로

S에서 Li에 속한 노드까지의 최단경로의 길이는 i이다

경로의 길이는 경로에 속한 edge의 개수를 의미한다

BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다

 

방향/무방향그래프, 출발노드s

모든 노드 v에대해

d[v] = s로부터 v까지의 최단 경로의 길이(edge의 개수)

ㅠ[v] = s로부터 v까지의 최단 경로상에서 v의 직전노드 , predecessor

     BFS(G,s)
Q <- 공집합;
d[s] <- 0; //출발점으로부터 s까지감
ㅠ[s] = null; // 그 경로상에서 나한테 도착하기 직전 노드 
Enqueue (Q,s); //출발노드를 Q에 넣는다
while Q!=공집합 do
u <- Dequeue(Q) // Q에서 꺼내기
	for each v adjacent to u do
		if v is unvisited then 
    		mark v as visited;
            d[v] = d[u] + 1; // distance to v
            ㅠ[v] = u; // u는 v의 predecessor이다 
        	Enqueue(Q,v);
    	end
	end
end

 

     BFS(G,s)
Q <- 공집합;
for each node u do  //o(n)
d[u] <- -1; 
ㅠ[u] <- null;
end

d[s]=0;
ㅠ[s] = null;

Enqueue (Q,s); //출발노드를 Q에 넣는다

	while Q!=공집합 do  // while문 한번돌때마다 큐에서 하나씩 꺼내므로 while문은 최대 n번 돈다
		u <- Dequeue(Q) // Q에서 꺼내기
			for each v adjacent to u do // 인접리스트로 구현할경우 for문은 각 노드 v에 대해서 degree(v)=한노드의 실제로 인접한 노드개수 번 돈다 , 2m이다! o(n+m), 인접 행렬 o(n) 전체 o(n^2)
				if(d[v]==-1)then 
            		d[v] = d[u] + 1; // distance to v
            		ㅠ[v] = u; // u는 v의 predecessor이다 
        			Enqueue(Q,v);
    		end.
	end.

 

 

학교 ppt 수도코드는 다음과 같다~~~~~ > <

   BFS(G,s)

for each node u < V-{s} do 
	color [u] <- WHITE;
	d[u] <- 무한대; 
	ㅠ[u] <- null;
end

color[s] <- GRAY;
d[s]=0;
ㅠ[s] = null;

Q <- {s} // Enqueue (Q,s); //출발노드를 Q에 넣는다

while Q!=공집합 do  // while문 한번돌때마다 큐에서 하나씩 꺼내므로 while문은 최대 n번 돈다
		u <- head[Q] // u <- Dequeue(Q) // Q에서 꺼내기 
		for each v adjacent to u do // 인접리스트로 구현할경우 for문은 각 노드 v에 대해서 degree(v)=한노드의 실제로 인접한 노드개수 번 돈다 , 2m이다! o(n+m), 인접 행렬 o(n) 전체 o(n^2)
			if(color[v] = WHITE)then 
            	d[v] = d[u] + 1; // distance to v
            	ㅠ[v] = u; // u는 v의 predecessor이다 
        		Enqueue(Q,v);
        Dequeue(Q)
        color[u] <- BLACK //큐에서 나갔다는 정점임을 표시해주기위해서 블랙으로??

 

 

 

 

깊이우선순회 (DFS) - inroder preorder postorder 은  dfs의 이진트리방법임

1. 출발점 s에서 시작한다

2. 현재노드를 visited로 mark하고 인접한 노드들 중 unvisited노드가 존재하면 그 노드로 간다

3. 2번 계속 반복한다

4. 만약 unvisited 인 이웃노드가 존재하지않으면 계속해서 직전노드를 되돌아 간다

되돌아갈 노드는 그 노드에  처음 도착할때 누구로부터 왔는냐가 바로 되돌아갈 노드이다~~~!!!!

5. 다시 2번을 반복한다

6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다

dfs 막다른 골목 되돌아 나가~~!

1 -> 3 -> 7 -> 8 -> 막혔네 마치 leaf node에 도달한거랑 비슷 -> 5 -> 2 -> 4 -> 6 -> 

 

빨간색 가는것 파란색 되돌아감 어디로 되돌아가는지 유심히 살피기~~!

  DFS(G,v)
  visited[v] <-YES
  for each node u adjacent to v do
  		if visited[u] = NO then
        	DFS(G,u);
            
            //이미 다 방문한 상태면 종료됨. 그러면 이미 그전에 있는 재귀함수 DFS가 수행됨. 이때 u로 되돌아 감

 

disconnected이거나 방향그래프라면 dfs에 의해서 모든 노드가 방문되지않을 수 있다

DFS를 반복하여 모든 노드 방문

  DFS-ALL(G,v)
 for each v < V //o(n) n: 노드개수 
 	visited[v] <- no;
    
 for each v < V
  		if visited[v] = NO then
        	DFS(G,v); //위의 코드!! //edge 1개당 1개의 recursion 호출! v에대해서 정점 u, u에대해서 v도 탐색 가능//인접리스트 o(m)-> 시간복잡도!o(n+m)
            
            //시간 복잡도 o(n+m)

 

학교 ppt 수도코드는 다음과 같다~~~~~ > <

  DFS(G)
 for each u < V do
 	color[u] <- white
    ㅠ[u] <- NIL
 time <-0
    
 for each u < V
  		if color[u] = white then
        	DFS_visit(G,u); //위의 코드!! //edge 1개당 1개의 recursion 호출! v에대해서 정점 u, u에대해서 v도 탐색 가능//인접리스트 o(m)-> 시간복잡도!o(n+m)
            
            //시간 복잡도 o(n+m)

DFS-visit(G,u)
color[u]<- gray
d[u] <- time <- time+1
for each v < Adj[u] do
if color[v] = white them
ㅠ[v] <- u
DFS-visit(G,v)

color[u] <- black
f[u] <- time <- time+1

codecodecode