According to the real bus route map of Nanjing, the storage structure of the main bus route map of Nanjing is established.

[basic requirements]

(1) Input any two stations and give the route with the least number of transfers.

(2) Input any two stations, and give the minimum route through the station.

Use map structure to store stations and buses. Establish the bus structure, and store the number of passing stations and bus numbers. The station structure is established to store the new station number and the bus number passing the station.

To find the minimum number of transfers, breadth first traversal algorithm is used to determine all stops of each bus involved in the starting point. If there is a terminal, there is no need to transfer. If there is no destination, all the stops that each bus involved in the starting point passes through will be put into the queue, and the Visited array will be used to determine whether the stop has been Visited. Queue element is out of the queue, continue to judge all stops of each bus involved in this point, and repeat the above steps until the required destination is found.

The breadth first traversal algorithm is still used to find the minimum number of passing stations, and judge the stations before and after the starting point of each bus involved in the starting point. If it is the terminal, the number of passing stations is the minimum. If there is no end point, let each bus involved in the starting point enter the queue before and after the starting point, and judge whether the site has been Visited through the Visited array. Queue element out, continue to judge the station before and after the point of each bus involved in the point, and repeat the above steps until the required destination is found.

#include <stdio.h>
#include <windows.h>
typedef int Status;

typedef struct Bus
{
    int No;        //The number of the bus
    int count;     //Number of stops the bus passes
    int route[80]; //The route of the bus
} Bus;             //1000
typedef struct Station
{
    short int bus[35]; //The number of the bus passing through the station
    int count;         //Number of buses passing through the station
    char name[60];     //Site name
} Station;             //12000
typedef struct Map
{
    Bus bus[1000];          //Buses in the city
    Station station[10000]; //Sites in the city
    int BusCount;           //Number of buses
    int StationCount;       //Number of sites
} Map;
typedef struct element
{
    int bus;
    int before;
    int cur;
} element;
typedef struct QNode
{
    element data;
    QNode *next;
} QNode, *QueuePtr;
typedef struct
{
    QueuePtr front; //Head pointer
    QueuePtr rear;  //Tail pointer
} LinkQueue;

