그래프(Graph)
정점과 간선으로 이루어진 자료구조(Cyclic)
-> 연결된 정점간의 관계를 표현할 수 있는 자료 구조
용도 : 지하철 노선도, 통신 네트워크 등등
예시1은 무방향 그래프이고, 예시2는 방향 그래프
무방향 그래프는 간선에 방향이 없는 그래프로 양방항 이동 가능
-> 정점 AB 간선의 표현 : (A,B) = (B,A)
방향 그래프는 간선에 방향이 있는 그래프로 해당 방향으로만 이동 가능
-> 정점 A -> B 간선의 표현 : <A,B> != <B,A>
- 정점(Vertex) : 각 노드
- 간선(Edge) : 노드와 노드를 연결하는 선
- 인접 정점(Adjacent vertex) : 간선 하나를 두고 바로 연결된 정점
- 점점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
-> 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배 - 진입 차수(In-degree) : 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수(Out-degree) : 방향 그래프에서 외부로 나가는 간선의 수
- 경로 길이(Path length) : 경로를 구성하는데 사용된 간선의 수
- 단순 경로(Simple Path) : 경로 중에서 반복되는 정점이 없는 경우
- 사이클(Cycle) : 단순 경로의 시작과 끝 정점이 동일한 경우
- 가중치 그래프 : 간선에 값이 있는 그래프
(이동 비용) - 완전 그래프 :
모든 정점이 서로 연결되어 있는 그래프, 이때 정점이 N개라면 -> 간선의 수는n(n-1) / 2
DFS
깊이 우선 탐색(Depth First Search) : 각 노드에 방문했는지 여부를 체크할 배열과 스택 이용하여 구현
-> 각 노드를 한번씩 탐색하면서 모든 노드 탐색
BFS
너비 우선 탐색(Breath First Search) : 각 노드에 방문했는지 여부를 체크할 배열과 큐를 이용하여 구현
그래프 구현방식
방법 1 : 인접 행렬
인접 행렬(Adjacency Matrix)를 통한 구현 -> 2차원 배열 이용
인접 행렬 사용 시 간선 정보의 확인과 업데이트가 빠름(O(1))
-> 하지만 인접 행렬을 위한 메모리 공간을 차지
방법 2 : 연결리스트 이용(인접 리스트)
인접 행렬을 통해 구현 시 메모리 사용량이 상대적으로 적고, 노드 추가 삭제가 빠름
-> 하지만 간선 정보 확인이 상대적으로 오래 걸림
인접 행렬 -> 노드의 개수가 적고 간선의 수가 많을 때 유리
인접 리스트 -> 노드의 갯수가 많고 간선의 수가 적을때 유리
인접 행렬을 이용한 그래프 구현해보기
class MyGraphMatrix{
char[] vertices;
int[][] adjMat;
int elemCnt;
public MyGraphMatrix(){};
public MyGraphMatrix(int size){
this.vertices = new char[size];
this.adjMat = new int[size][size];
this.elemCnt = 0;
}
public boolean isFull(){
return this.elemCnt == this.vertices.length;
}
public void addVertex(char data){
if(isFull()){
System.out.println("Graph is full!");
return;
}
this.vertices[this.elemCnt++] = data;
}
public void addEdge(int x, int y){
this.adjMat[x][y] = 1;
this.adjMat[y][x] = 1; // 무방향 그래프 이기 때문
}
public void addDirectedEdge(int x, int y){
this.adjMat[x][y] = 1; // 방향 그래프인 경우
}
public void deleteEdge(int x, int y){
this.adjMat[x][y] = 0;
this.adjMat[y][x] = 0;
}
public void deleteDirectedEdge(int x, int y){
this.adjMat[x][y] = 0;
}
public void printAdjacentMatrix(){
System.out.print(" ");
for(char item : this.vertices){
System.out.print(item + " ");
}
System.out.println();
for (int i = 0; i < this.elemCnt; i++) {
System.out.print(this.vertices[i] + " ");
for(int j = 0; j < this.elemCnt; j++){
System.out.print(this.adjMat[i][j] + " ");
}
System.out.println();
}
}
}
public class Main {
public static void main(String[] args) {
MyGraphMatrix graph = new MyGraphMatrix(4);
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,2);
graph.addEdge(1,3);
graph.addEdge(2,3);
graph.printAdjacentMatrix();
}
}
인접 리스트를 이용한 그래프 구현
class Node{
int id;
Node next;
public Node(int id, Node next) {
this.id = id;
this.next = next;
}
}
class MyGraphList{
char[] vertices;
Node[] adjList;
int elemCnt;
public MyGraphList(){};
public MyGraphList(int size){
this.vertices = new char[size];
this.adjList = new Node[size];
this.elemCnt = 0;
}
public boolean isFull(){
return this.elemCnt == this.vertices.length;
}
public void addVertex(char data){
if(isFull()){
System.out.println("Graph is full!");
return;
}
this.vertices[elemCnt++] = data;
}
public void addEdge(int x, int y){
this.adjList[x] = new Node(y, this.adjList[x]);
this.adjList[y] = new Node(x, this.adjList[y]);
}
public void addDirectedEdge(int x, int y){
this.adjList[x] = new Node(y, this.adjList[x]);
}
public void printAdjacentList(){
for (int i = 0; i < this.elemCnt; i++) {
System.out.print(this.vertices[i] + ": ");
Node cur = this.adjList[i];
while(cur != null){
System.out.print(this.vertices[cur.id] + " ");
cur = cur.next;
}
System.out.println();
}
}
}
public class Main {
public static void main(String[] args) {
MyGraphList graph = new MyGraphList(4);
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,2);
graph.addEdge(1,3);
graph.addEdge(2,3);
graph.printAdjacentList();
}
}
인접 행렬 그래프의 DFS, BFS
class MyGraphMatrix2 extends MyGraphMatrix{
public MyGraphMatrix2(int size){
super(size);
}
public void dfs(int id){
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
stack.push(id);
visited[id] = true;
while(!stack.isEmpty()){
int curId = stack.pop();
System.out.print(this.vertices[curId] + " ");
for(int i = this.elemCnt-1; i >= 0; i--){
if(this.adjMat[curId][i] == 1 && visited[i] == false){
stack.push(i);
visited[i] = true;
}
}
}
System.out.println();
}
public void bfs(int id){
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while(!queue.isEmpty()){
int curId = queue.poll();
System.out.print(this.vertices[curId] + " ");
for(int i = this.elemCnt - 1; i >= 0 ; i--){
if(this.adjMat[curId][i] == 1 && visited[i] == false){
queue.offer(i);
visited[i] = true;
}
}
}
System.out.println();
}
}
public class Practice1 {
public static void main(String[] args) {
MyGraphMatrix2 graph = new MyGraphMatrix2(7);
graph.addVertex('A');
graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');
graph.addVertex('E');graph.addVertex('F');graph.addVertex('G');
graph.addEdge(0,1);graph.addEdge(0,2);graph.addEdge(0,3);
graph.addEdge(1,4);graph.addEdge(2,5);graph.addEdge(3,4);graph.addEdge(3,5);
graph.addEdge(4,6);graph.addEdge(5,6);
graph.printAdjacentMatrix();
System.out.println();
graph.dfs(0);
graph.bfs(0);
}
}인접 리스트 그래프의 DFS, BFS
class MyGraphList2 extends MyGraphList{
public MyGraphList2(int size){
super(size);
}
public void dfs(int id){
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
stack.push(id);
visited[id] = true;
while(!stack.isEmpty()){
int curId = stack.pop();
System.out.print(this.vertices[curId] + " ");
Node cur = this.adjList[curId];
while(cur != null){
if(visited[cur.id] == false){
stack.push(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
System.out.println();
}
public void bfs(int id){
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
queue.offer(id);
visited[id] = true;
while(!queue.isEmpty()){
int curId = queue.poll();
System.out.print(this.vertices[curId] + " ");
Node cur = this.adjList[curId];
while(cur != null){
if(visited[cur.id] == false){
queue.offer(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
System.out.println();
}
}연습 문제
문제1
// Practice1
// Center Node 찾기
// Undirected 그래프에서 center node 를 출력하세요.
// Center node 는 다른 모든 노드와 연결된 노드를 의미
// 다른 모드와 연결된 노드는 하나라고 가정
// 입력 그래프: {{1, 2}, {2, 3}, {4, 2}}
// 출력: 2
// 입력 그래프: {{1,2}, {5,1}, {1,3}, {1,4}}
// 출력: 1
public class Practice1 {
public static int solution(int[][] e) {
MyGraphMatrix graph = new MyGraphMatrix(e.length + 1); // 간선 갯수 + 1
for (int i = 0; i < e.length; i++) {
graph.addEdge(e[i][0] - 1, e[i][1] - 1);
}
int[] edgeCnt = new int[e.length + 1];
for (int i = 0; i < graph.adjMat.length; i++) {
for (int j = 0; j < graph.adjMat[i].length; j++) {
if (graph.adjMat[i][j] == 1) {
edgeCnt[i] += 1;
}
}
}
int maxCnt = -1;
int maxIdx = -1;
for (int i = 0; i < edgeCnt.length; i++) {
if (maxCnt < edgeCnt[i]) {
maxCnt = edgeCnt[i];
maxIdx = i;
}
}
return maxIdx + 1;
}
public static int solution2(int[][] e) {
// 간선의 총 개수는 노드의 개수 - 1
// 모든 노드는 연결되어 있는 경우
return e[0][0] == e[1][0] || e[0][0] == e[1][1] ? e[0][0] : e[0][1];
}
public static void main(String[] args) {
// Test code
int[][] edges = {{1, 2}, {2, 3}, {4, 2}};
System.out.println(solution(edges));
System.out.println(solution2(edges));
System.out.println();
edges = new int[][]{{1,2}, {5,1}, {1,3}, {1,4}};
System.out.println(solution(edges));
System.out.println(solution2(edges));
}
}문제2
public class Practice2 {
public static void solution(int n, int[][] edges, int source, int dest) {
MyGraphList graph = new MyGraphList(n);
for (int i = 0; i < n; i++) {
graph.addVertex(i);
}
for (int i = 0; i < edges.length; i++) {
graph.addEdge(edges[i][0], edges[i][1]);
}
ArrayList<Integer> visitedItem = new ArrayList();
dfs(graph, 0, visitedItem);
if (visitedItem.contains(source) && visitedItem.contains(dest)) {
System.out.println("true");
} else {
System.out.println("false");
}
}
public static void dfs(MyGraphList graph, int id, ArrayList<Integer> visitedItem) {
boolean[] visited = new boolean[graph.vertices.length];
Stack<Integer> stack = new Stack<>();
stack.push(id);
visited[id] = true;
while (!stack.isEmpty()) {
int curId = stack.pop();
// 출력 대신 list에 추가
visitedItem.add(curId);
Node cur = graph.adjList[curId];
while (cur != null) {
if (visited[cur.id] == false) {
stack.push(cur.id);
visited[cur.id] = true;
}
cur = cur.next;
}
}
}
public static void main(String[] args) {
// Test code
int n = 3;
int[][] edges = {{0, 1}, {1, 2}, {2, 0}};
int source = 0;
int dest = 2;
solution(n, edges, source, dest);
n = 6;
edges = new int[][]{{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}};
source = 0;
dest = 5;
solution(n, edges, source, dest);
}
}문제 3
// Practice3
// 주어진 그래프를 두 개의 그래프로 분리할 수 있는지 확인 하는 프로그램을 작성하세요.
// 분리 조건: 인접하지 않은 노드끼리 분리
// 모든 노드는 연결되어 있다.
// 분리 가능하면 true, 불가능하면 false 출력
// 예시 입력)
// 그래프: {{1, 3}, {0, 2}, {1, 3}, {0, 2}} : 0이 1과 3에 연결 ~~~~
// 출력: true
// 그래프: {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}}
// 출력: false
public class Practice3 {
public static void solution(int[][] graph) {
int[] flags = new int[graph.length];
if (checkSplit(graph, flags, 1, 0) == true) {
System.out.println("true");
} else {
System.out.println("false");
}
}
public static boolean checkSplit(int[][] graph, int[] flags, int flag, int node) {
if (flags[node] != 0) {
return flags[node] == flag;
}
flags[node] = flag;
for (int adjacentNode : graph[node]) {
if (!checkSplit(graph, flags, -flag, adjacentNode)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
// Test code
int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
solution(graph);
graph = new int[][]{{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
solution(graph);
}
}
추가 개념
에지 리스트(Edge List)
에지를 중심으로 그래프 표현
-> 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현
-> 가중 치가 있는 경우에는 출발노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지 표현
방향이 없는 그래프라면 [1,2][2,1] 은 같은 표현
방향이 없다면 Start,End 느낌으로 넣지말고
[1,2][1,3] 이렇게 넣었다면 [1,2]가 [2,1]을 내포한다 가정
-> [1,2]를 꺼냈을때는 양쪽으로 검사해보자(1 -> 2, 2-> 1)
-> Start, End 로 다 넣어도됨 ([1,2], [2,1])
Start,End로 넣는 것이 더 편하긴 함
-> ex) 양쪽 방향이 있는 경우까지 대비할 수 있기 때문에
가중치가 있으면 행을 3개로 늘려서 진행하면 됨
이렇게 엣지 리스트를 구성하였을 때, 만약 특정 노드와 관련되어 있는 에지를 탐색하기가 쉽지 않음(이때는 사용 X)
-> 엣지 리스트는 보통 벨만 포드나, 크루스칼 알고리즘에 사용하고, 노드 중심 알고리즘에는 사용하지 않음
-> 위는 엣지를 기준으로 알고리즘이 돈다
인접 행렬
노드가 N개라면 N x N으로 행렬을 표현
1을 저장하는 이유는 가중치가 없기 때문
인접 행렬을 이용한 그래프 구현은 쉬움
-> 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면서 바로 확인할 수 있는 것도 장점
-> 하지만 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을때는 공간 효율성이 떨어짐
-> 또한 노드의 개수가 많은 경우에 아예 2차원 배열 선언 자체를 할수 없는 결함또한 존재
ex) 노드가 3만개가 넘으면 자바 힙 스페이스 에러 발생
예를들어 2번 노드와 관련된 탐색을 한다고 할때
-> A[2][N] 일때 N은 1~N까지 탐색해야 함(BigO 기준)
-> A[2][1] = 0, A[2][2] = 0..........
인접 리스트
ArrayList로 그래프 표현
-> 그래프 문제는 노드 중심으로 도는 경우가 많음
-> 제일 많이 사용
ArrayList< Integer >[5] 처럼 배열로 선언!!
-> 이는 가중치가 없을떄!!
위 구조가 가장~ 많이 사용하는 구조
-> 코테에선 왠만해서 가중치가 존재
위와 차이점은 Node 리스트를 만듬!
-> 가중치가 있을땐 클래스로 넣어주어야 함(Node 클래스 직접 구현)
위 구조는 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어남
-> 아까 인접행렬을 쓸데 없는 공간(0)까지 탐색해야했음
Journey for Backend Developer