그래프

그래프

• 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현한다.
• 정점(Vertex) : 그래프의 구성요소로 하나의 연결점
• 간선(Edge) : 두 정점을 연결하는 선
• 차수(Degree) : 정점에 연결된 간선의 수
• 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조
  • V: 정점의 개수, E: 그래프에 포함된 간선의 개수
  • V개의 정점을 가지는 그래프는 최대 V * (V-1)/2 간선이 가능
  • 예> 5개 정점이 있는 그래프의 최대 간선 수는 10(==>5 * 4/2)개 이다.
• 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N관계를 가지는 원소들을 표현하기 용이하다.

그래프 종류

• 무향 그래프 (방향 X , 양방향)
• 유향 그래프 (방향 O)
• 가중치 그래프
• 사이클 없는 방향 그래프
• 완전 그래프 : 정점들에 대해 가능한 모든 간서들을 가진 그래프
• 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
• 트리도 그래프이다
  • 각 노드는 최대 하나의 부모 노드가 존재할 수 있다.
  • 각 노드는 자식 노드가 없거나 하나 이상이 존재할 수 있다.
  • 두 노드 사이에는 유일한 경로가 존재한다.

인접 정점

• 인접 : 두개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다. 완전 그래프에 속한 임의의 두 정점들은 서로 인접해 있다.

그래프 경로

• 경로란 어떤 정점 A에서 시작하여 다른 정점 B로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것.
  • 어떤 정점에서 다른 정점으로 가는 경로는 여러가지일 수 있다.
• 단순경로
  • 시작정점과 끝 정점을 제외하고 중복된 정점이 없는 경로
• 싸이클
  • 경로의 시작 정점과 끝 정점이 같음

그래프 표현

• 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정
  1. 인접행렬
  • V * V 크기의 2차원 배열을 이용해서 간선 정보를 저장
  • 배열의 배열 2. 인접 리스트
  • 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장 3. 간선 리스트
  • 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장

1. 인접행렬

• 두 정점을 연결하는 간선의 유무를 행렬로 표현
• V * V 정방 행렬
• 행 번호와 열 번호는 그래프의 정점에 대응
• 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현
• 무향 그래프
  • i번째 행의 합 = i번째 열의 합 = Vi의 차수
• 유향 그래프
  • 행 i의 합 = Vi의 진출 차수
  • 열 i의 합 = Vi의 진입 차수
• 정점이 어느정도 있고, 간선도 꽤 있을 때.
• 메모리 사용량이 높고 시간이 많이 걸린다.
• 희소그래프일때는 시간상 유리하지 않지만 밀집 그래프일때는 인접행렬료 표현하는게 더 편리하다.

2. 인접리스트

• 각 정점에 대한 인접정점들을 순차적으로 표현
• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장
• 인접한 애들만 확인할 수 있긴 때문에 희소그래프일 경우 이 방법이 훨씬 유리하다.
• 밀집그래프는 인접행렬이든 인접리스트든 차이가 없다.
• 각 헤드 정점들은 노드타입의 리스트로 관리
• 무향 그래프 노드 수 = 간선의 수 * 2
• 각 정점의 노드 수 = 정점의 차수
• 방향 그래프 노드 수 = 간선의 수
• 각 정점의 노드 수 - 정점의 진출 차수
• 각 정점의 인접한 노드들의 순서가 상관 없기 때문에 노드의 꼬리 부분을 찾아 줄 필요 없이 앞부분에 노드를 추가 해주면 된다.
• 공간복잡도 측면이나 비교연산에서 유리한 점이 있다.
• 단, 정점이 어느정도되고 , 간서도 많을때는 별로 이익이없다.

3. 간선리스트

• 두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장

• 간선을 표현하는 두 정점의 정보를 나타냄(시작 정점, 끝 정점)

• 인접행렬과 인접리스트 : 정점을 중심으로 해결해야 하는문제들
• 간선리스트 : 간선정보를 하나하나 처리해 가면서 해결해야 하는 문제들

문제 제시 : 친구 관계(다대 다 관계)

• A의 친구는 E,G,J이고 E의 친구는 A,D,H이다.
• (D-E),(F-G),(N-B,I,L),(G-A,C,D,H),(I-J,H),(B-D,I,K,L),(M-I,J),(E-A,H),(C-B,I,L),(J-A,G)
• A의 친구 중에 친구가 가장 많은 친구는 누구이고 몇 명(A포함)인가?

