Нужно ускорить алгоритм

[shukshin]

Добрый вечер, уважаемые участники! Помогите ускорить поиск в ширину для графа.
Дан неориентированный граф на n вершинах и m рёбрах (1≤ n,m ≤100000), а также номера вершин a и b. Вывести количество рёбер на кратчайшем пути между вершинами a и b или -1, если пути между ними в графе нет.

На вход список ребер
3 2 //n m

1 2
2 3

1 3//?
Вывод: 2

Что я написал:

Используется синтаксис C++

#include <stdio.h>
#include <stdlib.h>

typedef struct _node 
{
        int vnum;
    struct _node *next;
}Node;

typedef struct _queue
{
        Node *include;
        Node *exclude;
}Queue;

void enq(int value, Queue *Q)
{
   Node *New_node = (Node *)malloc(sizeof(Node));
   
   New_node->vnum = value;
   New_node->next = NULL;

   if(Q->exclude == NULL)//first
   {
           Q->include = New_node;
           Q->exclude = Q->include;
   }
   else
   {
       Q->include->next = New_node;
       Q->include       = New_node;
   }
}

int  deq(Queue *Q)
{
   int value;
   Node *ptr;

   value = Q->exclude->vnum;
   ptr   = Q->exclude;   

   if(Q->exclude == Q->include)
   {
           Q->exclude = NULL;
       Q->include = NULL;
   }
   else
       Q->exclude = Q->exclude->next;

   free(ptr);
   return value;
}

int is_empty(Queue *Q)
{
        if( Q->include == NULL || Q->exclude == NULL )
                return 1;
        return 0;
}

void del_queue(Queue *Q)
{
   while( !is_empty( Q ))
      deq( Q );
}

int is_connected(int v1, int v2, Queue *LOC)
{
        Node *p;

        p = LOC[v1].exclude;

        while(p != NULL)
        {
       if(p->vnum == v2)
                   return 1;
           p = p->next;
        }
    
        return 0;
}

int *bfs( int v, int n, Queue *LOC)
{
        register int i;
        int *dest = (int *)malloc(n * sizeof(int)), u;
    Queue MyQueue;

        MyQueue.exclude = NULL;
        MyQueue.include = NULL;

        for(i = 0; i < n; ++i)
                dest[i] = -1;
        dest[v] = 0;

        enq(v, &MyQueue);

        while(!is_empty(&MyQueue))
        {
                u = deq(&MyQueue);
                for(i = 0; i < n; ++i)
                        if((is_connected(u, i, LOC)) && (dest[i] == -1))
                        {
                                enq(i, &MyQueue);
                        dest[i] = dest[u] + 1;
                        }
        }
    del_queue(&MyQueue);
        return dest;   
}

int main(void)
{
        register int i;
        int v, e, *q, a, b;
        Queue *ListOfContinuity;
        
        scanf("%i", &v);
        scanf("%i", &e);

        ListOfContinuity = (Queue *)calloc(v, sizeof(Queue));
        
        i = 0;
        while(i < e)
        {
                scanf("%i", &a);
                scanf("%i", &b);
                enq(b - 1, &ListOfContinuity[a - 1]);
                enq(a - 1, &ListOfContinuity[b - 1]);
                ++i;
        }

        scanf("%i", &a);
    scanf("%i", &b);

    q = bfs(a - 1,  v,  ListOfContinuity);
        printf("%i", q[b - 1]);

        free(q);
        for(i = 0; i < v; ++i)
                del_queue(ListOfContinuity + i);
        free(ListOfContinuity);
        return 0;
}
 

Представление графа списком смежности довольно эффективно, алгоритм - поиск в ширину - именно тот, что нужен для выполнения задачи. Чем ускорить-то?

[venco]

В bfs() вместо перебора всех вершин для перехода к следующей надо использовать список соседних вершин прямо из LOC[у].

[shukshin]

спасибо, огромное!