Module 13 - Introduction to Graph Algorithms

graph 란? linked list , binary tree 도 전부 그래프이다 

• Order = vertex 의 개수 그림에선 5개
• Size = edge 개수, 그림에서 6개
• Degree = 그 vertex 로 이어지는 edge 의 개수 A = 3 

• 두 점끼리 방향 없이 이어짐 = path 
• path 가 vertex 를 반복하지 않으면 simple path 라고 부름 

• Dense = 그래프가 거의 maximum edges 일때
• Sparse = 그래프가 거의 minimum edges 일때

그래프가 self loop 이나 같은곳으로 가는게 두개 이상이면 NON- simple graph 그렇지 않으면 simple graph 이다 

acyclic = tree

Depth-First Search (DFS) Introduction

 

 

• We have to visit each vertex.
• We have to consider all edges.
• efficiency for DFS = O(|V|+|E|

스택의 개념이 굉장히 중요

근처 로 넘어갈때 두개하면 하나만 pop 하고 넘어가야함 그래서 1 과 이어진 2,3 중에 2는 stack 에 제일 아래에 남다가 마지막에 출력

Breadth-First Search (BFS) Introduction

uses queue instead of stack

근처 vertex 를 queue 에 넣고 추가 후 삭제 deque

단계별로 내려가는데 길이 하나인것 부터 하고 두개면 다른것과 연결되있는지 확인

• A 에서 B H 
• B 가 일단 갈곳이 하나니까 C
• H 는 갈곳이 두개지만 C 와도 연결되있는 I 
• I 에서 갈곳 하나인 G, F 
• F 에서 갈곳이 두개지만 C 와도 연결되있는 D
• 마지막 E

 

언제 뭐를 쓸까?

1. Begin with an easy question. Do we have any prior knowledge of what vertex that is being searched for and its location in the graph relative to the starting point? If it is known that the vertex is relatively close by compared to the size of the graph, then we may prefer to use BFS.
2. How "deep" is the graph? For example, if we are doing a traversal of a tree from some root node and the depth of the tree is large, then we may want to use BFS to avoid staying on a single path for a long time. Or we could impose some sort of depth limit on DFS traversal if the graph is infinitely large.
3. How "wide" is the graph / how large is the branch factor? If each node has many neighbors, then a BFS will quickly blow up in space usage since we need to store all of these neighbors in a queue. This is particularly important in areas like AI where the graph we're considering is essentially infinitely large because our agent's decision space is very large.