무엇을 정점과 간선으로 삼는가
교통망에서 정점은 정류장, 간선은 이동 가능한 구간으로 정할 수 있다. 다른 문제에서는 작업을 정점으로, 먼저 끝나야 한다는 의존 관계를 간선으로 표현한다. 같은 그림이라도 간선의 의미가 다르면 해결할 질문도 달라진다.
한 방향으로만 성립하는 관계에는 방향 간선을 사용한다. 거리나 비용을 간선의 가중치로 저장할 수도 있다. 단순히 연결 여부만 알면 되는 문제와 최소 비용 경로를 찾는 문제는 필요한 정보가 다르다.
리스트와 행렬의 차이
인접 리스트는 각 정점에서 연결된 이웃을 모아 저장한다. 간선이 상대적으로 적은 그래프에서는 필요한 연결만 저장하여 공간을 줄일 수 있다. 특정 두 정점이 직접 연결됐는지 확인하는 비용은 구체적인 구현에 따라 달라진다.
인접 행렬은 정점 쌍마다 칸을 둔다. 정점이 n개라면 기본적인 행렬은 n²개의 칸이 필요하지만 특정 쌍의 연결 여부를 바로 확인하기 쉽다. 한 방식이 모든 그래프와 연산에서 더 좋은 것은 아니다.
순환이 있는 관계를 탐색하기
너비 우선 탐색은 시작점에서 가까운 단계부터 확장하고, 깊이 우선 탐색은 한 경로를 따라 더 들어갔다가 되돌아온다. 순환이 있는 그래프에서는 방문 상태를 관리하여 같은 위치를 불필요하게 반복하지 않도록 한다.
가중치가 모두 같은 경우 너비 우선 탐색으로 간선 수가 가장 적은 경로를 찾을 수 있다. 가중치가 제각각이면 같은 절차가 최소 비용을 보장하지 않는다. 알고리즘의 가정과 데이터의 조건을 맞춰야 한다.
관계 모델의 경계 조건
자기 자신으로 향하는 간선이나 같은 두 정점 사이의 여러 간선을 허용할지 정해야 한다. 무방향 그래프의 인접 리스트는 하나의 연결을 양쪽 정점에서 기록하는 구현이 흔하다.
저장된 간선의 개수와 실제 관계의 개수를 혼동하지 않도록 표현 규칙을 명시해야 한다. 그래프 분석의 결과는 원래 문제를 어떤 규칙으로 모델링했는지에 영향을 받는다.