그래프란

G(V,E)로 G는 Grahp, V는 Vertex(꼭지점), E는 Edge(가장자리)로 표현하며 그래프는 Vertex와 Edge로 이루어진 집합이라 의미이다.

무방향 그래프(=양방향 그래프)

다음 그림과 같은 그래프가 존재할 때 무방향 혹은 양방향 그래프라고 한다.
해당 그래프를 표로 그려내면

다음과 같이 그려낼 수 있고 이 표를 그대로 2차원 배열로 이용하여 사용할 수도 있다.

방향 그래프

방향 그래프란 무방향(양방향) 그래프와는 조금 다르게 노드가 진행할 수 있는 방향이 정해져있는 그래프를 말한다. 해당 그래프도 표로 나타낼 수 있다.

그래프로 나타내면 다음과 같으며 2차원 배열을 검사했을 때 해당 인덱스의 값이 1이라면 진행할 수 있다는 것이다.

가중치 방향 그래프

가중치 방향 그래프란 노드에서 진행할 때 진행 여부와 진행할때 필요한 비용 값이다. 이 또한 표로 나타낼 수 있는데

다음과 같이 1로 진행할 수 있는 여부를 판단하는 것이 아닌 비용 값을 넣어줌으로써 비용 값이 있다면 진행할 있고 해당 비용만큼을 낼수 있는지 판단할 수도 있다.

그래프와 인접 그래프에 대한 개념 정리