기본 콘텐츠로 건너뛰기

개발 공부 - [그래프 알고리즘] 순회 - 그래프에서의 BFS

 그래프 순회 (Graph Traversal)


순회

    그래프의 모든 노드들을 방문하는 일


대표적 두 가지 방법

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

    DFS (Depth - First Search (깊이우선순회))



BFS는 동심원 형태로 노드를 방문하는 건데

    이거는 모든 노드를 결국 다 방문하기는 하는데,

    출발 노드를 주어지게 해 놓고 (없으면 임의 노드를 출발점으로 삼음)

    인접한 노드를 먼저 탐색하는 방법이다.

    출발노드 -> 모든 이웃 노드 -> 이웃 노드1의 모든 노드 .. -> 이웃노드 n의 모든 노드

    이런 식으로 방문하는데,

    속하지 않는 노드를 추가하는 방식으로 구현한다.


    큐를 이용해서 너비우선순회를 하려면,

    이미 방문한 노드를 check 하도록 해 놓고 (start 노드부터 check로)

    큐에다가 start 노드를 첫번째로 삽입하고, 

    아직 방문되지 않은 노드를 찾아서 check로 바꾸고 또 삽입하고 하는 방식으로

    루프를 돌려서 방문되지 않은 노드가 전체에 아무것도 없을 때까지 돌리면 됨



너비우선순회 수도코드는 도움을 받았음 (치기 귀찮았습니다...)

BFS pesudo code

  • 그래프 G, 출발 노드 S


00 BFS(G, s)
01   Q <- null;
02   Enqueue(Q, s);
03   while Q != null do
04     u <- Dequeue(Q);
05     for each v adjacent to u do
06       if v is unvisited then
07         mark v as visited;
08         Enqueue(Q, v);


출처: https://ict-nroo.tistory.com/79?category=698685 [개발자의 기록습관]


이거 최단경로를 구하려면

위의 S에서 Li 에 속한 노드까지의 최단 경로의 길이는 i라는 것으로 두고 시작하는데,

여기서 경로의 길이는 경로에 속한 에지의 개수를 의미한다. (에지 의미는 이전 강좌에 참조)


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

* 이거 쥐가 치즈 물고 밖에 나가는 함수 구현할 때 적용하는 그거구나...


최단 경로

입력 : 방향 혹은 무방향 그래프 G = (V, E), 그리고 출발노드 s


출력 : 모든 노드 v에 대해서

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

π[V] = s로 부터 v까지의 최단경로상에서 v의 직전 노드(predecessor)


  • Pseudo code

    • 02 - 04 : 모든 노드 u에 대해서 d[], π[]를 초기화

    • 05 - 06 : 스타트 노드의 d[], π[]를 설정

    • 11 : d[v] 가 -1인가를 체크하여 unvisited 체크를 구현

    • 12 - 13 : unvisited 노드에 대하여 d[v], π[v]를 저장

      • 최단경로 길이 d[v]는 u까지의 최단경로길이 d[u]를 지나오는 것이므로 d[u] + 1이 될 것이고,

      • v노드의 최단경로상에서 v의 직전노드는 u가 된다.

    • 14 : unchecked 노드만 큐에 들어갈 수 있으므로 어떤 노드도 큐에 두번 들어가지는 않는다.


00 BFS(G, s)
01   Q <- null;
02   for each node u do
03     d[u] <- -1;
04     π[u] <- null;
05   d[s] <- 0; //distance from s to s is 0
06   π[s] <- null; //no predecessor of s
07   Enqueue(Q, s);
08   while Q != null do
09     u <- Dequeue(Q);
10     for each v adjacent to u do
11       if (d[v] == -1) then
12         d[v] <- d[u] + 1; //distance to v
13         π[v] <- u; //u is the predecessor of v
14         Enqueue(Q, v);


출처: https://ict-nroo.tistory.com/79?category=698685 [개발자의 기록습관]


이렇게 추가해서 모든 노드에 대해서 unvisited / visited에 대한 분기를 한다.

이거를 구현할 때 인접 리스트 방식으로 구현을 하면,

시간 복잡도는 

O(n+m)이 된다. (while문 한번 동작할 때마다 큐에서 하나를 꺼내니까 while문이 최대 n번 동작해야 하는데, 인접리스트로 구현시에 for이 또 각 노드 v에 대해서 degree(v)번 돌기 때문에 이것이 2m이 된다...)


BFS 트리는

각 노드 v와 파이[v]를 연결하는 에지들로 구성된 트리인데,

[BFS 트리에서 s에서 v까지의 경로는 s에서 v까지 가는 최단 경로]

어떤 엣지도 동심원의 2개의 layer(L0에서 L2로 가지 않는다)를 건너가지 않는다.(동일 레이어의 노드를 연결하거나, 혹은 1개의 layer를 건너간다.)

(왜냐면 코드상에서 봐도 checked이면 넘어가니까...)


그래프가 connected 라면 모든 노드를 방문하게 되지만, 그래프가 disconnected 이거나 혹은 방향 그래프라면 BFS에 의해서 모든 노드가 방문되지 않을 수도 있다.

disconnected 그래프의 모든 노드를 방문하려면 BFS를 반복하여 모든 노드 방문

전체 노드중 unvisited 노드가 없을 때까지 BFS를 반복한다.


= 이게 한번 더 방문하더라도 모든 unvisited를 없애려면 BFS를 여러번 하는 것이라는 말인데... (어...근데 그럼 방향 그래프면 굳이 BFS를 왜 쓰지... 하는 의문이 생기지만 DFS 이후에 생각해 보자)

댓글

  1. 굳이 O(n+m)인데 BFS를 여러번 돌릴 거면 시간 복잡도 의미가 있는지 궁금

    답글삭제

댓글 쓰기

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야