위는 예시

비전공이라 물어볼 곳도 없음.

Adjacency List는 알고 있었는데 Multilist는 정말 신박하더라

꼭 구현하고 싶은데 문제는 효율적으로 할당해제할 방법이 마땅히 안떠오름.

엣지하나만 없애는 건 링크드 리스트 지우듯이 앞에거랑 뒤엣거 잘 연결만 해주면 되니 알겠는데,

예를들어 vertex 5만에 평균 degree가 4, 8 이런 그래프를 지울 때,
어차피 다 지울 걸 하나씩 일일이 몇십만번 새로 이어주는 건 말이 안된다는 거지.

일단 생각나는 건
1. vertex하나(V1)를 집어 리스트 첫번째에 있는 edge(N1)를 stack에 넣는다.

2. 반복하기 전에 첫번째 edge가 연결하는 vertex 중 V1가 아닌 녀석 (V2)를  찾는다.

3. V2의 리스트에서 stack의 첫번째 edge N1이 나올 때 까지 따라간 뒤, 찾으면 nullptr로 바꿔준다.

4. stack의 top edge에 있는 2개의 edge( N2, N4)를 또 stack에 넣는다.

5. 양쪽모두 nullptr인 edge가 top에 올 때까지 stack에 넣는 걸 반복한다.

6. stack에 있는 edge들을 탑에서 부터 delete한다.

7.  모든 vertex에 대해 반복.


아씨 근데 쓰고나니 이젠 vertex3에서 N2에 접근할 때 이미 할당 해제된 곳에 접근하려 하겠네....

이미 해제된 memory에 또 delete를 쓰면 에러나겠지?

된다면 edge 객체의 파괴자에서 다음 edge의 파괴자도 호출하도록 하면 끝이긴 한데.

실행이 된다해도 좋은 방법은 아닌거 같음.

사실 weak pointer쓰면 깔끔한데 이건 최후의 수단으로 남기고 싶음.

훌륭하신 슨배님들 불쌍한 뉴비에게 길을 알려주세요

ps. 모든 edge를 배열에 저장해 두면 쉽지만, 길이 몇십만의 연속된 배열을 할당하는 건 좀.....

- dc official App