방향 그래프 (Directed Graph)

시작하기 전에

해당 블로그에 작성되는 글은 주인장의 지극히 주관적인 생각이 다수이며, 대부분의 지식은 구글링을 통해 얻고 있기 때문에 옳지않은 정보가 있습니다. 

잘못된 부분이나 수정해야 하는 부분이 있다면 과감히 덧글을 남겨주세요! 모르는게 많은 새싹입니다

오늘의 주제

그래프 중에서도 방향성을 갖는 방향 그래프(Directed Graph)에 대해서 정리를 해놓으려 합니다 :0  요즘 간간히 알고리즘도 다시 풀고 있기 때문에(취준 신세로 돌아왔기 떄문에) 조금이라도 정확히 몰랐던 부분에 대해서는 정리를 하겠습니다.

방향 그래프

방향 그래프는 지금까지 바왔던 그래프와 다르게 정점과 간선사이에 방향성을 띄고 있는 그래프를 말합니다.

정점 A,B에 대해 방향성을 띄고 있고 A->B 의 방향을 갖는 경우 <A,B>로 표시합니다. 여기서 방향성이 들어가기 때문문에 <A,B>와 <B,A>는 다른 의미를 가지게 됩니다. 방향 그래프는 입접 행렬과 인접 리스트를 통해서 표현할 수 있습니다.

예를들어, 다음과 같은인접 행렬(좌측)을 가질 때  정점과 간선의 방향 그래프로 표현할 경우 다음과 같은 그래프(우측)를 갖게 됩니다.

그래프의 탐색시 양방향 그래프인지, 단방향 그래프인지에 따라 코드의 로직이 완전히 달라질 수 있기 때문에 개념에 대해서 확실하게 알고가면 좋을 것 같습니다.

방향 그래프에 대한 알고리즘 문제를 풀어보고 싶으신 분은 링크로 가서 한번 풀어보시면 좋을 것 같습니다.