Status InitQueue(LinkQueue &Q);          //Construct an empty queue Q
Status EnQueue(LinkQueue &Q, element e); //Insert element e as a new queue tail element, if Q exists
element DeQueue(LinkQueue &Q);           //If the queue is not empty, delete the queue head element and return its value, if Q exists
Status GetMap(Map &M);
Status InitMap(Map &M);
int locate_station(Map &M, char name[30]);
int locate_bus(Map &M, int No);
Status GetBusStation(Map &M, char temp[60]);
Status LeastTransfers(Map &M, char name_1[60], char name_2[60]);
Status TraversalSite_CD(Map &M, int v1, int v2);
Status LeastSite(Map &M, char name_1[60], char name_2[60]);
Status TraversalSite_AD(Map &M, int v1, int v2);
void Print(Map M);
//Nanpu Park Station, SaJiaWan station, North Zhongshan Road, Xining community station
int visited[10000] = {0};
int main()
{
    Map M;
    InitMap(M);
    GetMap(M);
    while (1)
    {
        system("cls");
        char name_1[60], name_2[60];
        printf("\t\t\t Welcome to Nanjing bus line query system(To exit the system,Please enter exit)\n");
        printf("Please enter a starting point:");
        scanf("%s", name_1);
        if (strcmp(name_1, "Sign out") == 0)
            break;
        if (!locate_station(M, name_1))
        {
            printf("The site was not found,Please check whether the input is wrong!\n");
            system("pause");
            continue;
        }
        printf("Please enter the end point:");
        scanf("%s", name_2);
        if (strcmp(name_2, "Sign out") == 0)
            break;
        if (!locate_station(M, name_2))
        {
            printf("The site was not found,Please check whether the input is wrong!\n");
            system("pause");
            continue;
        }
        printf("\n Route with minimum number of stations\n");
        LeastSite(M, name_1, name_2);
        printf("\n Minimum transfer route\n");
        LeastTransfers(M, name_1, name_2);
        system("pause");
    }
    system("pause");
    return 0;
}
Status LeastSite(Map &M, char name_1[60], char name_2[60])
{
    int v1 = locate_station(M, name_1);
    for (int i = 1; i < 10000; i++)
    {
        visited[i] = 0;
    }
    int v2 = locate_station(M, name_2);
    TraversalSite_AD(M, v2, v1);
}
Status TraversalSite_AD(Map &M, int v1, int v2)
{
    element e[8000];
    for (int i = 1; i < 8000; i++)
    {
        e[i].cur = i;
        e[i].bus = 0;
    }
    element e0;
    int count = 1;
    LinkQueue Q;
    InitQueue(Q);
    EnQueue(Q, e[v1]);
    visited[v1] = 1;
    while (1)
    {
        int k = 1;
        count++;
        e0.cur = -1;
        EnQueue(Q, e0);
        while (Q.front != Q.rear)
        {
            v1 = DeQueue(Q).cur;
            if (v1 == -1)
                break;
            for (int i = 1; i <= M.station[v1].count; i++)
            {
                int bus1 = locate_bus(M, M.station[v1].bus[i]);
                for (int j = 1; j <= M.bus[bus1].count; j++)
                {
                    if (M.bus[bus1].route[j] == v1)
                    {
                        if (M.bus[bus1].route[j + 1] == v2 || M.bus[bus1].route[j - 1] == v2)
                        {
                            int bus = e[v1].bus;
                            printf("Least pass%d One site\n", count);
                            printf("%s(Starting point,ride%d Road bus)-->", M.station[v2].name, M.bus[bus1].No);
                            //Printf (""% s (take bus% d) -- > ", m.station [V1]. Name, m.bus [bus1]. No);
                            count--;
                            while (count--)
                            {
                                if (count == 0)
                                    printf("%s(End)\n\n", M.station[v1].name);
                                else
                                    printf("%s(ride%d Road bus)-->", M.station[v1].name, bus);
                                v1 = e[v1].before;
                                bus = e[v1].bus;
                            }
                            return 1;
                        }

                        if (!visited[M.bus[bus1].route[j - 1]] && j - 1 > 0)
                        {
                            e[M.bus[bus1].route[j - 1]].bus = M.bus[bus1].No;
                            e[M.bus[bus1].route[j - 1]].before = v1;
                            EnQueue(Q, e[M.bus[bus1].route[j - 1]]);
                            visited[M.bus[bus1].route[j - 1]] = 1;
                        }
                        if (!visited[M.bus[bus1].route[j + 1]] && j + 1 <= M.bus[bus1].count)
                        {
                            e[M.bus[bus1].route[j + 1]].bus = M.bus[bus1].No;
                            e[M.bus[bus1].route[j + 1]].before = v1;
                            EnQueue(Q, e[M.bus[bus1].route[j + 1]]);
                            visited[M.bus[bus1].route[j + 1]] = 1;
                        }
                        break;
                    }
                }
            }
        }
    }
}
Status LeastTransfers(Map &M, char name_1[60], char name_2[60])
{
    int v1 = locate_station(M, name_1);
    for (int i = 1; i < 10000; i++)
    {
        visited[i] = 0;
    }
    int v2 = locate_station(M, name_2);
    TraversalSite_CD(M, v2, v1);
}
Status TraversalSite_CD(Map &M, int v1, int v2) //Adjacent point diffusion Connected point diffusion
{
    element e[8000];
    for (int i = 1; i < 8000; i++)
    {
        e[i].cur = i;
        e[i].bus = 0;
    }
    element e0;
    int count = 1;
    LinkQueue Q;
    InitQueue(Q);
    EnQueue(Q, e[v1]);
    visited[v1] = 1;
    while (1)
    {
        int k = 1;
        count++;
        e0.cur = -1;
        EnQueue(Q, e0);
        while (Q.front != Q.rear)
        {
            v1 = DeQueue(Q).cur;
            if (v1 == -1)
                break;
            for (int i = 1; i <= M.station[v1].count; i++)
            {
                int bus1 = locate_bus(M, M.station[v1].bus[i]);
                for (int j = 1; j <= M.bus[bus1].count; j++)
                {
                    if (M.bus[bus1].route[j] == v2)
                    {
                        int bus2;
                        bus2 = locate_bus(M, e[v1].bus);
                        printf("Least rotation%d Secondary vehicle\n", count - 1);
                        printf("%s(Starting point,ride%d Road bus)-->", M.station[v2].name, M.station[v1].bus[i]);
                        --count;
                        while (count--)
                        {
                            if (count == 0)
                                printf("%s(End)\n\n", M.station[v1].name);
                            else
                                printf("%s(Transfer%d Road bus)-->", M.station[v1].name, M.bus[bus2].No);
                            v1 = e[v1].before;
                            bus2 = locate_bus(M, e[v1].bus);
                        }
                        return 1;
                    }
                    if (!visited[M.bus[bus1].route[j]])
                    {
                        e[M.bus[bus1].route[j]].bus = M.bus[bus1].No;
                        e[M.bus[bus1].route[j]].before = v1;
                        EnQueue(Q, e[M.bus[bus1].route[j]]);
                        visited[M.bus[bus1].route[j]] = 1;
                    }
                }
            }
        }
    }
}
Status GetBusStation(Map &M, char temp[60])
{
    int index = locate_station(M, temp);
    if (!index)
    {
        strcpy(M.station[++M.StationCount].name, temp);
        index = M.StationCount;
    }
    M.bus[M.BusCount].route[M.bus[M.BusCount].count] = index;
    M.station[index].bus[++M.station[index].count] = M.bus[M.BusCount].No;
    for (int i = 0; i < 60; i++)
    {
        temp[i] = '\0';
    }
    return index;
}
int locate_station(Map &M, char name[60])
{
    for (int i = 1; i <= M.StationCount; i++)
    {
        if (strcmp(M.station[i].name, name) == 0)
            return i;
    }
    return 0;
}
int locate_bus(Map &M, int No)
{
    for (int i = 1; i <= M.BusCount; i++)
    {
        if (M.bus[i].No == No)
            return i;
    }
    return 0;
}
void Print(Map M)
{
    for (int i = 1; i <= M.BusCount; i++)
    {
        printf("%d road\t", M.bus[i].No);
        for (int j = 1; j <= M.bus[i].count; j++)
        {
            printf("%s ", M.station[M.bus[i].route[j]].name);
        }
        printf("\n");
    }
}
Status InitMap(Map &M)
{
    M.BusCount = 0;
    M.StationCount = 0;
    return 1;
    for (int i = 0; i < 1000; i++)
    {
        M.bus[i].count = 1;
    }
    for (int i = 0; i < 15000; i++)
    {
        M.station[i].count = 0;
    }
}
Status GetMap(Map &M)
{
    int k = 0;
    char temp[60];
    char ch;
    FILE *fp;
    if ((fp = fopen("Nanjing bus line.txt", "r")) == NULL)
    {
        printf("can't open this file\n");
        system("pause");
        exit(0);
    }
    for (int i = 1; i <= 1000; i++)
    {
        M.bus[i].count = 1;
    }
    fscanf(fp, "%d", &M.bus[++M.BusCount].No);
    while (ch != ' ')
        ch = fgetc(fp);
    while (1)
    {
        ch = fgetc(fp);
        if (feof(fp))
        {
            GetBusStation(M, temp);
            break;
        }
        if (ch == '\n')
        {
            GetBusStation(M, temp);
            //printf("%s",bus[i].route[j]);
            k = 0;
            char ch2;
            ch2 = fgetc(fp);
            if (feof(fp))
                break;
            fseek(fp, -1L, 1);
            fscanf(fp, "%d", &M.bus[++M.BusCount].No);
            while (ch != ' ')
                ch = fgetc(fp);
            continue;
        }
        if (ch == ' ')
            continue;
        if (ch == ',')
        {
            GetBusStation(M, temp);
            //printf("%s",bus[i].route[j]);
            k = 0;
            M.bus[M.BusCount].count++;
            continue;
        }
        temp[k++] = ch;
    }
    fclose(fp);
}
Status InitQueue(LinkQueue &Q)
{
    Q.front = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        exit(-2);
    Q.front->next = NULL;
    Q.rear = Q.front;
    return true;
}
Status EnQueue(LinkQueue &Q, element e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); //Open up new nodes
    if (!p)
        exit(-2);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return true;
}
element DeQueue(LinkQueue &Q)
{
    element e;
    if (Q.front == Q.rear)
    {
        printf("Stack space");
        system("pause");
        exit(0);
    }
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return e;
}

test result