dfsearch

깊이 우선 그래프 탐색(Depth-first Graph Search)

구문

v = dfsearch(G,s)

T = dfsearch(G,s,events)

[T,E] = dfsearch(G,s,events)

[___] = dfsearch(___,'Restart',tf)

설명

v = dfsearch(G,s)는 노드 s에서 시작하여 그래프 G에 깊이 우선 탐색을 적용합니다. 그 결과, 노드 ID가 발견된 순서대로 구성된 벡터가 생성됩니다.

T = dfsearch(G,s,events)는 하나 이상의 탐색 이벤트에 플래그를 지정하여 깊이 우선 탐색의 출력값을 사용자 지정합니다. 예를 들어, T = dfsearch(G,s,'allevents')는 모든 이벤트에 플래그를 지정하여 테이블로 반환하고, X = dfsearch(G,s,'edgetonew')는 간선으로 구성된 행렬 또는 셀형 배열을 반환합니다.

[T,E] = dfsearch(G,s,events)는 events가 'edgetonew', 'edgetodiscovered' 또는 'edgetofinished'로 설정된 경우에 간선 인덱스 벡터 E를 추가로 반환합니다. 간선 인덱스는 다중 그래프에서 간선을 고유하게 식별할 때 사용합니다.

tf가 true인 경우 [___] = dfsearch(___,'Restart',tf)는 발견된 노드에서 새 노드에 도달할 수 없는 경우 탐색을 다시 시작합니다. 위에 열거된 구문에 나와 있는 입력 인수 또는 출력 인수를 원하는 대로 조합하여 사용할 수 있습니다. 이 옵션을 사용하면 시작 노드 s에서 도달할 수 없는 경우에도 깊이 우선 탐색이 그래프에 포함된 모든 노드와 간선에 도달하도록 합니다.

예제

깊이 우선 그래프 탐색 수행하기

그래프를 생성하고 플로팅합니다.

s = [1 1 1 1 2 2 2 2 2];
t = [3 5 4 2 6 10 7 9 8];
G = graph(s,t);
plot(G)

노드 7에서 시작하여 그래프에 대해 깊이 우선 탐색을 수행합니다. 결과는 노드 발견 순서를 나타냅니다.

v = dfsearch(G,7)

v = 10×1

     7
     2
     1
     3
     4
     5
     6
     8
     9
    10

모든 이벤트를 사용한 깊이 우선 그래프 탐색

유방향 그래프를 생성하고 플로팅합니다.

A = [0 1 0 1 1 0 0; 
     0 0 0 0 0 0 0; 
     0 0 0 1 0 1 1;
     0 0 0 0 0 1 0; 
     0 0 0 0 0 0 0; 
     0 0 0 0 0 0 0; 
     0 0 0 0 0 0 0];
G = digraph(A);
plot(G)

노드 3에서 시작하여 그래프에 대해 깊이 우선 탐색을 수행합니다. 'allevents'를 지정하여 알고리즘의 모든 이벤트를 포함하는 테이블을 반환합니다.

T = dfsearch(G,3,'allevents')

T=13×4 table
        Event         Node       Edge       EdgeIndex
    ______________    ____    __________    _________

    startnode           3     NaN    NaN       NaN   
    discovernode        3     NaN    NaN       NaN   
    edgetonew         NaN       3      4         4   
    discovernode        4     NaN    NaN       NaN   
    edgetonew         NaN       4      6         7   
    discovernode        6     NaN    NaN       NaN   
    finishnode          6     NaN    NaN       NaN   
    finishnode          4     NaN    NaN       NaN   
    edgetofinished    NaN       3      6         5   
    edgetonew         NaN       3      7         6   
    discovernode        7     NaN    NaN       NaN   
    finishnode          7     NaN    NaN       NaN   
    finishnode          3     NaN    NaN       NaN   

알고리즘의 단계를 따르려면 위에서부터 아래로 테이블에 나와 있는 이벤트를 읽어보십시오. 예를 들면 다음과 같습니다.

1. 알고리즘이 노드 3에서 시작합니다.

2. 간선이 노드 3과 노드 4 사이에서 발견됩니다.

3. 노드 4가 발견됩니다.

