이상적인 데이터 구조의 신진 대사 경로

Question

생물체 내에서 화학 물질의 엄청난 목록과 전구체 화학 물질 및 생성 된 화학 물질에 대한 데이터가 있습니다.

저는 나무 구조가 적절할 것이라고 생각했습니다. 각 화학 물질은 노드이고, 각 부모는 전구체이며, 각 어린이는 제품입니다.

각 노드에는 하나 이상의 부모 또는 하나 이상의 자식이있을 수 있습니다. 따라서 혼란스러워합니다!

그러나이 구조의 주요 기능은 모든 화학적 경로를 찾아 내고, 나무가 이런 종류의 검색에서 가장 효율적인지 확신 할 수 없습니다.

내 질문은 :이 데이터 및 작업 유형에 적합한 데이터 구조가 있습니까?

Answer 1

데이터 구조가 유향 그래프라고 생각합니다.

A부터 B까지 모든 경로를 찾는 무차별 대입 방식은 A에서 시작하는 너비 우선 검색을 수행하고 허용되는만큼 많은 그래프를 덮는 것입니다.

이렇게하면 찾을 경로가 가장 짧은 것부터 가장 긴 것으로 순서가 지정됩니다.

B를 누르면 항상 경로의 모든 노드를 'B로 연결'으로 표시해야합니다. 이렇게하면 그래프를 한 번 이상 둘러 보지 않고도 수렴형 경로를 고려할 수 있습니다.

제한하지 않는 한 그래프에 루프가 포함될 수 있습니다. A에서 B로 연결되는 경로의 루프는 무한 경로를 제공하므로이 사례를 어떻게 처리 할 것인가는 당신에게 달려 있습니다.