24.02_Graph_22.09.23

Graph

>의미

: 여러 개의 점들이 서로 연결되어 있는 관계를 표현한 자료구조(수학에서 배운 x-y그래프 아님)

: 네트워크망과 같은 구조로 생각.

>Graph 구조

• 1. 정점(vertex)

: Graph 구조에 있는 각각의 데이터

• 2. 간선(edge)

: 정점을 잇는 통로(선)

: 단방향, 양방향이 존재

• 3. 직접 관계

: 한 개의 간선으로 연결된 관계

• 4. 간접 관계

: 여러 간선과 정점을 거쳐 연결된 관계

• 5. 비가중치 그래프(unweighted Graph)

: 연결의 강도와 같은 추가적인 정보가 없는 그래프

: vertex와 edge로만 이루어진 그래프

: 연결 유무만 확인 가능

• 6. 가중치 그래프(weighted Graph)

: 연결의 강도와 같은 추각적인 정보가 있는 그래프

: vertex와 edge외에도 추가적인 정보가 있는 그래프

: 연결 유무 외에도 연결된 상태 및 정도를 알 수 있음.

• 7. 무방향 그래프(undirected graph)

: edge들이  양방향인 상태의 그래프

• 8. 방향 그래프(directed graph)

: edge들이 단방향인 상태의 그래프

• 9. 진입차수 (in-degree) / 진출차수 (out-degree)

: 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄.

• 10. 자기 루프(self loop)

: 정점에서 시작하는 진출 간선이 본인을 향하는 경우

: 다른 정점을 거치지 않음(정점 1 + 간선 1)

• 11. 사이클(cycle)

: 한 정점에서 출발한 후, 최종적으로 다시 본인으로 돌아오는 경우, 사이클이 존재한다고 표현.

>Graph 표현 방식

• 인접 행렬(adjacency procession)

: 직접 관계인 두 정점을 인접하다고 표현.

: 인접한 상태인지 확인하는 2차원 행렬이 존재함.

: 두 점이 이어진 상태면 1(true), 이어지지 않으면 0(false)의 값으로 저장되어 있음.

: 예시) [numVertex][numVertex]

• 인접 행렬의 사용

: 정점 사이의 관계를 확인할 때 용이

: 가장 빠른 경로를 찾을 때, 주로 사용

• 인접 리스트

: 각 vertex가 어떤 vertex와 인접하는지 리스트 형태로 표현한 것.

: 각 vertex마다 하나의 인접 리스트를 갖음

: 해당 리스트는 vertex끼리의 인접 순서는 무시함

: 인접한 모든 vertex의 정보를 저장하고, 마지막엔 null을 저장한다.

• 인접 리스트의 사용

: 메모리를 효율적으로 사용하고자 할 때 사용

: 인접 행렬로 파악하기에는 인접 행렬은 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지함!

>Graph의 실사용 예시

: 포털 사이트 검색 엔진

: SNS의 유저 관계

: 네비게이션 (길 찾기, 빠른 길 찾기)

 

인접 행렬 구현

• 필드1

: 2차원 배열 변수 저장

: 모든 버텍스가 행, 그리고 열에도 똑같이 입력될 예정

• setter

: 인접 행렬(2차원 배열)을 생성하는 메서드

: 버텍스의 갯수를 매개변수로 함.

: 반복문을 이용하여 인데스 0부터 주어진 갯수 만큼의 길이를 같는 2차원 배열 생성

• getter

: 필드1 주소 반환 메서드

• addEdge

: 버텍스 사이의 간선을 생성하는 메서드

: 두 개의 값을 매개변수로 삼으며, 시작점(vertex1)과 종료점(vertex2)를 받는다.

: vertex1, 2가 주어진 2차원 배열의 길이보다 길면 종료

: vertex1의 행에서 vertex2의 열의 값을 1(연결)로 변경. (방향 그래프라는 가정)

• hasEdge

: 버텍스 사이의 간선의 유무를 파악하는 메서드

: 두 개의 값을: 두 개의 값을 매개변수로 삼으며, 시작점(vertex1)과 종료점(vertex2)를 받는다.

: vertex1, 2가 주어진 2차원 배열의 길이보다 길면 종료

: vertex1의 행에서 vertex2의 열의 값이 1(연결)이면 true, 0(비연결)이면 false 반환. (방향 그래프라는 가정)

• removeEdge

: 버텍스 사이의 간선을 제거하는 메서드

: 두 개의 값을 매개변수로 삼으며, 시작점(vertex1)과 종료점(vertex2)를 받는다.

: vertex1, 2가 주어진 2차원 배열의 길이보다 길면 종료

: vertex1의 행에서 vertex2의 열의 값을 0(비연결)으로 변경. (방향 그래프라는 가정)

 

인접 리스트 구현

• 필드1

: 버텍스와 엣지를 연결지어 담아낼 변수 저장.

: 중첩된 ArrayList로 구현

: ArrayList<Integer>를 요소로 삼는 ArrayList.

• 생성자

: 매개변수 없이 새로운 리스트 객체 생성

• setter

: 버텍스의 수만큼 필드1에 ArrayList<Integer>객체 할당

: 버텍스 수 만큼 공간 생성.

• getter

: 필드1 주소값 반환

• addEdge

: 버텍스에 엣지의 정보를 저장(연결점을 저장)

: 두 개의 인자(vertex1, vertex2)를 제공받음

: vertex1, vertex2가 음수거나, 기존 리스트의 크기(버텍스 수)보다 크면 종료

: vertex1의 list에 vertex2 값을 할당 (양방향은 2->1 값도 할당)

• hasEdge

: 버텍스에 엣지가 있는지 확인하는 메서드

: 두 개의 인자(vertex1, vertex2)를 제공받음

: vertex1, vertex2가 음수거나, 기존 리스트의 크기(버텍스 수)보다 크면 종료

: vertex1에 vertex2가 있는지 contains 메서드로 확인

• removeEdge

: 버텍스에 존재하는 엣지를 제거하는 메서드

: 두 개의 인자(vertex1, vertex2)를 제공받음

: vertex1, vertex2가 음수거나, 기존 리스트의 크기(버텍스 수)보다 크면 종료

: vertex1에 vertex2가 있는지 확인하고 있다면, vertex1에서 remove메서드를 호출하여 vertex2를 제거함.