Как измерить время и сложность Breadth First Search на основе подходов к очередям для Смежности Матра - PullRequest
Новая
       34

Как измерить время и сложность Breadth First Search на основе подходов к очередям для Смежности Матра

0 голосов
/ 02 ноября 2018

Поиск в ширину (BFS) - это алгоритм обхода или поиска в структурах данных дерева или графа. Он начинается с корня дерева (или некоторого произвольного узла графа, иногда называемого «ключом поиска») и исследует все соседние узлы на текущей глубине, прежде чем перейти к узлам на следующем уровне глубины.

Это мой C-код поиска в ширину (BFS), основанный на подходах к очереди для матрицы смежности. Я использую clock_t, чтобы измерить время, но время короткое. Как измерить время, затраченное на этот код? Кто-нибудь может мне помочь? 

  #include <stdio.h>
    #include <time.h>

    #define QUEUE_SIZE 20
    #define MAX 20

    //queue
    int queue[QUEUE_SIZE];
    int queue_front, queue_end;
    void enqueue(int v);
    int dequeue();

    void bfs(int Adj[][MAX], int n, int source);

   int main(void) {
       clock_t t;
       t = clock();
    //Adj matrix
    int Adj[][MAX] = {
        {0,0,1,1,0,0,0,0},
        {0,0,0,0,0,1,0,0},
        {1,0,0,0,0,0,1,0},
        {1,0,0,0,0,1,0,0},
        {0,0,0,0,0,0,1,1},
        {0,1,0,1,0,0,0,1},
        {0,0,1,0,1,0,0,0},
        {0,0,0,0,1,1,0,0},
    };

    int n = 8;  //no. of vertex
    int starting_vertex = 0;

    bfs(Adj, n, starting_vertex);

double time_taken = ((double)t)/(CLOCKS_PER_SEC/(1000));

    printf("\n%f miliseconds to execute \n", time_taken);
    return 0;
}

void bfs(int Adj[][MAX], int n, int source) {
    //variables
    int i, j;

    //visited array to flag the vertex that
    //were visited
    int visited[MAX];

    //queue
    queue_front = 0;
    queue_end = 0;

    //set visited for all vertex to 0 (means unvisited)
    for(i = 0; i < MAX; i++) {
        visited[i] = 0;
    }

    //mark the visited source
    visited[source] = 1;

    //enqueue visited vertex
    enqueue(source);

    //print the vertex as result
    printf("%d ", source);

    //continue till queue is not empty
    while(queue_front <= queue_end) {
        //dequeue first element from the queue
        i = dequeue();

        for(j = 0; j < n; j++) {
            if(visited[j] == 0 && Adj[i][j] == 1) {
                //mark vertex as visited
                visited[j] = 1;

                //push vertex into stack
                enqueue(j);

                //print the vertex as result
                printf("%d ", j);
            }
        }
    }
    printf("\n");
}

void enqueue(int v) {
    queue[queue_end] = v;
    queue_end++;
}

int dequeue() {
    int index = queue_front;
    queue_front++;
    return queue[index];
}
...