4. 기타 등등...

여러 성분을 사용한 깊이 우선 그래프 탐색

여러 성분을 사용하여 그래프에 대한 깊이 우선 탐색을 수행한 후 탐색 결과를 기반으로 하여 그래프 노드와 간선을 강조 표시합니다.

유방향 그래프를 생성하고 플로팅합니다. 이 그래프에는 2개의 약한 연결성분이 있습니다.

s = [1 1 2 2 2 3 4 7 8 8 8 8];
t = [3 4 7 5 6 2 6 2 9 10 11 12];
G = digraph(s,t);
p = plot(G,'Layout','layered');

c = conncomp(G,'Type','weak')

c = 1×12

     1     1     1     1     1     1     1     2     2     2     2     2

노드 4에서 시작하여 그래프에 대해 깊이 우선 탐색을 수행하고 'edgetonew', 'edgetodiscovered', 'edgetofinished', 'startnode' 이벤트에 플래그를 지정합니다. Restart를 true로 지정하여 도달할 수 없는 노드가 남아 있을 때마다 탐색이 다시 시작되도록 합니다.

events = {'edgetonew','edgetodiscovered','edgetofinished','startnode'};
T = dfsearch(G,4,events,'Restart',true)

T=15×4 table
         Event          Node       Edge       EdgeIndex
    ________________    ____    __________    _________

    startnode             4     NaN    NaN       NaN   
    edgetonew           NaN       4      6         7   
    startnode             1     NaN    NaN       NaN   
    edgetonew           NaN       1      3         1   
    edgetonew           NaN       3      2         6   
    edgetonew           NaN       2      5         3   
    edgetofinished      NaN       2      6         4   
    edgetonew           NaN       2      7         5   
    edgetodiscovered    NaN       7      2         8   
    edgetofinished      NaN       1      4         2   
    startnode             8     NaN    NaN       NaN   
    edgetonew           NaN       8      9         9   
    edgetonew           NaN       8     10        10   
    edgetonew           NaN       8     11        11   
    edgetonew           NaN       8     12        12   

Restart가 true인 경우 'startnode' 이벤트는 알고리즘이 탐색을 다시 시작하는 위치와 시점에 대한 정보를 반환합니다.

다음과 같이 이벤트를 기준으로 그래프를 강조 표시합니다.

• 시작 노드는 빨간색으로 표시합니다.

• 녹색 간선은 'edgetonew'를 나타냅니다.

• 검은색 간선은 'edgetofinished'를 나타냅니다.

• 자홍색 간선은 'edgetodiscovered'를 나타냅니다.

highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'g')
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetofinished'), 'EdgeColor', 'k') 
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetodiscovered'), 'EdgeColor', 'm') 
highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')

그래프에서 순환 제거하기

일부 간선을 반전하여 유방향 그래프를 비순환적(acyclic)으로 만듭니다.

유방향 그래프를 생성하고 플로팅합니다.

s = [1 2 3 3 3 3 4 5 6 7 8 9 9 9 10];
t = [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2];
g = digraph(s,t);
plot(g, 'Layout', 'force')

그래프에 대해 깊이 우선 탐색을 수행하고, 'edgetodiscovered' 이벤트에 플래그를 지정합니다. 이 이벤트는 순환을 완료하는 간선에 대응됩니다.

[e,edge_indices] = dfsearch(g, 1, 'edgetodiscovered', 'Restart', true)

e = 3×2

     3     1
     6     4
     8     7

edge_indices = 3×1

     3
     9
    11

순환을 더 이상 완료하지 못하도록 flipedge를 사용하여 플래그가 설정된 간선의 방향을 바꿉니다. 그러면 그래프에서 모든 순환이 제거됩니다. isdag를 사용하여 그래프가 비순환적인지 확인합니다.

gnew = flipedge(g, edge_indices);
isdag(gnew)

ans = logical
   1

새 그래프를 플로팅하고 하고 뒤집힌 간선을 강조 표시합니다.

p = plot(gnew, 'Layout', 'force');
highlight(p,'Edges',findedge(gnew,e(:,2),e(:,1)),'EdgeColor','r')

입력 인수

G — 입력 그래프

