알고리즘20

어떤 박스를 쓰느냐에 따라서 달라진다.

 

---

DFS를 재귀적으로 표현하는 것이 더 편할 때도 있다.

핵심만 보여주는 코드

 

 

p에서 시작했다고 치면 누군가 얘를 최초 호출해주는 애가 있어야 한다,

RDFS(p)

나머지는 재귀적으로 돌아간다.

 

 

global 마크 배열(모두 0으로 초기화)

1이 되면 마킹하는 것

 

 

노드마다 숫자를 2개 적는다.

pre = 1 / post =1 로 시작 (글로벌 변수)

 

pre(s) <- pre : pre++;

post(s) <- post: post++;

1씩 증가시켜준다. 

각각 pre order / post order 로 번호를 붙인 것

 

s에 진입

s의 인접 노드인 t에 가기 직전에 t가 마킹이 안되어있으면 RDFS(t)를 호출

---

 

나와 인접한 노드를 넣기 전에 p*를 넣는다.

내가 넣은 노드가 다 뽑히면 p*가 나온다!

---

 

connected graph

 

 

 

 

 

인접한 노드를 가지고 있다.

 

인접한 노드의 마킹을 check한다.

 

새로 marking하여 전진하면 child에 기록

s에 들어올때 이미 마킹이 되어있었다면 back에 기록

parent는 무시

 

 

Adj: 인접노드

Child: 전진한 노드

Parent: 부모 노드

Back: parent말고 이미 마킹되어있던 노드

 

다른 곳으로 전진하는 와중에 마킹된 것 (e)은 무시된다.

 

ex) b는 이미 마킹이 되어있어 s가 b를 back에 넣었듯이,

e의 입장에서 s는 이미 마킹이 되어있으므로 e가 s를 back을 넣었기 때문에

s입장에서 e는 무시된다.

 

 

---

back edges : 트리의 자손에서 조상으로 올라가는 길만 가능하다.

(방향성을 부여한 것을 설명을 위한 것)

 

그래프에서 잘 안풀리는 문제가 트리에서 쉽게 풀리는 이유라고 할 수 있음

 

back edge가 되는 것: 인접한 것 중에 들어왔을 때 이미 marking 되어 있는 것

ex) s->b

Q. b에 대해서 post를 했을까? (완전히 완료되었을까?)

A. b는 완료가 되었을 수 없다.

 

s에 들어왔을 때 b가 이미 마킹이 되어있다.

b는 종료가 안된 상태이기때문에 back에 들어온 것

 

조상과 자손을 잇는 형태만 가능하다.(b가 s의 자손)

 

또다른 back edge: "e는 s를 back에 넣는다." 도 같은 형태

(s가 e의 자손)

 

---

Bipartite Graph Detection

주어진 그래프가 Bipartite 그래프인지 확인한다.

두파트 그래프:

노드를 두 그룹으로 나눠서모든 엣지가 크로스로만 있도록 나눌 수 있다

 

Q. 엣지가 하나도 없다면  Bipartite 인가?

A. YES

 

 

- connected인지 확인 & 사이클이 없는지 확인 => 트리

 

or

 

- connected인지 확인 & 노드가 n개일 때 엣지 갯수가 반드시 n-1개

 

(사이클을 직접 체크하지 않아도 된다.)

 

 

 

---

루트를 무조건 왼쪽 그룹에 넣고 생각해보자.

 

루트와 연결된 노드는 무조건 오른쪽 그룹에 있어야 함

 

R와 L을 잇는 백엣지만 있어야 함

(같은 사이드에 있는 back edge가 하나라도 있으면 => NO)