Pagini recente » Cod sursa (job #1483416) | Cod sursa (job #258735) | Cod sursa (job #2613499) | Cod sursa (job #2688374) | Cod sursa (job #2888910)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//EDGES
typedef struct edge {
int leftNode;
int rightNode;
} edge;
typedef struct graphEdges {
edge* edges;
int numNodes;
int numEdges;
} graphEdges;
//POINTERS/VERTEX
typedef struct vertex {
int name;
struct vertex** neighbors;
int numNeighbors;
// int* weights;
} vertex;
typedef struct graphVertex {
int numNodes;
int numEdges;
vertex* nodes;
} graphVertex;
int stack[100];
int indexStack = 0;
void push(int value)
{
if (indexStack < 100)
stack[indexStack++] = value;
else
printf("Dimensiune stiva depasita!\n");
}
int pop()
{
//verificare daca sunt elemente in stiva
if (indexStack > 0) {
int value = stack[--indexStack];
stack[indexStack] = 0;
return value;
}
printf("Stiva este goala!\n");
return (int)0;
}
void bfs_edges(graphEdges graph, int n, int startNode, int* visited)
{
int C[10001];
int* D = NULL;
int p, u, x;
p = u = 1;
C[1] = startNode;
D = (int*)calloc(n, sizeof(int));
D[startNode] = 0;
visited[startNode] = 1;
int d = 1;
int ok = 0;
while (p <= u)
{
ok = 0;
x = C[p];
for (int i = 0; i <= graph.numEdges; i++)
{
if (graph.edges[i].leftNode == x && visited[graph.edges[i].rightNode] == 0)
{
ok = 1;
D[graph.edges[i].rightNode] = d;
u++;
C[u] = graph.edges[i].rightNode;
visited[graph.edges[i].rightNode] = 1;
}
}
if(ok == 1)
d++;
p++;
}
for (int i = 0; i < n; i++)
if (D[i] == 0 && i != startNode)
D[i] = -1;
FILE* g = fopen("bfs.out", "w");
for (int i = 1; i <= n; i++)
fprintf(g, "%d ", D[i]);
fclose(g);
//printf("%d %d\n", C[i], D[i]);
}
graphEdges readGraphEdgeList(const char* fileName, int* S)
{
graphEdges graph;
graph.numEdges = 0;
graph.edges = NULL;
FILE* f = fopen(fileName, "r");
if (f == NULL)
return graph;
//TODO
int n = 0;
fscanf(f, "%d", &n);
graph.numNodes = n;
int m = 0;
fscanf(f, "%d", &m);
graph.numEdges = m;
int s = 0;
fscanf(f, "%d", &s);
*S = s;
graph.edges = (edge*)malloc(m * sizeof(edge));
//int no = 0;
for (int i = 0; i < graph.numEdges; i++)
{
int auxi = 0;
int auxj = 0;
fscanf(f, "%d", &auxi);
fscanf(f, "%d", &auxj);
//graph.edges = (edge*)realloc(graph.edges, (m + 1) * sizeof(edge));
graph.edges[i].leftNode = auxi;
graph.edges[i].rightNode = auxj;
//m++;
}
//graph.numEdges = m;
fclose(f);
return graph;
}
int main()
{
//EDGES
int S = 0;
graphEdges graphE = readGraphEdgeList("bfs.in", &S);
int visited3[100] = { 0 }; //we assume fewer than 100 nodes
bfs_edges(graphE, graphE.numNodes, S, visited3);
printf("\n");
return 0;
}