그래프 인접리스트(DFS, BFS)

그래프를 인접 리스트로 구현하는 방법은 정점별 인접 정점을 연결리스트로 저장하는 방식이다.

즉, 인접 리스트는 특정 노드에 연결되는 노드를 저장하는 방식을 통해 그래프를 구현한다. !! 이게 중요함..

그리고 인접행렬과 틀린점은 메모리 낭비가 없다. 실제 연결된 노드만 리스트에 들어가니까..

하지만 검색 시간은 더 걸린다.

음..깊이우선은 현재 노드와 연결된게 우선이고..

반면 넓이 우선은 현재 선택된 노드의 이전노드에서 연결된 다른노드들이 우선이다.

문제인 재귀호출 방법부터..

DFS(node V)

실제 처리 V

    v <- 방문표시

for(all u  ( v 의 인접 노드들))

if( 방문하지 않은 u찾고)

DFS(u)

스택방법은 1. 방문여부를 저장하는 1차원 배열이 있어야 하고 2. 깊이 우선을 가능하게하는 스택이 있어야 한다.

즉, 각 노드별로 탐색 되었는지 여부를 저장할 수 있어야 하며 , 깊이 우선 탐색을 위해 방문한 노드 정보를 저장할 스택이 있어야 한다.

DFS(node V)

스택 S

v <- 방문표시

push(S, v);

wihle(s가 비어있지 않다면)

u <- pop(S);

u에 대한 실제처리

for( all w in U의 인접 노드들)

if( w != 방문)

w <- 방문

push(S, w)

0

  ↙    ↘

1            2

   ↙   ↘     ↙     ↘

3        4 ↔ 5            6

↓

7

이상태에서 스택으로 DFS돌리면 순서는 0 1 3 7 4 5 2 6 이다

위에 1. 방문여부를 저장하는 1차원 배열이 필요한건..방문 표시 때문이다..그래서

pVisited = new int[그래프의 총 노드 수] 이렇게 해서 하나 있으면 좋다.

초기화하고..FALSE로..

최초 시작위치는 true로 해놓고..그리고 그걸 스택에 넣고 시작하낟..

좀더 코드로 본다면..

pVisited[startIndex] = true;

pushStack(Stack, StartIndex);

while (!Stack.empty()

{

GraphNode = popStack(Stack);

if (GraphNode != NULL)

{

cout << GraphNode 노드의 인덱스 << "방문했어요" << endl;    //리얼 방문 노드 처리하는부부

GraphNode = 현재 이 그래프와 연결된 노드들을 검색;

while (GraphNode != NULL)

{

//방문하지 않았다면

if (pVisited[연결된 노드의 인덱스] == false)

{

//여기서 방문처리는 실제 노드를 이미 방문했거나 스택 안에 저장되어있다는 뜻이다..

//실제 처리는 저기 위에 "방문했어요"가 된다. 팝하면서 되는거라고..

//여기는 While끝나면 다시 팝으로 가게 되어 있어..

pVisited[연결된 노드의 인덱스] = true;   

pushStack(Staco, 연결된 노드의 인덱스);

}

//이게 왜이러냐면 트리가 아니라 그래프라..

//0번루트는 1번과 2번하고만 연결되어있다는거임..

GraphNode = GraphNode->다음노드? 

}

}

}

겨룩 시간 복잡도는 O(m + n)이 소요 단, 인접리스트일때는

인접행렬이라면..O(n^2)이 된다. 이건 bfs dfs둘다 같음

BFS는 큐를 이용하고

슈도코드 보면

BFS(node V)
    큐 Q;

v<-방문

enqueue(Q, v);

while(Q.empty()!)

{

u <- dequeue(Q);

u에 대한 실제처리

for(all w in u의 인접노드들)

if(w != 방문)

w <- 방문;

enqueue(Q, w);

좀더 코드로 본다면..