이것은 interview question입니다. 그래프를 직렬화하는 방법은 무엇입니까? 나는 이것이 answer을 봤지만 이것이 충분한 지 확신 할 수 없다.그래프를 직렬화하는 방법은 무엇입니까?
이것은 매우 혼란스러운 "열린 질문"처럼 보입니다. 후보자는 요구 사항에 대해 더 많은 질문을해야 할 것입니다 : 노드와 에지가 무엇인지, 어떻게 직렬화되는지,이 그래프가 가중되고 지시되는지 등등. , 얼마나 많은 노드/에지가 그래프에 있습니다. 인프라는 어떻습니까? 일반 파일 시스템입니까 아니면 데이터베이스를 사용할 수 있습니까?
그럼이 질문에 어떻게 대답합니까?
나는 대답이 당신이 provided라고 생각합니다. IMO, 기본적으로 응용 프로그램 배경을 알아야합니다, 적어도 물어 볼 것입니다 :
가장 간단한 방법은 가장자리 목록으로 저장하는 것입니다. 그러나 다른 응용 프로그램에는이를 수행하는 몇 가지 고전적인 방법이 있습니다. 예를 들어 회로 시뮬레이션을 수행하면 그래프가 희박 해지고 결과 그래프/매트릭스를 열 압축 형식으로 저장할 수 있습니다. 최대 (최소 비용) 최대 흐름 문제를 푸는 중이라면 DIMACS 형식이 이미 있으므로 공개 솔버가이를 읽고 쓸 수 있습니다. 사람이 읽을 수 있기를 원하면 구조화 된 방법을 사용하는 것이 좋습니다. XML은 자체 유효성 검사를 제공 할 수 있습니다 (이미 GraphML이 표준으로 제공됨). 그건 그렇고, dot 형식은 완전히 자체 포함되어 있습니다.
Meh. 무엇을 저장하든 기본적으로 다음과 같습니다.
그래프에 각 정점을 출력합니다. 모든 정점을 먼저 가지고 있지 않다면 그래프를 다시 읽을 때 그래프를 다시 작성하는 것은 PITA입니다.
이제 정점 사이에 모서리를 저장할 수 있습니다. 다행히도 정점에는 ID를 고유하게 식별 할 수있는 ID가 포함되기를 바랍니다. 내가 본 버전은 "데이터베이스에 (그래프 | 트리) 저장"입니다. 그래서, 노드를 읽어서 O (1) 상각 된 룩업을 위해 해시 테이블이나 유사하게 저장하십시오. 그런 다음 foreach edge, ID- 소스 및 ID-dest 및 링크를 찾습니다.
바일라, 당신은 그것을 비 직렬화했습니다. DB가 아닌 경우 일반적으로 동일한 아이디어가 유지됩니다. 먼저 노드를 직렬화 한 다음 에지를 직렬화합니다.
어떤 언어입니까? C#에서는 클래스를 Serializable로 표시 할만큼 충분합니다. –
당신이 말하는 대답이 완전히 만족 스럽다고 생각합니다. 목록과 행렬은 모두 분산과 가중치를 유지하도록 조정될 수 있습니다. –