graph 객체 | digraph 객체

입력 그래프로, graph 객체 또는 digraph 객체로 지정됩니다. 무방향 그래프를 생성하려면 graph를 사용하고 유방향 그래프를 생성하려면 digraph를 사용하십시오.

예: G = graph(1,2)

예: G = digraph([1 2],[2 3])

s — 시작 노드

노드 인덱스 | 노드 이름

시작 노드로, 다음 표에 있는 값 중 하나로 지정됩니다.

값	예제
스칼라 노드 인덱스	1
문자형 벡터 노드 이름	'A'
string형 스칼라 노드 이름	"A"

예: dfsearch(G,1)

events — 플래그로 지정된 탐색 이벤트

'discovernode' (디폴트 값) | 'startnode' | 'finishnode' | 'edgetonew' | 'edgetodiscovered' | 'edgetofinished' | 'allevents' | 셀형 배열 | string형 배열

플래그로 지정된 탐색 이벤트로, 다음 표에 나와 있는 옵션 중 하나로 지정됩니다.

• 하나의 이벤트에 플래그를 지정하려면 그 플래그 이름을 사용하십시오.

• 전체 이벤트 중 일부에 플래그를 지정하려면 두 개 이상의 플래그 이름을 셀형 배열에 넣어 사용하십시오.

• 모든 이벤트에 플래그를 지정하려면 'allevents'를 사용하십시오.

참고

events의 값에 따라 dfsearch의 출력값이 달라집니다. 각 옵션에서 반환되는 출력값에 대한 자세한 내용은 아래 표의 마지막 열을 참조하십시오.

events의 값	설명	출력값
'discovernode'(디폴트 값)	새 노드가 발견되었습니다.	다음과 같은 노드 ID의 벡터를 반환합니다. s가 숫자형 노드 인덱스이면 숫자형 노드 인덱스가 포함된 벡터가 반환됩니다. s가 노드 이름이면 노드 이름이 포함된 셀형 배열의 벡터가 반환됩니다.
'finishnode'	노드의 모든 진출 간선이 방문되었습니다.
'startnode'	이 플래그는 탐색의 시작 노드를 나타냅니다. 'Restart'가 true이면 탐색이 다시 시작될 때마다 'startnode'가 시작 노드에 플래그로 지정됩니다.
'edgetonew'	간선이 발견되지 않은 노드에 연결되어 있습니다.	다음과 같이 그래프에서 간선의 끝 노드를 지정하는 N×2 크기의 행렬이나 셀형 배열을 반환합니다. s가 숫자형 노드 인덱스이면 숫자형 노드 인덱스가 포함된 행렬이 반환됩니다. s가 노드 이름이면 노드 이름이 포함된 셀형 배열의 행렬이 반환됩니다. 또한, 간선 인덱스 벡터 E가 반환되도록 [T,E] = dfsearch(…)에 두 번째 출력값을 지정할 수도 있습니다.
'edgetodiscovered'	간선이 이전에 발견된 노드에 연결되어 있습니다.
'edgetofinished'	간선이 완료된 노드에 연결되어 있습니다.
셀형 배열	탐색 중 둘 이상의 특정 이벤트에 플래그를 지정하고자 한다면 그 플래그들을 셀형 배열에 포함시켜 지정해야 합니다.	다음과 같은 변수 T.Event, T.Node, T.Edge, T.EdgeIndex를 포함하는 테이블 T를 반환합니다. T.Event는 발생한 순서대로 플래그를 포함하는 categorical형 벡터입니다. T.Node는 이벤트 'discovernode', 'finishnode', 'startnode'에 해당하는 노드의 노드 ID를 포함합니다. T.Edge는 이벤트 'edgetonew', 'edgetodiscovered', 'edgetofinished'에 해당하는 간선을 포함합니다. T.EdgeIndex는 이벤트 'edgetonew', 'edgetodiscovered', 'edgetofinished'에 대한 간선 인덱스를 포함합니다. 간선 인덱스는 다중 그래프에서 반복되는 간선을 고유하게 식별할 때 사용합니다. T.Node와 T.Edge에서 사용되지 않은 요소는 NaN으로 설정됩니다. s가 숫자형 노드 인덱스이면 T.Node와 T.Edge가 숫자형 노드 인덱스를 포함합니다. s가 노드 이름이면 T.Node와 T.Edge는 노드 이름을 포함하는 셀형 배열입니다.
'allevents'	모든 이벤트에 플래그가 지정됩니다.

