0
학교 프로젝트의 1 단계 (3 단계)가 24 시간이기 때문에 결론을 내리고 코드를 수정하기 위해이 문제를 제대로 논의 할 시간이 없지만 적어도 올바른 결정을했는지 알아야합니다.C의 그래프 구조에서 특정 노드를 검색하는 방법은 무엇입니까?
내 구조를 여기에 연결리스트와있어 사용하고 있습니다 :
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와 D를 E에 연결합니다.
이제 도시 E에 가야한다고 가정 해 봅시다. 하나는 링크 된 목록에 있으며 링크 된 목록을 끝까지 탐색하는 데 시간이 걸립니다. 아마도 5 개 도시에서의이 예제가 아닐지 모르지만 적어도 실제 도시에서는 10,000 개 도시를 지원해야합니다. 그러나 가장 짧은 경로는 C에서 E까지의 출발점 인 A (또는 A-D-E 또는 A-B-E 일 수 있습니다.)는 중요하지 않습니다.
내 구조를 사용하면 링크 된 목록 전체를 순회하지 않고도 A에서 E까지 최단 경로를 찾을 수 있습니까? 그렇지 않다면 내가 뭘 잘못하고 있니?
그렇다면 어떻게해야합니까? 나는 그런 경로를 어떻게 찾을 수 있는지 실마리가 없습니다 ...
특정 도시가 필요한 경우 찾을 때까지 목록을 탐색해야합니다. 두 지점 간의 최단 경로를 찾아야하는 경우 BFS를 사용합니다. 맞습니까? –
네, 어느 정도 연결되어 있습니다. 두 도시 중 적어도 하나의 도시 포인터로 BFS를 시작하십시오. – jpalecek