본문 바로가기

그래프2

[자료구조] 그래프 구현 1. 그래프 구현 방법 인접 행렬(adjacent matrix) : 2차원 배열 사용 인접 리스트(adjacency list) : 연결리스트 사용 1) 인접 행렬 방법 if(간선 (i, j)가 그래프에 존재) M[i][j] = 1. 존재하지 않으면 M[i][j] = 0 2. 인접 행렬 행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장 n개의 정점을 가진 그래프 : n * n 정방 행렬 행렬의 행 번호와 열 번호 : 그래프의 정점 행렬값 : 두 정점이 인접되어 있으면 1, 인접되어있지 않으면 0 1) 인접 행렬 예 2) 무방향 그래프 행 i의 합 = 열 i의 합 = 정점 i의 차수 3) 방향 그래프 행 i의 합 = 정점 i의 진출 차수(Out) 열.. 2020. 6. 28.
[자료구조] 그래프 1. 정의 그래프 G는 정점 V(Vertex)와 간선 E(Edge)로 구성되며 G = (V, E)로 표시된다 V는 정점(Vertices)들의 집합이다. E는 간선(Edge)들의 집합이다. 정점과 간선은 모두 관련되는 데이터를 가질 수 있다. 트리는 사이클이 없는 그래프의 한 종류이다. 1) 그래프 종류 G1과 G2는 무방향 그래프다. G2는 Tree다. G3은 방향성 그래프다. 2. 무방향 그래프(Undirected Graph) 두 정점을 연결하는 간선의 방향이 없는 그래프 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타낸다. V(G1) = {A, B, C, D} E(G1) = {(A, B), (A, D), (B, C), (B, D),.. 2020. 6. 27.

티스토리툴바