데이터 구조 13

Selection Trees

전체에서 가장 작은 걸 가져가 Tree에 넣고, 그 다음 원소를 위로 올림.

가장 작은 값을 반환하는 걸로 구현되어있음 ,  큰 거로도 가능함.

정확히는 토너먼트 식으로 구현함. 

 

1) Winner trees :  원소 2개씩 대진표를 짜고, 이기는 원소가 계속 올라감.

 

2가 이겨서 올라간 뒤에는, 2 뒤에 있던 12가 올라온다. 

 

 

Loser trees : 패배한(더 큰) 원소의 정보를 올리고, 실제로 올라가는 건 이긴 쪽

(참고용)

노드에는 진 원소의 값을 넣고, 실제로 올라가는 애들은 이긴 애들임.

왼쪽 그림을 보면 2 vs 8했을 땐 2가 이기는데 진 8의 정보를 올려놓고,

그 뒤에도 그렇게 진 원소의 값을 올려놓는다.

 

그렇게 해서 Root 에 3까지 올라가있다는 건 3이 마지막에 졌고, 3한테서 이긴 놈은 그 위로 나갔다.

 

장점 ) 옆에 애랑 비교하는 게 아니라, parent랑 비교하면 되니까 정말 조금은 간단해진다.  

 

Counting Binary Trees

 

 

Graphs

 

개념 : Tree 는 root(parent)와 Child 관계에 중점을 두었다면,

Graph 는 연결이 되어있는지의 유무를 확인한다

                도시로 예를 든다면 도로가 연결되어 있는가 

 

• 용어

1) Vertex : 노드라고 봐도 됨    (도시)

2) Edge : 노드와 노드의 연결  (도로)

 

3) Adjacent : 두 vertex간 edge가 존재하는지 !   --> 직접 연결만 가능 [ Edge 한 개면 닿는 거리 ] 

D의 Adjacent vertex는 A와 B

 

4) Path (경로) : 두 vertex간 edge로 연결되는 vertex의 sequence 

 

5) Length of a path : 한 vertex에서 다른 vertex까지 가는 경로의 수

ex) D -> C는 DABC + DBAC + DAC +DBC 로 4개가 있다.

 

6) conneted : 두 vertex간 path가 존재 --> Adjacent와 차이점은 바로 옆이냐 or 가는 길이 있기는 하냐

 

7) Connected component

 

3 에서 6으로 가는 path가 있나?

왼쪽 있음 / 오른쪽 없음   --> 왼쪽은 connected component , 오른쪽은 아님

 

8) Cycle  : 자기 자신에서 시작해서 자기 자신으로 끝나는 path인 graph --> connected임 당연함

                 --> 시작과 끝이 동일한 vertex인 path

 

 

 

추가 특징

 

• (V1,V2) : 방향성 X   --> graph (=undirected)  

(V1,V2) = (V2,V1) 임

 

• <V1, V2> : 방향성 O  --> directed graph(=digraph)

<V1,V2> != <V2,V1> 오르막 내리막이라 생각

 

Strongly connected : 양방향 Path가 존재할 때 (Directed graph에서만 존재)

 

Degree of a vertex : 그 vertex와 연결된 edge의 수

Degree of a 'a' = 4 이해 됨?

 

근데 여기에서 방향성이 있을 땐,

1) indegree : incoming edge의 수 = 들어오는 방향의 edge

2) outdegree : outgoing edge의 수 = 나가는 방향의 edge

 

• Fully connected graph의 edge 개수

 

n개의 vertex에 대해, 자기 자신을 제외한 (n-1)에 대한 edge들.

하지만 이러면 한 번씩 더 카운트 되기 때문에, 반을 나눠준다. 

 

 

+ 한붓 그리기

 

 

 

---

 

Graphs represent

 

• Adjacency Matrix (방향 X)

 

--> 1) n*n 짜리 행렬

    2) 그래프에서 인접하면 1, 아니면 0

  3) 1의 개수 = edge개수의 2배임 (1,4) , (4,1) 이렇게 있기 때문에