예: v = dfsearch(G,3)은 세 번째 노드에서 탐색을 시작하고 발견되는 순서대로 노드를 포함하는 벡터 v를 반환합니다. 이는 v = dfsearch(G,3,'discovernode')와 동일합니다.

예: X = dfsearch(G,'A','edgetonew')는 'A'라는 이름의 노드부터 시작하여, 탐색 과정에서 발견되지 않은 노드에 연결되는 간선을 각각 나타내는 문자형 벡터로 구성된 셀형 배열 X를 반환합니다.

예: T = dfsearch(G,s,{'discovernode','finishnode'})는 테이블 T를 반환하지만, 새 노드가 발견되거나 노드가 완료된 것으로 표시되는 경우에만 플래그를 지정합니다.

예: T = dfsearch(G,s,'allevents')는 모든 탐색 이벤트에 플래그를 지정하고 테이블 T를 반환합니다.

데이터형: char | string | cell

tf — 탐색을 다시 시작할지 여부

false (디폴트 값) | true

탐색을 다시 시작할지 여부로, false(디폴트 값) 또는 true로 지정됩니다. 이 옵션은 그래프가 시작 노드에서 도달할 수 없는 노드를 포함하는 경우 유용합니다. 'Restart'가 true이면 발견되지 않은 노드가 발견된 노드에서 도달할 수 없는 상태로 남아 있을 때마다 탐색이 다시 시작됩니다. 새 시작 노드는 아직 발견되지 않은 노드 중 가장 작은 인덱스를 갖는 노드입니다. 이 다시 시작 프로세스는 dfsearch가 모든 노드를 발견할 때까지 반복됩니다.

탐색이 시작 노드에서 도달할 수 있는 노드만 방문하도록 'Restart'는 기본적으로 false입니다.

'Restart'가 true이면 'discovernode' 이벤트와 'finishnode' 이벤트가 그래프에 포함된 각 노드에 대해 한 번씩 발생합니다. 또한, 그래프의 각 간선은 'edgetonew', 'edgetodiscovered' 또는 'edgetofinished'에 의해 플래그가 한 번 지정됩니다. 'edgetonew'에 의해 플래그가 지정된 간선은 하나 이상의 트리를 형성합니다.

예: T = dfsearch(graph([1 3],[2 4]),1,'Restart',true)는 그래프에서 연결성분을 모두 탐색합니다.

데이터형: logical

출력 인수

v — 노드 ID

숫자형 열 벡터 | 셀형 벡터

노드 ID로, 다음 형식 중 하나로 반환됩니다.

• 숫자형 노드 ID를 사용하여 시작 노드 s를 지정하는 경우 v는 노드 인덱스로 구성된 숫자형 열 벡터입니다.

• s가 노드 이름을 포함하는 문자형 벡터 또는 string형이면 v는 노드 이름을 포함하는 셀형 벡터입니다.

v에 포함된 노드 ID는 깊이 우선 그래프 탐색에서 발견된 순서를 반영합니다.

T — 탐색 결과

테이블 | 벡터 | 행렬 | 노드 이름으로 구성된 셀형 배열

탐색 결과로, 다음 형식 중 하나로 반환됩니다.

• events가 지정되지 않았거나 'discovernode', 'finishnode', 'startnode' 중 하나이면 T는 v와 유사하게 노드 ID로 구성된 벡터입니다.

• events가 'edgetonew', 'edgetodiscovered', 'edgetofinished' 중 하나이면 T는 관련 간선 각각에 대한 소스 노드와 타깃 노드를 나타내는 N×2 크기의 행렬이거나 셀형 배열입니다.

• events가 탐색 이벤트로 구성된 셀형 배열이거나 'allevents'이면 T는 플래그가 지정된 탐색 이벤트를 포함하는 테이블이 됩니다. 이 테이블은 T.Event에 탐색 이벤트 플래그를, T.Node에 관련 노드 ID를, T.Edge와 T.EdgeIndex에 관련 간선을 포함합니다.