그래프탐색(순회)

• 그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것을 의미한다.
• 두가지 방법
  • 너비 우선 탐색(BFS)
  • 깊이 우선 탐색(DFS)

BFS(Breadth First Search)

• 너비우선탐색은 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함.

BFS(G,v) //그래프 G, 탐색 시작 정점 v
	큐 생성
	시작 정점 v를 큐에 삽입
	정점 v를 방문한 것으로 표시
	while(큐가 비어 있지 않은 경우){
		t<- 큐의 첫번째 원소 반환
		for(t와 연결된 모든 간선에 대해){
			u<-t의 인접 정점
			u가 방문하지 않은 곳이면,
			u를 큐에 넣고, 방문한 것으로 표시
		}
	}
end BFS()

• 트리에서는 방문관리를 안해줘도 됐다.(부모가 오직 하나이기 때문에)
• 그래프는 계층형 관계가 아닌 다대다이기 때문에 모든 정점을 한번씩만 가기 위해 방문관리가 필요.

DFS(Depth First Search)

• 시작 점정의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법.
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택 사용.
• 기저조건 : 모든 정점이 방문처리가 이미 되어있을때

G : 그래프
DFS(v) // v: 탐색 정점
	visited[v] <- true // v방문 설정
	FOR each all w in adjacency(G,v)
		IF visited[w] != TRUE
			DSF(w)

인접행렬과 BFS & DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class AdjMatrixTest {
	static int N; //정점 개수
	static boolean[][] adjMatrix; //인접행렬(가중치 없음)
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		adjMatrix = new boolean[N][N];
		int C = Integer.parseInt(in.readLine()); //간선개수
		for(int i=0; i<C; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			adjMatrix[to][from]=adjMatrix[from][to] = true; //무향그래프이기 때문에
			
		}
		System.out.println("===============bfs============================");
		bfs();
		System.out.println();
		System.out.println("===============dfs============================");
		boolean[] visited = new boolean[N];
		dfs(0, visited );
	}
	
	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];
		
		queue.offer(0);
		visited[0] = true;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			System.out.print((char)(current+65) + " ");
			for(int i=0; i<N; i++) {
				if(!visited[i] //미방문
						&& adjMatrix[current][i]) {//인접정점
					queue.offer(i);
					visited[i] = true;
				}
			}
		}
	}
	
	private static void dfs(int current, boolean[] visited) {
		visited[current] = true;
		System.out.print((char)(current+65) + " ");
		
		for(int i=0; i<N; i++) {
			if(!visited[i] && adjMatrix[current][i]) {
				dfs(i, visited);
			}
		}
	}
}

인접리스트와 BFS & DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class AdjListTest {
	static class Node {
		int vertex;
		Node link;

		public Node(int vertex, Node link) {
			this.vertex = vertex;
			this.link = link;
		}

		@Override
		public String toString() {
			return "Node [vertex=" + vertex + ", link=" + link + "]";
		}

	}

	static int N; // 정점 개수
	static Node[] adjList; // 인접 리스트(가중치 없음)

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		adjList = new Node[N];
		int C = Integer.parseInt(in.readLine()); // 간선개수
		for (int i = 0; i < C; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			adjList[from] = new Node(to, adjList[from]);
			adjList[to] = new Node(from, adjList[to]);

		}
		System.out.println("===============bfs============================");
		bfs();
		System.out.println();
		System.out.println("===============dfs============================");
		boolean[] visited = new boolean[N];
		dfs(0, visited);
	}

	private static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N];

		queue.offer(0);
		visited[0] = true;

		while (!queue.isEmpty()) {
			int current = queue.poll();
			System.out.print((char) (current + 65) + " ");
			for (Node temp = adjList[current]; temp != null; temp = temp.link) {
				if (!visited[temp.vertex]) {// 미방문
					queue.offer(temp.vertex);
				visited[temp.vertex] = true;
			}
		}
	}

	}

	private static void dfs(int current, boolean[] visited) {
		visited[current] = true;
		System.out.print((char) (current + 65) + " ");

		for (Node temp = adjList[current]; temp != null; temp = temp.link) {
			if (!visited[temp.vertex]) {// 미방문
				dfs(temp.vertex, visited);
		}
	}
}}