달공이와 임베디드

[자료구조] 인접 행렬 그래프 (DFS-Recursion) 본문

알고리즘

[자료구조] 인접 행렬 그래프 (DFS-Recursion)

하일리99 2020. 1. 28. 23:43

인접 행렬 그래프 1

 

 

  • 단방향 그래프
  • 인접 행렬로 그래프를 나타냄
  • dfs-recursion
  • 3번 노드 출발점
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include <iostream>
#include <vector>
 
using namespace std;
 
int graph[7][7] = {
    {0, 0, 0, 0, 1, 0, 0},
    {1, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0, 0, 0},
    {0, 1, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0, 0},
};
 
int check[7];
 
void dfs(int node)
{
    check[node] = 1;
    
    cout << "node: " << node << endl;
    
    int next_node;
    for(int i=0; i<7; i++)
    {
        if (graph[node-1][i] == 0) continue;
        
        next_node = i + 1;
        
        if(check[next_node] == 1) continue;
        
        dfs(next_node); 
    }
}
 
int main()
{
    dfs(3);
 
    return 0;
}
 
 cs
과

 

결과
1
2
3
4
5
6
7
node: 3                                                                                                                                      
node: 2                                                                                                                                      
node: 1                                                                                                                                      
node: 5                                                                                                                                      
node: 6                                                                                                                                      
node: 7                                                                                                                                      
node: 4   
 cs

 

 

인접 행렬 그래프 2

 

  • 양방향 그래프
  • dfs-recursion
  • 그룹의 수
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
 
using namespace std;
 
int graph[7][7] = {
    {0, 0, 0, 0, 1, 1, 0},
    {0, 0, 1, 1, 0, 0, 0},
    {0, 1, 0, 1, 0, 0, 0},
    {0, 1, 1, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 1, 0},
    {1, 0, 0, 0, 1, 0, 1},
    {0, 0, 0, 0, 0, 1, 0},
};
 
int check[7];
 
 
void dfs(int node, int group)
{
    check[node] = group;
    
    cout << "(" << group <<") "<< "node: " << node << endl;
    
    int next_node;
    for(int i=0; i<7; i++)
    {
        if (graph[node-1][i] == 0) continue;
        
        next_node = i + 1;
        
        if(check[next_node] != 0) continue;
        
        dfs(next_node, group); 
    }
}
 
int main()
{
    for (int i=0; i<7; i++)
    {
        if (check[i+1] != 0) continue;
        
        dfs(i+1, i+1);
    }
    
    int group_number = 0;
    for (int i=0; i<7; i++)
    {
        if (check[i] > group_number)
            group_number = check[i];
    }
    
    cout << "group number: " << group_number << endl;
    return 0;
}
 
 cs

 

결과
1
2
3
4
5
6
7
8
(1) node: 1                                                                                                                                  
(1) node: 5                                                                                                                                  
(1) node: 6                                                                                                                                  
(1) node: 7                                                                                                                                  
(2) node: 2                                                                                                                                  
(2) node: 3                                                                                                                                  
(2) node: 4                                                                                                                                  
group number: 2 
 cs

 

'알고리즘' 카테고리의 다른 글

[백준][1065] 한수  (0) 2020.05.09
[C++ 자료구조] STL deque 사용 예제  (0) 2020.05.09
[C++ 자료구조] unordered_map  (0) 2020.05.07
[C++ 자료구조] STL deque  (0) 2020.05.07
[DP] 1로 만들기  (0) 2018.09.18
'알고리즘' Related Articles more
Comments