Main Content

bfsearch

너비 우선 그래프 탐색(Breadth-first Graph Search)

설명

예제

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

예제

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

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

예제

tftrue인 경우 [___] = bfsearch(___,'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)

Figure contains an axes object. The axes object contains an object of type graphplot.

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

v = bfsearch(G,2)
v = 10×1

     2
     1
     6
     7
     8
     9
    10
     3
     4
     5

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

s = [1 1 1 2 3 3 3 4 6];
t = [2 4 5 5 6 7 4 1 4];
G = digraph(s,t);
plot(G)

Figure contains an axes object. The axes object contains an object of type graphplot.

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

T = bfsearch(G,1,'allevents')
T=14×4 table
         Event          Node       Edge       EdgeIndex
    ________________    ____    __________    _________

    startnode             1     NaN    NaN       NaN   
    discovernode          1     NaN    NaN       NaN   
    edgetonew           NaN       1      2         1   
    discovernode          2     NaN    NaN       NaN   
    edgetonew           NaN       1      4         2   
    discovernode          4     NaN    NaN       NaN   
    edgetonew           NaN       1      5         3   
    discovernode          5     NaN    NaN       NaN   
    finishnode            1     NaN    NaN       NaN   
    edgetodiscovered    NaN       2      5         4   
    finishnode            2     NaN    NaN       NaN   
    edgetofinished      NaN       4      1         8   
    finishnode            4     NaN    NaN       NaN   
    finishnode            5     NaN    NaN       NaN   

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

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

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

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

  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');

Figure contains an axes object. The axes object contains an object of type graphplot.

c = conncomp(G,'Type','weak')
c = 1×12

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

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

events = {'edgetonew','edgetofinished','startnode'};
T = bfsearch(G,2,events,'Restart',true)
T=15×4 table
        Event         Node       Edge       EdgeIndex
    ______________    ____    __________    _________

    startnode           2     NaN    NaN       NaN   
    edgetonew         NaN       2      5         3   
    edgetonew         NaN       2      6         4   
    edgetonew         NaN       2      7         5   
    edgetofinished    NaN       7      2         8   
    startnode           1     NaN    NaN       NaN   
    edgetonew         NaN       1      3         1   
    edgetonew         NaN       1      4         2   
    edgetofinished    NaN       3      2         6   
    edgetofinished    NaN       4      6         7   
    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   

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

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

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

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

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

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

Figure contains an axes object. The axes object contains an object of type graphplot.

너비 우선 탐색을 사용하여 그래프가 이분 그래프인지 확인하고 관련 파티션을 반환합니다. 이분 그래프는 두 개의 세트 AB로 나눌 수 있는 노드가 있는 그래프입니다. 이 그래프에 포함된 간선은 각각 A의 노드를 B의 노드에 연결합니다.

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

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

Figure contains an axes object. The axes object contains an object of type graphplot.

그래프에 대해 너비 우선 탐색을 사용하여 그래프가 이분 그래프인지 확인하고, 그럴 경우 관련 파티션을 반환합니다.

events = {'edgetonew', 'edgetodiscovered', 'edgetofinished'};
T = bfsearch(g, 1, events, 'Restart', true);
partitions = false(1, numnodes(g));
is_bipart = true;
is_edgetonew = T.Event == 'edgetonew';
ed = T.Edge;

for ii=1:size(T, 1)   
    if is_edgetonew(ii)
        partitions(ed(ii, 2)) = ~partitions(ed(ii, 1));
    else
        if partitions(ed(ii, 1)) == partitions(ed(ii, 2))
            is_bipart = false;
            break;
        end
    end
end
is_bipart
is_bipart = logical
   1

g는 이분 그래프이므로 partitions 변수는 각 노드가 속하는 파티션에 대한 정보를 포함합니다.

partitions 변수를 사용하여 첫 번째 계층에 나타나는 소스 노드를 지정하고 'layered' 레이아웃을 사용하여 이분 그래프를 플로팅합니다.

partitions
partitions = 1x10 logical array

   0   1   1   0   0   1   0   1   0   0

plot(g, 'Layout', 'layered', 'Source', find(partitions));

Figure contains an axes object. The axes object contains an object of type graphplot.

입력 인수

모두 축소

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

예: G = graph(1,2)

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

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

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

예: bfsearch(G,1)

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

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

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

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

참고

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

events의 값설명출력값
'discovernode'(디폴트 값)

새 노드가 발견되었습니다.

다음과 같은 노드 ID의 벡터를 반환합니다.

  • s가 숫자형 노드 인덱스이면 숫자형 노드 인덱스가 포함된 벡터가 반환됩니다.

  • s가 노드 이름이면 노드 이름이 포함된 셀형 배열의 벡터가 반환됩니다.

'finishnode'

노드의 모든 진출 간선이 방문되었습니다.

'startnode'

이 플래그는 탐색의 시작 노드를 나타냅니다.

'Restart'true이면 탐색이 다시 시작될 때마다 'startnode'가 시작 노드에 플래그로 지정됩니다.

'edgetonew'

간선이 발견되지 않은 노드에 연결되어 있습니다.

다음과 같이 그래프에서 간선의 끝 노드를 지정하는 N×2 크기의 행렬이나 셀형 배열을 반환합니다.

  • s가 숫자형 노드 인덱스이면 숫자형 노드 인덱스가 포함된 행렬이 반환됩니다.

  • s가 노드 이름이면 노드 이름이 포함된 셀형 배열의 행렬이 반환됩니다.

또한, 간선 인덱스 벡터 E가 반환되도록 [T,E] = bfsearch(…)에 두 번째 출력값을 지정할 수도 있습니다.

'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.NodeT.Edge에서 사용되지 않은 요소는 NaN으로 설정됩니다.

  • s가 숫자형 노드 인덱스이면 T.NodeT.Edge가 숫자형 노드 인덱스를 포함합니다.

  • s가 노드 이름이면 T.NodeT.Edge는 노드 이름을 포함하는 셀형 배열입니다.

'allevents'

모든 이벤트에 플래그가 지정됩니다.

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

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

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

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

데이터형: char | string | cell

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

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

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

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

데이터형: logical

출력 인수

모두 축소

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

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

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

v의 노드 ID는 너비 우선 그래프 탐색에서 발견되는 순서를 반영합니다.

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

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

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

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

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

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

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

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

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

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

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

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

알고리즘

너비 우선 탐색 알고리즘은 시작 노드 s에서 시작하고 인접 노드의 인덱스 순서대로 인접 노드를 모두 탐색합니다. 그런 다음, 방문하지 않은 이웃 노드를 각각 순서대로 방문합니다. 이 알고리즘은 시작 노드에서 도달할 수 있는 모든 노드를 방문할 때까지 계속됩니다.

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

Event startnode(S)
Event discovernode(S)
NodeList = {S}

WHILE NodeList is not empty

  C = NodeList{1}
  Remove first element from NodeList
  
  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
      Event discovernode(N)
      Append N to the end of NodeList
    END
  END

  Event finishnode(C)
END

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

이벤트 플래그이벤트 설명
'discovernode'

새 노드가 발견되었습니다.

'finishnode'

노드의 모든 진출 간선이 방문되었습니다.

'startnode'

이 플래그는 탐색의 시작 노드를 나타냅니다.

'edgetonew'

간선이 발견되지 않은 노드에 연결되어 있습니다.

'edgetodiscovered'

간선이 이전에 발견된 노드에 연결되어 있습니다.

'edgetofinished'

간선이 완료된 노드에 연결되어 있습니다.

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

참고

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

확장 기능

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

버전 내역

R2015b에 개발됨