알고리즘 - 그래프 탐색 알고리즘 구현(DFS)[Swift]

1. 간선의 배열과 노드의 개수가 주어졌을 때

위 그래프를 인접행렬의 이차원 배열로 만든다면 아래와 같다.

1	1	0	0	0	0	0	0
1	1	1	1	0	0	0	0
0	1	1	1	0	1	0	0
0	1	1	1	1	0	0	0
0	0	0	1	1	1	1	0
0	0	1	0	1	1	0	1
0	0	0	0	1	0	1	0
0	0	0	0	0	1	0	1

//간선의 배열
let graph = [[1, 1, 0 ,0 ,0 ,0 ,0, 0], [1, 1, 1, 1, 0, 0, 0, 0], [0, 1, 1, 1, 0, 1, 0, 0], 
              [0, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 0], 
              [0, 0, 1, 0, 1, 1, 0, 1], [0, 0, 0, 0, 1, 0, 1, 0], 
              [0, 0, 0, 0, 0, 1, 0, 1]]
//정점의 개수
let n = 8

 dfs 순회

//방문 한 노드인지 체크하기위한 배열
var visited = Array(repeating: false, count: n)

//dfs 알고리즘
func dfs(_ V: Int){
    //방문한 노드인지 check하기 위해 true
    visited[V] = true
    
    //방문한 노드번호 출력
    print(V, terminator: " ")
    
    // 0번노드에 연결된 노드를 찾는다
    for i in 0..<n{
        //예)
        // 1) graph[0][i]를 보게되면 [1, 1, 0, 0, 0, 0, 0, 0] 이다.
        // 2) 0번 노드에 인접한 노드는 0번 노드와 1번노드뿐인데 0번노드는 이미 ture 1번노드는 false
        // 3) 인접한 노드인 1번 노드로 이동
        // 1 ~ 3을 반복
        // * graph[V][i] == 1 && !visited[i] -> 현재 간선에 연결된 노드가 존재하고 아직 방문하지 않았으면!
        if graph[V][i] == 1 && !visited[i]{    //!visited[i] 는 i번째 노드를 방문하지 않았을 경우 ture이다.
            dfs(i)
            //만약 dfs(0)이 실행돼서 graph[0][i]가 진행중이다가
            //graph[0][1]이 되어 1번노드가 연결되어 있다는걸 알았을 때!
            //graph[1][i]이 되어 1번노드에 연결된 노드를 찾는다
        }
    }
}

//0번노드부터 순회
dfs(0)

주석없는 ver

var visited = Array(repeating: false, count: n)

func dfs(_ V: Int){
    visited[V] = true
    
    print(V, terminator: " ")
    
    for i in 0..<n{
        if graph[V][i] == 1 && !visited[i]{
            dfs(i)
        }
    }
}

dfs(0)