Алгоритм поиска в ширину - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Нашел алгоритм "поиска в ширину" только на С#. Может кто-нибудь переписать его на С?
Random rand = new Random();
Queue<int> q = new Queue<int>();    //Это очередь, хранящая номера вершин
string exit = "";
int u;
int v;
u = rand.Next(3, 5);
bool[] used = new bool[u + 1];  //массив отмечающий посещённые вершины
int[][] g = new int[u + 1][];   //массив содержащий записи смежных вершин
 
for (int i = 0; i < u + 1; i++)
{
    g[i] = new int[u + 1];
    Console.Write("\n({0}) вершина -->[", i + 1);
    for (int j = 0; j < u + 1; j++)
          {
                  g[i][j] = rand.Next(0, 2);
           }
      g[i][i] = 0;
      foreach (var item in g[i])
            {
                  Console.Write(" {0}", item);
             }
      Console.Write("]\n");

Решение задачи: «Алгоритм поиска в ширину»

textual
Листинг программы
#include <stdio.h>
#include <malloc.h>
#include <limits.h>
typedef unsigned short word_t;
typedef unsigned char  byte_t;
 
typedef struct node {
    struct node* next;
    word_t v;
} node_t;
 
typedef struct {
    node_t* h, *t;
} queue_t;
 
void   queue_init(queue_t* q){ q->h = q->t = NULL; }
int    queue_empty(queue_t* q){ return (q->h == NULL); }
word_t queue_front(queue_t* q) { return q->h->v; }
int    queue_push(queue_t* q, word_t v);
void   queue_pop(queue_t* q);
void   queue_clear(queue_t* q);
 
typedef struct {
    word_t v, p;
} vert_t;
byte_t** graph_input(FILE* _in, int* n);
void     graph_free(byte_t** g, int n);
word_t*  graph_bfs(byte_t** g, int n, word_t s, word_t e, int* m);
 
int main(void){
    int      i, n, m;
    word_t*  p, s, e;
    byte_t** g;
 
/*   ввод из файла
    FILE* f = fopen("graph.txt", "rt");
    if(f == NULL)
        return 1;
    g = graph_input(f, &n);
    fclose(f);
*/
    g = graph_input(stdin, &n);
    if(g == NULL)
        return 1;
 
    s = 3;//старт
    e = 4;//конец
    p = graph_bfs(g, n, s, e, &m);
    if(p != NULL){
        printf("path: ");
        for(i = 0; i < m; ++i)
            printf("%u ", p[i]);
        putchar('\n');
 
        free(p);
    } else
        fputs("error find bfs!\n", stderr);
 
    graph_free(g, n);
    return 0;
}
 
//поиск в ширину
word_t* graph_bfs(byte_t** g, int n, word_t s, word_t e, int* m){
    int     i, y;
    queue_t q;
    vert_t* vs;
    word_t  v, *p, *d, *j;
 
    p  = NULL;
    vs = (vert_t*)malloc((size_t)n * sizeof(vert_t));
    if(vs == NULL)
        return NULL;
    for(i = 0; i < n; ++i)
        vs[i].p = vs[i].v = USHRT_MAX;
    
    vs[s].v = 0;
    queue_init(&q);
    queue_push(&q, s);
 
    y = 0;
    while(! queue_empty(&q)){
        v = queue_front(&q);
        queue_pop(&q);
        if(v == e){
            y = 1;
            break;
        }
        for(i = 0; i < n; ++i){
            if((g[v][i] != 0) && (vs[i].v > (vs[v].v + 1))){
                queue_push(&q, (word_t)i);
                vs[i].p = v;
                vs[i].v = vs[v].v + 1;
            }
        }
    }
    queue_clear(&q);
 
    if(y){
        v = e;
        i = 1;
        while(v != s){
            v = vs[v].p;
            ++i;
        }
        p = (word_t*)malloc((size_t)i * sizeof(word_t));
        if(p == NULL)
            return NULL;
 
        d = p;
        for(*d++ = e; e != s; e = vs[e].p)
            *d++ = vs[e].p;
        
        for(--d, j = p; j < d; ++j, --d){
            v  = *d;
            *d = *j;
            *j = v;
        }
        *m = i;
    }
    free(vs);
    return p;
}
 
/*
ввод неориентированного графа, формат
    N - кол-во вершин  M - кол-во рёбер
*/
byte_t** graph_input(FILE* _in, int* n){
    int      i, j, vn, em, a, b;
    byte_t** g;
    if((fscanf(_in, "%d %d", &vn, &em) != 2) || (vn <= 1) || (em <= 1))
        return NULL;
 
    g = (byte_t**)malloc((size_t)vn * sizeof(byte_t*));
    if(g == NULL)
        return NULL;
 
    for(i = 0; i < vn; ++i){
        g[i] = (byte_t*)calloc((size_t)vn, sizeof(byte_t));
        if(g[i] == NULL){
            i -= 1;
            goto err;
        }
    }
 
    for(i = 0; i < em; ++i){
        if(fscanf(_in, "%d %d", &a, &b) == 2){
            if((a < vn) && (b < vn))
                g[a][b] = g[b][a] = 1;
        } else
            break;
    }
    *n = vn;
    return g;
err:
    for(j = i; j >= 0; --j)
        free(g[j]);
    free(g);
    return NULL;
}
 
//удаление графа из памяти
void graph_free(byte_t** g, int n){
    int i;
    for(i = 0; i < n; ++i)
        free(g[i]);
    free(g);
}
 
//---------------
//вставка
int queue_push(queue_t* q, word_t v){
    node_t* p = (node_t*)malloc(sizeof(node_t));
    if(p != NULL){
        p->v    = v;
        p->next = NULL;
        if(q->h == NULL)
            q->h = q->t = p;
        else {
            q->t->next = p;
            q->t = p;
        }
    }
    return (p != NULL);
}
 
//извлечение
void queue_pop(queue_t* q){
    node_t* t;
    if(q->h != NULL){
        t    = q->h;
        q->h = q->h->next;
        free(t);
        if(q->h == NULL)
            q->t = NULL;
    }
}
 
//удаление всех
void queue_clear(queue_t* q){
    while(! queue_empty(q))
        queue_pop(q);
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 3.8 из 5
Похожие ответы