그래프
그래프의 탐색 기법
BFS와 DFS 설명 및 코드 직접구현 링크
탐색기법: BFS(너비우선탐색), DFS(깊이우선탐색)
BFS : 주변에 있는 노드를 탐색하며 탐색 범위 확장 (queue활용해서 구현)
DFS : 한쪽방향까지 끝까지 진행 한 후, 나머지 방향도 끝까지 탐색 반복 (stack활용해서 구현)
언제 쓰는가
- 관계가 N:N 관계일떄
스킬트리
유저 -> 친구관계 (서로 여러명과 연결) - 순서가 문제가 아니라 연결이 중요한경우 (정렬이 아닐때)
- 순환이 있을수 있는 구조(트리로 표현못함)
그래프 간단 C# 코드로 예시
BFS.. 이런거는 너무 어렵다.
스킬트리로 각 스킬들을 찍기위한 선행 스킬들을 표현해본 코드
class Skill
{
//스킬이름 (스킬구별을 위해)
public string Name;
//이 스킬을 찍기위해 어떤 스킬들이 필요한지
public List<Skill> requireSkills = new List<Skill>();
public Skill(string name)
{
Name = name;
}
}
class Program
{
static void Main(string[] args)
{
//스킬트리 구조를 그래프로 만들어보고싶다
//스킬트리에 대한 클래스를 먼저 만들자
Skill A = new Skill("A");
Skill B = new Skill("B");
Skill C = new Skill("C");
Skill D = new Skill("D");
//그래프 연결 구조를 설정한다
B.requireSkills.Add(A);
C.requireSkills.Add(A);
D.requireSkills.Add(B);
D.requireSkills.Add(C);
//그래프 연결 구조를 출력하자
PrintConnect(D,new HashSet<string>());
}
//현재 스킬, 방문한 스킬 이름을 저장해서 재귀형식으로 반복 호출
public static void PrintConnect(Skill skill, HashSet<string> visited)
{
//이미 방문한 스킬이면 return
if (visited.Contains(skill.Name)) return;
visited.Add(skill.Name);
//현재 스킬을 찍기위해 어떤 스킬들이 선행되어서 찍혀야하는지 출력
Console.WriteLine($"스킬 {skill.Name}를 배우려면");
if(skill.requireSkills.Count == 0) Console.WriteLine("선행스킬 없음");
else
{
foreach (var item in skill.requireSkills)
{
Console.WriteLine($"- {item.Name}");
}
}
//상위 스킬들도 접근해서 정보를 얻어옴
foreach(var item in skill.requireSkills)
{
PrintConnect(item, visited);
}
}
}결과
스킬 D를 배우려면
- B
- C
스킬 B를 배우려면- A
스킬 A를 배우려면
선행스킬 없음
스킬 C를 배우려면- A
트리
+정렬에 사용한다(이진 정렬)
코드
출력을 오름차순으로 정렬된 형식으로 출력, 중간에 값이 입력되어도 자동으로 정렬된다
namespace Test2
{
//트리 노드 하나, 클래스로 정의
public class TreeNode
{
public int Value; //노드값
public TreeNode Left; //왼쪽에 뭐있는지 (오른쪽보다 작은수 들어감)
public TreeNode Right; //오른쪽 노드 (왼쪽보다 큰수 들어감)
public TreeNode(int value)
{
Value = value;
}
}
//트리를 관리하는 클래스
public class BinaryTree
{
//부모 노드 정보
public TreeNode Root;
public void Insert(int value)
{
Root = InsertRecursive(Root, value);
}
public TreeNode InsertRecursive(TreeNode node, int value)
{
//(초기 1회) 부모노드가 없다면 부모노드를 만들어줌
if (node == null) return new TreeNode(value);
//계속 작은값이 들어와도 재귀로 인해 왼쪽에 붙음
if (value < node.Value) node.Left = InsertRecursive(node.Left, value);
else if (value > node.Value) node.Right = InsertRecursive(node.Right, value);
return node;
}
//출력(재귀형식으로 오름차순으로 출력됨)
public void PrintInOredr(TreeNode node)
{
if (node == null) return;
PrintInOredr(node.Left);
Console.Write(node.Value + " ");
PrintInOredr(node.Right);
}
}
class Program
{
static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.Insert(5);
tree.Insert(3);
tree.Insert(7);
tree.Insert(1);
tree.Insert(4);
tree.PrintInOredr(tree.Root);
}
}
}
결과 : 1 3 4 5 7
그래프와 트리의 차이
| 구분 | 그래프(Graph) | 트리(Tree) |
|---|---|---|
| 구조 | 비계층적 | 계층적 |
| 방향 | 방향/무방향 모두 가능 | 부모 → 자식 단방향 |
| 사이클 | 순환 구조 허용 | 사이클 없음 |
| 연결성 | 비연결 노드도 표현 가능 | 항상 연결됨 |
| 간선 수 | 제한 없음 | 노드 수 - 1 |
| 경로 | 두 노드 간 여러 경로 가능 | 두 노드 간 유일한 경로만 존재 |
