그래프 데이터 구조에 동적으로 추가하기

Question

작은 코드 단이 포인트를 얻는 유일한 방법이 아니라면, 반드시 실제 코드가 아닌 방향을 원한다고 설명하겠습니다.

C++에서 인접 목록이나 행렬을 사용하여 DIRECTED 그래프 데이터 구조를 만들고 표준 입력에서 정점/가장자리를 동적으로 추가해야합니다.

처음에는 Vertices 세트를 인스턴스화 한 다음 가장자리를 만들고 그래프에 추가 할 수 있으면 그래프를 잘 작성할 수있을 것이라고 생각하지만 추가하는 방법을 이해하지 못합니다. 아직 인스턴스화되지 않은 꼭지점을 포함하는 가장자리.

예를 들어, 표준 입력의 첫 번째 줄을 읽

마이애미 -> 뉴욕/1100 -> 워싱턴/1000 -> 앨버 커키/1700

나는 마이애미에서 우위를 추가 할 수 있다고 생각 할수 있습니까 뉴욕 정점이 아직 그래프에 추가되지 않았다면 뉴욕으로?

모두에게 감사드립니다!

Answer 1

에 아직 인스턴스화되지 않은 정점이 포함 된 에지를 추가하는 방법.

간단한 :이 어떤 문제를 볼 수 없습니다 ..

를 인스턴스화. 지금까지 보았던 정점 집합이 V이라고 가정합니다. V은 처음에는 비어 있습니다. 입력 x->y을 읽으면 끝점 (x 및 y)이 표시됩니다. 인스턴스 중 하나가 인스턴스화되지 않은 경우 (즉, V이 아닌 경우) 인스턴스를 인스턴스화하여 정점 세트에 추가합니다.

또 다른 방법은 다음과 같습니다. 그래프를 가장자리 설정 E으로 정의하는 것을 상상해보십시오. 정의에 따라 모든 엣지는 그래프의 정점 집합을 정의하는 한 쌍의 정점입니다.