алгоритм для BFS, реализованный здесь, упоминается в Cormen. Этот код, однако, по какой-то причине выдает неверные результаты, даже для тривиальных графов Все до создания списка Смежности работает нормально.
Вот весь код:
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#define size 5
struct node *nodelist = NULL;
struct node
{
int nodeid;
int parentid;
int sourcedist;
char *color;
};
struct graph *adjlist = NULL;
struct graph
{
struct listnode *list;
int count;
};
struct listnode
{
int nodeid;
struct listnode *next;
};
struct listnode *createnode(int id)
{
struct listnode *newnode = (struct listnode *)malloc(sizeof(struct listnode));
(*newnode).nodeid = id;
(*newnode).next = NULL;
return newnode;
}
int addtoadjlist(int u, int v)
{
struct listnode *newnode = createnode(v);
if((*(adjlist + u)).list == NULL)
{
(*(adjlist + u)).list = newnode;
(*(adjlist + u)).count++;
}
else
{
(*newnode).next = (*(adjlist + u)).list;
(*(adjlist + u)).list = newnode;
(*(adjlist + u)).count++;
}
}
int disp(int totalnodes)
{
int degreesum = 0, i;
struct listnode *currentnode = NULL;
for(i = 0; i < totalnodes; i++)
{
currentnode = (*(adjlist + i)).list;
printf("\n node %d -> ",i);
while(currentnode != NULL)
{
printf("%d -> ",(*currentnode).nodeid);
currentnode = (*currentnode).next;
}
printf("NULL | Degree: %d",(*(adjlist + i)).count);
degreesum += (*(adjlist + i)).count;
}
return degreesum/2;
}
int dispnodeinfo(int totalnodes)
{
int i;
for(i = 0; i < totalnodes; i++)
{
printf("\n node %d: parent %d| distance from source %d| color %c",(*(nodelist + i)).nodeid,(*(nodelist + i)).sourcedist,(*(nodelist + i)).color);
}
}
int *BFSQf;
int *BFSQr;
int ENQ(int x)
{
if(BFSQr == NULL)
{
BFSQr = BFSQf;
*BFSQf = x;
}
else
{
BFSQr++;
*BFSQr = x;
}
return 0;
}
int DEQ()
{
int temp;
if(BFSQr == NULL)
return -1;
else if(BFSQr == BFSQf)
{
BFSQr = NULL;
return *BFSQf;
}
else
{
temp = *BFSQr;
BFSQr--;
return temp;
}
}
int bfs(int s)
{
(*(nodelist + s)).color = "G";
(*(nodelist + s)).sourcedist = 0;
BFSQr = NULL; //Empty the Queue;
ENQ(s);
while(BFSQr != NULL)
{
int u = DEQ();
struct listnode *currentnode = (*(adjlist + u)).list;
while(currentnode != NULL)
{
int nodeid = (*currentnode).nodeid;
if((*(nodelist + nodeid)).color == "W")
{
(*(nodelist + nodeid)).color = "G";
(*(nodelist + nodeid)).sourcedist = (*(nodelist + u)).sourcedist + 1;
(*(nodelist + nodeid)).parentid = u;
ENQ(nodeid);
}
currentnode = (*currentnode).next;
}
(*(nodelist + u)).color = "B";
}
}
int main(void)
{
int totalnodes, choice = 0, u, v, i, s;
printf("\n Enter the number of nodes in the graph: ");
scanf("%d",&totalnodes);
nodelist = (struct node *)malloc(totalnodes*sizeof(struct node));
for(i = 0; i < totalnodes; i++)
{
(*(nodelist + i)).nodeid = i;
(*(nodelist + i)).parentid = INT_MIN;
(*(nodelist + i)).sourcedist = INT_MAX;
(*(nodelist + i)).color = "W";
}
adjlist = (struct garph *)malloc(totalnodes*sizeof(struct graph));
for(i = 0; i < totalnodes; i++)
{
(*(adjlist + i)).list = NULL;
(*(adjlist + i)).count = 0;
}
while(choice != 3)
{
printf("\n\n 1.) Add Edges. \n 2.) Display \n 3.) Exit. \n Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter source and destination vertices for the edge (starting 0): ");
scanf("%d %d",&u,&v);
addtoadjlist(u,v);
//addtoadjlist(v,u);
break;
case 2:
disp(totalnodes);
//printf("\n Total edges = %d ",disp(totalnodes)); only for non directed graphs.
break;
case 3:
break;
default:
printf("\n Invalid input.");
}
}
BFSQf = (int *)malloc(totalnodes*sizeof(int));
BFSQr = NULL; // Queue Empty.
printf("\n Enter source node to apply BFS: ");
scanf("%d",&s);
bfs(s);
dispnodeinfo(totalnodes);
return 0;
}
Для ввода: 6 1 0 1 1 0 3 1 1 4 1 4 3 1 3 1 1 2 4 1 2 5 1 5 5 2 3 3
Список смежности, который я получаю:
node 0 -> 3 -> 1 -> NULL | Degree: 2
node 1 -> 4 -> NULL | Degree: 1
node 2 -> 5 -> 4 -> NULL | Degree: 2
node 3 -> 1 -> NULL | Degree: 1
node 4 -> 3 -> NULL | Degree: 1
node 5 -> 5 -> NULL | Degree: 1
что правильно. Но полученная продукция:
node 0: parent 2147483647| distance from source 984096070| color
node 1: parent 1| distance from source 984096072| color
node 2: parent 2147483647| distance from source 984096070| color
node 3: parent 0| distance from source 984096072| color
node 4: parent 2| distance from source 984096072| color
node 5: parent 2147483647| distance from source 984096070| color
Только идентификаторы узла были назначены правильно, все остальные являются поддельными значениями. Я вызвал displaynodeinfo () сразу после первоначального присваивания в main (), например:
int main(void)
{
....
nodelist = (struct node *)malloc(totalnodes*sizeof(struct node));
for(i = 0; i < totalnodes; i++)
{
(*(nodelist + i)).nodeid = i;
(*(nodelist + i)).parentid = INT_MIN;
(*(nodelist + i)).sourcedist = INT_MAX;
(*(nodelist + i)).color = "W";
}
displaynodeinfo(totalnodes);
.....
}
Здесь все же я получил поддельные назначения, кроме узловых. В чем дело? Пожалуйста, помогите.