8.1 그래프 간단 구현

그래프 표현(배열에 기초한 구현)

structure graph: 그래프와 정점 사이의 관계

• vertices(정점 리스트): array(0~n-1)
• edges(간선 리스트): array(0~m-1)

structure vertex: 정점

• name(이름): string
• edges(부착간선리스트): linked-list

structure edge: 간선

• name(이름): string
• endpoint1(끝점): integer
• endpoint2(끝점):integer

structure graph:

• vertices(정점리스트): array(0~n-1)
• edges(간선리스트): array(0~m-1)
• adjacencyMatrix(인접행렬): [0~n-1, 0~m-1]

structure vertex:

• name: string

structrue edge:

• name(이름): string
• endpoint1(끝점): integer
• endpoint2(끝점): integer

그래프 표현 간단버전

원래는 정점, 간선, 연결관계 세개를 이용했다.

그러나 보통은 간선 정보를 유지하지 않는다.(간단버전-간선요소 생략)

보통 정점을 기준으로 찾기에 간선 리스트를 생략하는 것.

• 붉은색 번호: 정점 리스트의 번호
• 녹색 번호: 간선 리스트의 번호
• incidence list에서 배열로 구현할 경우엔 배열 번호를 알려주고, 리스트로 구현하면 주소를 알려준다.
• 간단버전에서는 incidence list에서 연결된 정점 번호를 알려준다.

• 간선 정보를 넣어줌.
• 가중치가 있다면 가중치를 써주고, 없다면 이름, 그것도 없다면 0,1로 구현

그래프 구현시 범용버전으로 구현하면 만점, 아니면 차감 일 수도 있다.

• 난이도가 높으면 간단을 써도 됨.

위의 구현 방식은 정답이 아니다.