-인접 행렬
-인접 리스트
-DFS / BFS
-이중결합요소 : 단절점 찾기
-최소 비용 신장 트리 : kruskal, prim, sollin
-최단 경로 : shortestpath / BellmanFord 알고리즘, all-paires shortest path
그래프 G : 2개 집합 V(vertex:정점)와 E(edge:간선)로 구성
무방향 그래프 (undirected graph)
방향 그래프 (directed graph) //정점 표시 순서 존재
차수 : 정점에 부속한 간선 수
in-degree / out-degree
그래프 표현 방법
1) 인접 행렬
G=(V,E)는 정점의 수가 n인 그래프 => n*n의 2차원 배열
수행 시간 : O(n^2) //각 행마다 노드 개수만큼 check해야함
2) 인접 리스트
인접 행렬의 n행들을 n개의 연결리스트로 표현 => data, link 필드
Chain<int> *adjList;
LinkedGraph(const int vertices=0) ; n(vertices), e(0)
{adjList=new Chain<int>[n];} //n개 linked list로 선언
무방향 그래프의 경우, n개 노드 => 2e개 리스트 노드 필요
방향 그래프의 경우, n개 노드 => e개 리스트 노드 필요
3) 인접 다중 리스트
4) 가중치 간선 => 네트워크 : 가중치 간선을 가진 그래프
그래프 기본 연산
-DFS
-BFS
+ 연결요소
-신장 트리 => DFS/BFS
=> 단절점 찾기
-최소비용 신장트리 알고리즘 3가지 => 비용관점
+최단 경로 (shortest path)
그래프 기본 연산
- 깊이-우선 탐색 (DFS : Depth-First Search)
-깊이-우선 탐색 (DFS : Depth-First Search) //Stack 사용 : 선입후출
출발 정점 v 방문
v에 인접 & 미방문 정점 w 택
w에 인접 & 미방문 정점 택 => 반복
모든 인접 방문을 방문한 정점 u에 도달 => 최근 방문한 정점 중 미방문 정점과 인접해있는 정점으로 되돌아감
다시 깊이 우선 탐색 시작
방문한 정점들로부터 방문하지 않은 정점으로 더 이상 못 갈 때 종료
virtual void Graph::DFS() // Driver
{
visited = new bool [n]; // visited is declared as a bool* data member of Graph
fill (visited, visited + n, false); //초기화
DFS(0); // start search at vertex 0
delete [] visited;
}
virtual void Graph::DFS(const int v) // Workhorse
{// Visit all previously unvisited vertices that are reachable from vertex v.
visited [v] = true; //방문 처리
cout << v << “ “;
for (each vertex w adjacent to v) // actual code uses an iterator
if(!visited[w]) DFS(w);
}
- 너비-우선 탐색 (BFS : Breadth-First Search)
시작 정점 v 방문 //Queue 사용 : 선입선출
v에 인접한 모든 정점 방문 => queue => 하나씩 front(), pop() => 선입 선출됨
새롭게 방문한 정점들에 인접 & 미방문 정점들 방문
virtual void Graph::BFS(int v)
// 너비-우선 탐색은 정점 v에서부터 시작한다.
// v 방문시 visited[v]는 true 로 설정된다. 이 함수는 큐를 이용한다.
{
visited = new bool [n]; .
fill(visited, visited + n, false);
visited[v] = true; cout << v << “ “; // 출력도 해보자.
Queue<int> q;
q.Push(v);
while (!q.IsEmpty()) {
v = q.Front();
q.Pop();
for (v에 인접한 모든 정점 w에 대해) // 실제 코드는 반복자를 사용
if (!visited[w])
{
q.Push(w);
visited[w] = true; cout << v << “ “; // 출력도 해보자.
}
} // while 루프의 끝
delete [] visited;
}
+연결 요소 (connected component) => DFS/BFS와 합치게 됨
: 방문하지 않은 정점 v에 대해 DFS(v) or BFS(v) 반복 호출로 도출
virtual void Graph::Components()
// 그래프의 연결요소들을 결정
{
// visited는 Graph의 bool* 데이타 멤버로 선언되었다고 가정.
visited = new bool[n];
fill(visited, visited+n, false);
for(i=0; i<n; i++)
if(!visited[i]){
DFS(i); // 연결 요소를 탐색
OutputNewComponent();
}
delete [] visited;
}
Spaning Tree : 신장 트리
g의 간선들로만 구성되면서 g의 모든 정점을 포함한 트리
-깊이-우선 신장트리(depth-first spanning tree)
-너비-우선 신장트리(breadth-first spanning tree)
이중결합요소
단절점 (articulation point) : 말 그대로 해당 정점에 연결된 간선이 모두 삭제될 경우 그래프 단절 발생하는 점
이중결합 그래프 : 단절점 없는 그래프
이중결합요소 : 단절점 없는 그래프의 가장 큰 부분 그래프
=> 이중결합 요소 도출에 DFS 사용
-back edge : u가 v의 조상이거나 v가 u의 조상인 비트리 간선
-cross edge : 비트리 간선 중 back edge가 아닌 것
dfn# : 깊이-우선 탐색의 순서
low(w) : 후손들과 최대 하나의 백간선을 통해 갈 수 있는 가장 작은 dfn#
=> articulation point
1) 정점 u : 2개 이상의 자식을 가진 경우 신장트리 루트
2) root가 아니면서 low(w)>=dfn(u)인 u
최소비용신장트리
-kruskal algorithm
-prim algorithm
-sollin algorithm
최단 경로(shortest path)
1)단일 출발점 & 음이 아닌 간선 비용
출발정점 v에서 G의 모든 다른 정점까지의 최단 경로 구하기
ShortestPath함수 정의
void MatrixWdigraph::ShortestPath(const int n, const int v)
{
// dist[j](0<=j<n) : 최단 경로 길이로 설정됨.
// length[i][j] : 간선의 길이
for (int i = 0; i < n; i++)
{ s[i] = false; dist[i] = length[v][i]; } // 아직 모두 방문한 적 없으므로 초기화 F
s[v] = true; //s는 이미 최단 경로가 발현된 정점들의 집합임
dist[v] = 0; //시발점~s의 정점들만을 거쳐 v까지 가는 최단 경로
for (i=0; i<n-2; i++)
{ // 정점 v로부터 n-1개 경로를 결정
int u = Choose(n); // choose returns a value u such that:
// dist[u] = minimum dist[w], where s[w]=false
s[u] = true;
for (int w=0; w<n; w++)
if(!s[w] && dist[u] + length[u][w] < dist[w])
dist[w] = dist[u] + length[u][w];
//아직 방문 안한 정점 & 해당 정점을 거쳐가는 길이가 더 적다면 change
} // end of for (i=0; ...)
}
=> 음수인 경우, 최단 거리 도출이 안됨
2) 단일 출발점/모든 종점 (음수 가능)
Ballman과 Fold 알고리즘
void MatrixWDigraph::BellmanFord(const int n, const int v)
{
// Single source all destination shortest paths with negative edge lengths.
for(int i=0; i<n; i++)
dist[i] = length[v][i]; // dist 초기화
for(int k=2; k<=n-1; k++)
for(each u such that u != v and u has at least one incoming edge)
for(each <i,u> in the graph)
if(dist[u]>dist[i]+length[i][u]) dist[u] = dist[i] + length[i][u];
}
3) All-pairs Shortest Path
'학교 > 자료구조' 카테고리의 다른 글
[자료 구조] 7장 (0) | 2023.06.08 |
---|---|
[자료구조] 6장 실습 kruskal, prim, sollin (0) | 2023.06.06 |
[자료구조] 5장 실습 코드 정리 : sets (0) | 2023.06.04 |
[자료구조] 5장 실습 코드 정리 : BT, BST(hw3) (0) | 2023.06.04 |
[자료구조] 5장 tree 코드 (0) | 2023.06.03 |