[자료구조] 6장 개념&코드 정리

-인접 행렬

-인접 리스트

-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