index기반으로 구현안한다면 vertex멤버변수에 index두고
삽입삭제시 vertex->idx (번호)를 갱신해주고
removevertex (elem) 으로한다면 시간복잡도도 O(vertex개수)되겠지만은... 어차피 index기반이어도 번호땡기기(shift)때문에 시간복잡도는 같을테고
정점삽입시 vector이용
뭐 간선삽입시에는 정점vector인덱스이용(2, 5, 간선의elem)
근데이렇게 구현한사람이 없더군요
크루스칼에 union find연산에서
정점의 인덱스를 구해야하는데
간선 u로 정점 두개찾고 (간선에는 두개의 vertex포인터가 저장되있음)
vertex->idx로 인덱스얻고
이렇게하면 index기반이랑 다를게없는데
또 맘에안드는건 결국 edge삽입때 (vtx elem1,vertex elem2,edge) 이함수의 시간복잡도는 elem검사때문에 O(vertex개수) 이고
그렇다면 해쉬는 아니더라도 BST이용해서 빠른검사를 한다던지 이러면 해봐야 E개 edge삽입하는데 시간복잡도ElogV
그래프 대체로 어떻게구현하죠??
그냥 문제풀기식 그래프구현말고 자료구조로써의 그래프 질문입니다.
1. 모든 vertex의 번호가 고정되있다(서울은 무조건1번 인천은 2번 ....등 절대바뀌지않음 )
제가 잘못생각하고있는것 같기도해서 조언부탁드립니다
실제로는 어떤식으로 구현하죠?
삽입삭제시 vertex->idx (번호)를 갱신해주고
removevertex (elem) 으로한다면 시간복잡도도 O(vertex개수)되겠지만은... 어차피 index기반이어도 번호땡기기(shift)때문에 시간복잡도는 같을테고
정점삽입시 vector이용
뭐 간선삽입시에는 정점vector인덱스이용(2, 5, 간선의elem)
근데이렇게 구현한사람이 없더군요
크루스칼에 union find연산에서
정점의 인덱스를 구해야하는데
간선 u로 정점 두개찾고 (간선에는 두개의 vertex포인터가 저장되있음)
vertex->idx로 인덱스얻고
이렇게하면 index기반이랑 다를게없는데
또 맘에안드는건 결국 edge삽입때 (vtx elem1,vertex elem2,edge) 이함수의 시간복잡도는 elem검사때문에 O(vertex개수) 이고
그렇다면 해쉬는 아니더라도 BST이용해서 빠른검사를 한다던지 이러면 해봐야 E개 edge삽입하는데 시간복잡도ElogV
그래프 대체로 어떻게구현하죠??
그냥 문제풀기식 그래프구현말고 자료구조로써의 그래프 질문입니다.
1. 모든 vertex의 번호가 고정되있다(서울은 무조건1번 인천은 2번 ....등 절대바뀌지않음 )
제가 잘못생각하고있는것 같기도해서 조언부탁드립니다
실제로는 어떤식으로 구현하죠?
그건 대체로 vertex 자체의 크기가 크기 때문.
index 의 수배 내지 수십배에 달하기 때문에 vertex 를 직접핸들링하는데 부적합하고, 동일 vertex인지 중복 vertex인지 구별도 힘들뿐더러, 동일 vertex의 업데이트에 대해 일일이 찾아가며 푸는게 결국 문제.
그렇다면 그냥 처음에 vertex가 insert 차례대로 쭈르르륵되고 edge삽입할땐 vertex번호기반으로 삽입하면 되나요
중간에 삽입삭제가없다면 edge변수에도그냥 int startend_vertexidx [2]; 이런식으로 정점번호 저장하나요??
크루스칼 union find연산할때 edge로부터 vertex번호얻으려면 vertex에 순서번호를 저장하던지 edge자체가 알고있던지 해야할것 같아서입니다