기본 콘텐츠로 건너뛰기

개발 공부 - [그래프 알고리즘] 그래프(graph) 개념과 표현

 그래프 (Graph)


(무방향) 그래프 G = (V,E)

V : 노드 (node) 혹은 정점 (vertex)

E : 노드쌍을 연결하는 edge 혹은 link

개체들 간의 이진관계를 표현

n = |V|, m = |E|




방향 그래프와 가중치 그래프


방향그래프(Directed Graph) G = (V,E)

- 에지 (u,v)는 u로부터 v로의 방향을 가짐


가중치 그래프

- 에지마다 가중치(weight)가 지정

ㄴ 노드의 모든 에지마다 가중치라고 부르는 value를 지정해 주는 그래프이다.

    노드에다가 직접 부여하지는 않고 에지에 부여함



그래프의 표현

인접행렬(adjacency matrix), 인접리스트

인접행렬 : 근처에 있는 애부터 시작해서 모든 노드를 조회하는 방식이다.

= 연결 관계를 이차원 배열로 만들 수 있다.

n x n 배열을 a[0][0] 부터 a[n][n] 까지 정의할 수 있음.


인접리스트 (adjacency list)

정점 집합을 표현하는 하나의 배열과

각 정점마다 인접한 정점들의 연결 리스트


- 저장 공간 : O(n+m)

- 어떤 노드 v에 인접한 모든 노드 찾기 : O(degree(v)) 시간

- 어떤 에지 (u,v)가 존재하는지 검사 : O(degree(u)) 시간


참고 : https://sarah950716.tistory.com/12



방향그래프

인접행렬은 비대칭

인접 리스트는 m개의 노드를 가짐



가중치 그래프의 인접행렬 표현

- 에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장

- 에지가 없을 때 혹은 대각선:

특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서 표현



경로와 연결성

- 무방향 그래프 G= (V,E)에서 노드 u와 노드 v를 연결하는 경로(path)가

존재할 때 v와 u는 서로 연결되어 있다고 말함


모든 노드 쌍들이 서로 연결된 그래프를 연결된 그래프라고 한다 .(Connected graph)


연결 요소 (Connected component) : 노드 3개가 연결되어 있을 때 3개의 연결 요소를 가졌다고 표현한다.

참고: https://velog.io/@kjh107704/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C

아래의 그림처럼 나누어진 각각의 그래프를 연결 요소라고 한다.

즉, 노란색 덩어리 하나가 연결 요소 하나, 초록색 덩어리 하나가 연결 요소 하나를 차지하여 전체 그래프에는 연결 요소가 2개 존재하는 셈이다.

댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - PC 카카오톡 작업 표시줄 아이콘 이미지 변경 방법

PC 카카오톡 사용시 작업 표시줄에서 아이콘 이미지를 변경하는 방법이다. 1) 작업 표시줄 내 카카오톡 아이콘에서 마우스 오른쪽 버튼을 누른  뒤 속성에 들어간다. 2) 아이콘 변경에서  C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS DOS Icons) 등을 누른 뒤 적당한 것을 선택하여 적용한다. * 사내 메신저 아이콘을 참고해도 된다. 참고 : 기본 아이콘 위치 https://blog.silnex.kr/windowstip-windows-%EA%B8%B0%EB%B3%B8-%EC%95%84%EC%9D%B4%EC%BD%98-%EC%9C%84%EC%B9%98/ 2022. 11. 29.  생각보다 유입이 많아서 놀랐습니다. PC 카톡 사용자 화이팅!

운동 정보 - 어메이즈핏 밴드 5 스마트밴드 나이키 런 클럽(NRC = Nike Run Club) 연동

 나이키 런 클럽 쓰려고 산 어메이즈핏 밴드5 인데 연동이 영 어려워서 찾아보고 써봤다. 1. Zepp 앱은 연동이 되어 있어야 한다. 2.  Zepp 앱 -> 프로필 -> 내 기기 -> Amazfit Band 5 3. 검색 가능 : 켜짐 활동 심박수 공유 : 켜짐 연결 제한 : 꺼짐 (기본) 백그라운드에서 실행 : 제외로 등록 4. NRC(나이키 런 클럽) 앱 -> 설정 -> 러닝 설정 -> 기기 5. 심박수 표시 -> 블루투스에서 AmazFit Band 5 누르고 NRC 즐기면 된다! * 안드로이드 이용자입니다.