Cómo buscar un nodo específico en una estructura gráfica en C?

Question

No es que tenga tiempo para hablar de esto correctamente para llegar a una conclusión y adaptar mi código porque la fase uno (de tres) de un proyecto de la escuela se encuentra en 24 horas, pero al menos tengo que saber si lo hice la decisión correcta.

Estoy usando listas enlazadas y aquí está mi estructuras:

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;

Básicamente, tengo un montón de ciudades y las ciudades están unidas todas juntas, como un gráfico. Por ejemplo, A, B, C, D y E que se insertan en este orden en la estructura Ciudad . Entonces, me conecto de A a B, C y D, B a C, D, E, C y D y E y D a E.

Ahora, digamos que tengo que ir a la ciudad de E. Este es el último en la lista enlazada y se necesita tiempo para recorrer la lista enlazada todo el camino. Tal vez no en este ejemplo con 5 ciudades, sino en la aplicación real que se supone que soportar como 10.000 ciudades por lo menos. Pero la ruta más corta es de A (que es el punto de partida) de C a E (o podría ser A-D-E o A-B-E, no importa).

¿Mis estructuras permiten a mí para encontrar la ruta más corta desde la A a la E sin recorrer toda la lista uno vinculado por uno? Si no, ¿qué estoy haciendo mal?

En caso afirmativo, ¿cómo puedo hacer eso? No tengo ni idea de cómo puedo encontrar un camino así ...

Answer 1

Hay dos problemas separados - uno, es probable que desee encontrar un puntero City para un ID de la ciudad (por ejemplo, "E".). No se puede hacer eso en menos tiempo lineal con sus estructuras; si usted lo necesita más rápidamente, utilice un árbol de búsqueda binaria o tabla hash.

Dos, usted quiere encontrar un camino entre dos ciudades dadas. Para ello lo que probablemente utiliza el algoritmo BFS, para el que la estructura de datos está muy bien. Tenga en cuenta que BFS toma tiempo O (V + E) donde V y E son el vértice y el recuento de borde de la subgrafo inducido cuya distancia vértices desde el vértice de inicio no es mayor que la distancia desde el principio hasta el vértice extremo. Lo que significa que en el peor de los casos, se tarda más tiempo que recorrer la lista de ciudades.

Answer 2

Puede utilizar un algoritmo llamado primero en amplitud Search (BFS). Es necesario implementar una bandera "de color" en cada nodo para usarlo. Tenga en cuenta que este algoritmo sólo funciona si los bordes son no ponderado - si 2 ciudades están conectadas, a continuación, son de la misma distancia. Si los bordes tienen un peso (que no se ve igual que lo hacen), se necesita algo así como algoritmo de Dijkstra o A * .