4) 대각선 기준 대칭

 

 

 

• Adjacency Matrix (방향 O)

--> 1) n*n 짜리 행렬 // 세로 = from   , 가로 = to

    2) 그래프에서 인접하면 1, 아니면 0

  3) 1의 개수 = edge개수 <1,4> 와 <4,1> 둘 다 카운트 되어야 하기 때문에

4) 대칭 아님 (받기만 하고 안 가는 것도 있어서)

5) 가로에 있는 1은 Outdegree(나가는 거) / 세로로 있는 1은 Incoming(들어오는 거)

2의 가로축을 보면 2에서 나가는 것들을 볼 수 있음

2의 세로축으로 보면 어떤 게 들어오는 지 볼 수 있다.

 

 

• Adjacency lists

- 각 vertex마다 하나의 리스트 한 칸을 주고

    Adjacency 인 vertex들을 뒤로 이어서 linked list로 만든다.

 

- edge 의 2배만큼 나옴

 

 

 

• A weighted graph

- 각 edge 마다 가중치가 있다.

- 연결되어있고, 가중치가 있으면 matrix에 그 가중치를 적어줌.

- 방향이 없으면 대각선 대칭임

 

+ 한 도시에서 다른 도시로 가는 시간 or 톨비 라고 생각해도 됨 

(Network라고 부르기도 한다고 한다.)

 

 

 

Search 연산

1) DFS ( Depth First Search )

: 안 가본 쪽을 들어간다, 가려고 하는데 가본 곳이면 뒤로 빠짐  --> 스택으로 구현 

 

- 뒤로 빠지는 건 스택에서 pop해서 진행

- 한 번 다 돌고 다시 Root로 돌아와야함. Root에서 안 간 게 있을 수도 있어서

 

- 알고리즘

1) Start vertex를 방문하고, Stack에 넣는다.

2) Stack empty일 때까지 다음을 반복

 2-1) Stack 의 top원소와 adjacent한 vertex 중, 아직 방문하지 않은 vertex를 한 개 선택하여 방문하고, stack에 넣는다.

            더 이상 선택할 원소가 없다면, stack에서 원소 한 개를 pop한다.

 

 

 

2) BFS ( Breadth First Search )

: 인접한 애들 먼저 들렀다가 간다.

-- > Queue로 구현

 

큐에 a먼저 방문하고 넣는다.

--> a에 인접한 애들 큐에 넣음 [ b c 입장 ]

--> b 방문 후, 인접한 애들 큐에 넣음 [ d, e입장 ]    +      c 방문 후 , 인접한 애들 큐에 넣음 [ f ] 

...반복

 

 

- 알고리즘

 

1) Start vertex를 방문하고, queue에 넣는다.

2) queue empty일 때까지 다음을 반복

  2-1) queue 의 front 원소와 adjacent한 vertex 중에 아직 방문하지 않은 vertex를 한 개 선택하여 방문하고,

           queue에 넣는다.

             더 이상 선택할 원소가 없다면, queue에서 원소 한 개를 delete 한다.

 

 

 

방문했는지 확인하는 방법 

 

1) 모든 vertex를 (flag)Array로 만들어서 [ data값 , 방문 여부 (0,1)] 로 한다.

2) 방문 여부를 모두 0으로 초기화 ( 방문 X = 0 / 방문 O = 1)

3) vertex를 방문했으면, 해당 flag를 1로 변경

 

 

방문 순서

 

graph 표현 형태에 따라 순서 결정

ex) edge 데이터 입력 순서     OR       vertex에 부여된 일련번호

 

 

 

 

 

참고 : 

https://velog.io/@falling_star3/%EA%B7%B8%EB%9E%98%ED%94%84Graph-%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC%EA%B3%BC-%EC%9D%B8%EC%A0%91%EB%A6%AC%EC%8A%A4%ED%8A%B8

 

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

 

출처 : 한동대학교 김호준교수님 - 데이터구조 PPT