모든 경우에 다음 사항이 적용됩니다.

• T의 행 또는 요소의 순서는 탐색 과정에서 나타나는 순서를 나타냅니다.

• s를 숫자형 노드 ID로 지정하면 T도 해당 숫자형 ID를 사용하여 노드를 참조합니다.

• s를 노드 이름으로 지정하면 T도 그 이름을 사용하여 노드를 참조합니다.

E — 간선 인덱스

벡터

간선 인덱스로, 벡터로 반환됩니다.

이벤트 'edgetonew', 'edgetodiscovered' 또는 'edgetofinished'에 대한 간선 인덱스 벡터를 가져오려면 이 출력값을 지정합니다. N×1 간선 인덱스 벡터는 T에 대응하는데, 이는 관련 간선 각각에 대한 소스 노드와 타깃 노드를 나타내는 N×2 크기의 행렬 또는 셀형 배열입니다.

예: [T,E] = dfsearch(G,s,'edgetonew')

팁

• dfsearch와 bfsearch는 무방향 그래프를 유방향 그래프와 동일하게 처리합니다. 노드 s와 노드 t 사이의 무방향 간선은 s에서 t로 연결되는 유방향 간선과 t에서 s로 연결되는 유방향 간선, 이 두 가지 유방향 간선처럼 처리됩니다.

알고리즘

깊이 우선 탐색 알고리즘은 시작 노드 s에서 시작하여 가장 작은 노드 인덱스를 갖는 s의 이웃 노드를 탐색합니다. 그런 다음 이 이웃 노드를 기점으로 다음으로 발견되지 않은 이웃 노드 중에서 가장 작은 인덱스를 갖는 이웃 노드를 조사합니다. 이 작업은 노드의 이웃 노드가 모두 방문된 걸로 나올 때까지 계속됩니다. 그런 후 깊이 우선 탐색은 경로를 역추적하여 이전에 발견된 노드 중 발견되지 않은 이웃 노드를 갖는 최근접이웃 노드를 찾습니다. 이 과정은 시작 노드에서 도달할 수 있는 모든 노드가 방문될 때까지 계속됩니다.

(재귀적) 알고리즘은 아래와 같은 의사코드(Pseudo-code)로 작성될 수 있습니다.

Event startnode(S)
Call DFS(S)

function DFS(C)

  Event discovernode(C)
  
  FOR edge E from outgoing edges of node C, connecting to node N
    Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E) 
    (depending on the state of node N)
    IF event was edgetonew
      Call DFS(N)
    END
  END

Event finishnode(C)  

END

dfsearch는 새 노드가 발견된 경우나 노드의 모든 진출 간선이 방문된 경우와 같이, 알고리즘의 다양한 이벤트를 설명하는 플래그를 반환할 수 있습니다. 이벤트 플래그가 아래 나열되어 있습니다.

이벤트 플래그	이벤트 설명
'discovernode'	새 노드가 발견되었습니다.
'finishnode'	노드의 모든 진출 간선이 방문되었습니다.
'startnode'	이 플래그는 탐색의 시작 노드를 나타냅니다.
'edgetonew'	간선이 발견되지 않은 노드에 연결되어 있습니다.
'edgetodiscovered'	간선이 이전에 발견된 노드에 연결되어 있습니다.
'edgetofinished'	간선이 완료된 노드에 연결되어 있습니다.

자세한 내용은 events에 대한 입력 인수 설명을 참조하십시오.

참고

입력 그래프가 시작 노드에서 도달할 수 없는 노드를 포함하는 경우, 'Restart' 옵션을 사용하면 너비 우선 탐색이 그래프에 포함된 모든 노드를 방문하게 됩니다. 이 경우, 'startnode' 이벤트는 탐색이 다시 시작될 때마다 시작 노드를 나타냅니다.

확장 기능

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2015b에 개발됨

참고 항목

bfsearch | conncomp | graph | digraph

도움말 항목

• 너비 우선 탐색(Breadth-First Search)과 깊이 우선 탐색(Depth-First Search) 시각화하기