#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
void *data; /* lista ...*/
struct
Node *next;
} Node;
typedef struct {
Node *head;
Node *tail;
int size;
} LinkedList;
void init_list(LinkedList *list) {
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
void add_nth_node(LinkedList *list, int n, void *new_data) {
Node *prev, *curr;
Node *new_node;
if (list == NULL) {
return;
}
if (n > list->size) {
n = list->size;
} else if (n < 0) {
return;
}
curr = list->head;
prev = NULL;
while (n > 0) {
prev = curr;
curr = curr->next;
--n;
}
new_node = malloc(sizeof(Node));
if (new_node == NULL) {
perror("Not enough memory to add element!");
exit(-1);
}
new_node->data = new_data;
new_node->next = curr;
if (prev == NULL) {
/* Adica n == 0. */
list->head = new_node;
} else {
prev->next = new_node;
}
if (new_node->next == NULL) {
list->tail = new_node;
}
list->size++;
}
Node* remove_nth_node(LinkedList *list, int n) {
Node *prev, *curr;
if (list == NULL) {
return NULL;
}
if (list->head == NULL) { /* Lista este goala. */
return NULL;
}
if (n > list->size - 1) {
n = list->size - 1;
} else if (n < 0) {
return NULL;
}
curr = list->head;
prev = NULL;
while (n > 0) {
prev = curr;
curr = curr->next;
--n;
}
if (prev == NULL) {
/* Adica n == 0. */
list->head = curr->next;
} else {
prev->next = curr->next;
if (prev->next == NULL) {
list->tail = prev;
}
}
list->size--;
return curr;
}
int get_size(LinkedList *list) {
if (list == NULL) {
return -1;
}
return list->size;
}
void free_list(LinkedList **pp_list) {
struct Node *currNode;
if (pp_list == NULL || *pp_list == NULL) {
return;
}
while(get_size(*pp_list) > 0) {
currNode = remove_nth_node(*pp_list, 0);
free(currNode);
}
free(*pp_list);
*pp_list = NULL;
}
typedef struct { // Queue
LinkedList *list;
} Queue;
void init_q(Queue *q) {
q->list = malloc(sizeof(LinkedList));
if (q == NULL) {
perror("Not enough memory to initialize the queue!");
exit(-1);
}
init_list(q->list);
}
int get_size_q(Queue *q) {
return q->list->size;
}
int is_empty_q(Queue *q) {
return get_size_q(q) == 0;
}
void* front(Queue *q) {
if (q == NULL || q->list == NULL) {
return NULL;
}
return q->list->head->data;
}
void dequeue(Queue *q) {
struct Node *node;
if (q == NULL || q->list == NULL) {
return;
}
node = remove_nth_node(q->list, 0);
free(node);
}
void enqueue(Queue *q, void *new_data) {
add_nth_node(q->list, q->list->size, new_data);
}
void clear_q(Queue *q) {
struct Node *node;
while (!is_empty_q(q)) {
node = remove_nth_node(q->list, 0);
free(node);
}
}
void purge_q(Queue *q) {
clear_q(q);
free(q->list);
}
typedef struct {
LinkedList **neighbors; /* Listele de adiacenta ale grafului */
int nodes; /* Numarul de noduri din graf. */
} ListGraph;
void init_list_graph(ListGraph *graph, int nodes) { // grapf............
graph->nodes = nodes;
graph->neighbors = malloc(nodes * sizeof(LinkedList));
if (graph->neighbors == NULL) {
perror("Not enough memory to initialize the adjacency list!");
exit(-1);
}
for (int i = 0; i < nodes; ++i) {
graph->neighbors[i] = malloc(sizeof(LinkedList));
if (graph->neighbors[i] == NULL) {
perror("Not enough memory to initialize the adjacency list!");
exit(-1);
}
init_list(graph->neighbors[i]);
}
}
void add_edge_list_graph(ListGraph *graph, int src, int *dest) {
add_nth_node(graph->neighbors[src], (1 <<30), dest);
}
int has_edge_list_graph(ListGraph *graph, int src, int dest) {
Node *head = graph->neighbors[src]->head;
int crt_node;
while (head != NULL) {
crt_node = *(int *)head->data;
if (crt_node == dest) {
return 1;
}
head = head->next;
}
return 0;
}
LinkedList* get_neighbours_list_graph(ListGraph *graph, int node) {
return graph->neighbors[node];
}
void remove_edge_list_graph(ListGraph *graph, int src, int dest) {
Node *head = graph->neighbors[src]->head;
int node_index = 0;
int crt_node = 0;
while (head != NULL) {
crt_node = *(int *)head->data;
if (crt_node == dest) {
remove_nth_node(graph->neighbors[src], node_index);
return;
}
head = head->next;
++node_index;
}
}
void clear_list_graph(ListGraph *graph) {
for (int i = 0; i < graph->nodes; ++i) {
free_list(&graph->neighbors[i]);
}
free(graph->neighbors);
}
void min_path(ListGraph *lg, int *nodes_index, int source, FILE *out) { // bfs_min........
Queue *q = malloc(sizeof(Queue));
init_q(q);
struct Node *curr;
int i, v, *distance, *parents, *visited;
distance = malloc((lg->nodes)*sizeof(int));
parents = malloc((lg->nodes)*sizeof(int));
visited = malloc((lg->nodes)*sizeof(int));
for(i=0; i<lg->nodes; i++) {
visited[i] = 0;
parents[i] = 0;
distance[i] = 1000000;
}
visited[source] = 1; parents[source] = -1; distance[source] = 0;
enqueue(q, &nodes_index[source]);
while(q->list->head != NULL) {
v = *(int*)q->list->head->data; // bfs e la fel doar ca e pusa distanta
dequeue(q);
curr = lg->neighbors[v]->head;
while(curr != NULL) {
if(visited[*(int*)curr->data] == 0) { // *(int*)curr->data ... e vecinul
visited[*(int*)curr->data] = 1;
distance[*(int*)curr->data] = distance[v] + 1;
enqueue(q, &nodes_index[*(int*)curr->data]);
parents[*(int*)curr->data] = v;
}
curr = curr->next;
}
}
for(i=0; i<lg->nodes; i++) {
if(visited[i] == 0) { // daca nu e vizitat e -1
distance[i] = -1;
}
fprintf(out, "%d ", distance[i]);
}
free(parents); free(distance); free(visited);
purge_q(q);
free(q);
}
#define MAX_NODES 1000000
int main() {
FILE *in, *out;
char input[] = "bfs.in", output[] = "bfs.out";
int nodes, edges, source;
int nodes_index[MAX_NODES];
int x[MAX_NODES], y[MAX_NODES];
ListGraph *lg = malloc(sizeof(ListGraph));
in = fopen(input, "r");
out = fopen(output, "w");
fscanf(in, "%d %d %d", &nodes, &edges, &source);
init_list_graph(lg, nodes);
for (int i = 0; i < nodes; ++i) {
nodes_index[i] = i;
}
for (int i = 0; i < edges; ++i) {
fscanf(in, "%d %d", &x[i], &y[i]);
x[i]--; y[i]--;
add_edge_list_graph(lg, x[i], &y[i]);
}
source--;
min_path(lg, nodes_index, source, out);
clear_list_graph(lg);
free(lg);
fclose(in); fclose(out);
return 0;
}
Pricop Razvan Marius RazorBest