C의 그래프 구조에서 특정 노드를 검색하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/670301

문제

학교 프로젝트의 1 단계 (3 단계)가 24 시간이기 때문에 결론에 도달하고 코드를 적응시키기 위해 이것을 제대로 논의 할 시간이 아니라 적어도 올바른 결정을했는지 알아야합니다.

링크 된 목록을 사용하고 있으며 여기에 내 구조가 있습니다.

typedef struct sCity {
    int cityID;
    char *cityName;

    struct sCityLink *links;
    struct sCity *next;
} nCity, *City;

typedef struct sCityLink {
    City cityLinkParent;
    City cityLinkTo;

    struct sCityLink *next;

} nCityLink, *CityLink;

기본적으로, 나는 많은 도시를 가지고 있으며 그 도시는 그래프처럼 모두 연결되어 있습니다. 예를 들어, A, B, C, D 및 E는이 순서로 구조에 삽입됩니다. 도시. 그런 다음 A를 B, C 및 D, B에서 C, D, E, C에서 D 및 E로 연결합니다.

이제 City E로 가야한다고 가정 해 봅시다. 이것은 링크 된 목록의 마지막 것이며 링크 된 목록을 끝까지 횡단하는 데 시간이 걸립니다. 어쩌면 5 개 도시가있는이 예에서는 아니지만 실제 앱에서는 적어도 10,000 개 도시처럼 지원해야합니다. 그러나 가장 짧은 경로는 C에서 E까지 (또는 ADE 또는 ABE 일 수도 있고, 중요하지 않음) A에서입니다.

내 구조를 통해 전체 연결된 목록을 하나씩 가로지 않고 A에서 E까지 가장 짧은 경로를 찾을 수 있습니까? 그렇지 않다면, 내가 뭘 잘못하고 있습니까?

그렇다면 어떻게 할 수 있습니까? 나는 어떻게 그런 길을 찾을 수 있는지 단서가 없습니다 ...

도움이 되었습니까?

해결책

두 가지 별도의 이슈가 있습니다. 하나는 아마도 도시 ID (예 : "e")에 대한 도시 포인터를 찾고 싶을 것입니다. 구조로 선형 시간 이하로 그렇게 할 수 없습니다. 더 빨리 필요한 경우 해시 가능 또는 이진 검색 트리를 사용하십시오.

둘째, 주어진 두 도시 사이의 길을 찾고 싶습니다. 이를 위해서는 데이터 구조가 정상인 BFS 알고리즘을 사용할 것입니다. BFS는 v와 e가 시작된 서브 그래프의 정점과 가장자리 수는 시작 정점에서의 정점 거리가 시작에서 끝에서 끝에서 끝에서 끝까지 거리보다 크지 않은 유도 된 서브 그래프의 정점 및 가장자리 수 인 O (v+e) 시간이 걸린다는 점에 유의하십시오. 이는 최악의 경우 도시 목록을 가로 지르는 것보다 더 많은 시간이 걸립니다.

다른 팁

호출 된 알고리즘을 사용할 수 있습니다 폭 넓은 첫 번째 검색 (BFS). 각 노드에서 "색상"플래그를 구현하여 사용해야합니다. 이 알고리즘은 가장자리가있는 경우에만 작동합니다. 비가 중 - 2 개 도시가 연결되어 있으면 거리가 같다. 가장자리에 무게가있는 경우 (그렇지 않은 것처럼 보이지 않음) Dijkstra의 알고리즘 또는 ㅏ*.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top