ComputerScience에서 DataStructure의 하나인 Graph에 관한 이론들.

어떤 대상(object, node)들과 그들 사이의 관계(relationship, edge)에 관한 이론. Bioinformatics의 많은 문제들이 실제 GraphTheory문제인경우가 많다.

알려진 GraphTheory문제들

• TravelingSalesmanProblem

• AntiSymmetricLongestPathProblem

• ShortestPathProblem

• EulerPathProblem

• HamiltonianPathProblem

관련자료

• IntroductionToAlgorithms

• GraphTheoryWithApplications

• ReinhardDiestelGraphTheory

• GraphTheory

• 파이썬으로구현

  • 여기서 구현한 내용은 recursive 함수를 사용해서 shortest path를 구하는 건데요, 그렇게 하면 노드가 많아질 경우 stack overflow되서 제대로 동작하지 못할 것 같습니다. 대략 어느정도 recursive가 불려질 경우 에러가 발생할지는 모르겠지만.. DynamicProgramming으로 path 구하는 방법을 바꿔야 하지 않을까 합니다. --destine, 2004-03-21

SeeAlso GraphTheory