안 쓰던 블로그

그래프 순회=그래프 탐색: 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산 깊이 우선vs너비 우선 깊이 우선 탐색 순회 방법 -시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 갈 곳이 없을 때, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하는 식 -가장 마지막에 만났던 갈림길 간선의 정점으로 돌아가야 하기 때문에 후입선출 구조 스택을 사용한다 구현 1. visited라는 방문 체크 배열을 전부 false(하나도 방문하지 않은 상태)로 초기화 2. 스택 생성 3. visited[v]=true; 시작하는 첫번째 위치는 방문했다고 표시 4. 스택이 empty가 아닐 때까지, 현재 노드의 인..

그래프 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 그래프 G는 객체를 나타내는 정점(V)와 객체를 연결하는 간선(E)의 집합이다 G=(V,E) 종류 무방향 그래프 두 정점을 연결하는 간선에 방향이 없는 그래프 (Vi, Vj)로 표현한다 V정점은 ABCD E간선은 AB, AD, BC, BD ,CD 방향이 없음 방향 그래프 =다이그래프 간선에 방향이 있는 그래프 Vi->Vj를 로 표현한다 는 A->B 는 B->C 완전 그래프 각 정점에서 다른 모든 정점이 연결된, 최대로 많은 간선 수를 가진 그래프 정점이 n개인 무방향 그래프에서 최대 간선 수: n(n-1)/2개 정점이 n개인 방향 그래프에서 최대 간선 수: n(n-1)개 G5의 간선 수: 정점의 개수는 4개고 무방향 그래프이므로 완전 그래..