Уважаемые, я испытываю трудности с обходом связного графа. пользуюсь псевдокодом алгоритма из кормена. к сожалению не могу его реализацию воплотить на си. самая большая проблема в том, что у меня задан список смежности и мне надо работать с ним. я думаю, что у кого-то должы были остаться коды для реализации этих алгоритмов. буду очень благодарен, если поделитесь. выдаю на суд, свой труд... может быть кому-то и пригодится | Код |
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct NODE {
int info;
struct NODE *next;
} node;
int KolVer, color[10]={0}, bfs_a[10], t, h;
node *adjacency_list;
//----------------------------------------------------------------------------
node *f1(int *KolVer) // Input Adjacency List
{
node *adjacency_list=NULL, *c=NULL;
printf("Kol-vo vershin: ");
scanf("%i", KolVer);
adjacency_list=(node *) malloc(*KolVer*sizeof(node));
for (int i=0; i<*KolVer; i++)
{
printf("%i - ", i+1);
scanf("%i", &adjacency_list[i].info);
if (adjacency_list[i].info != 0)
{
c=adjacency_list+i;
while (c->info != 0)
{
c->next=(node *) malloc(sizeof(node));
c=c->next;
scanf("%i", &c->info);
} //while not 0
c->next=NULL;
} // if not end of line
else adjacency_list[i].next=NULL; //if end of line
} // for i
return adjacency_list;
}
//----------------------------------------------------------------------------
void f2(node *adjacency_list, int KolVer) // Output Adjacency List
{
node *c=NULL;
int i;
for (i=0; i<KolVer; i++)
{
printf("%i - ", i+1);
c=adjacency_list+i;
while (c->info != 0)
{
printf("%i, ", c->info);
c=c->next;
}
puts("0");
}
}
//----------------------------------------------------------------------------
void dfs_visit(int v) // Deep First Search Visit
{
node *p=NULL;
color[v]=1;
printf("%d, ", v+1);
p=adjacency_list+v;
while ( p )
{
if ( color[(p->info)-1] == 0 )
dfs_visit((p->info)-1);
p=p->next;
}
}
//----------------------------------------------------------------------------
void dfs() // Deep First Search
{
printf("Start from: ");
int point;
scanf("%d", &point);
dfs_visit(point-1);
for (int i=0; i<KolVer; i++)
if ( color[i] == 0 )
dfs_visit(i);
printf("\n");
}
//----------------------------------------------------------------------------
void enqueue(int v)
{
bfs_a[t++]=v;
color[v]=1;
}
//----------------------------------------------------------------------------
void dequeue()
{
bfs_a[h++];
}
//----------------------------------------------------------------------------
void bfs(int v) // Breadth First Search
{
color[v]=1;
node *p=NULL;
p=adjacency_list+v;
while ( p )
{
if ( color[(p->info)-1] == 0 )
enqueue((p->info)-1);
p=p->next;
}
dequeue();
}
//----------------------------------------------------------------------------
void bfs_main()
{
h=0; t=1;
printf("Start from: ");
int point;
scanf("%d", &point);
bfs_a[0]=point-1;
bfs(bfs_a[0]);
while ( h!=t )
bfs(bfs_a[h]);
for (int i=0; i<KolVer; i++)
if ( color[i] == 0 )
{
enqueue(i);
while ( h!=t )
bfs(bfs_a[h]);
}
for (i=0; i<KolVer; i++)
printf("%d, ", bfs_a[i]+1);
printf("\n");
}
//----------------------------------------------------------------------------
int menu()
{
int a;
while (1) {
printf("Menu:\n");
printf(" 1 - Input Adjacency List\n");
printf(" 2 - Output Adjacency List\n");
printf(" 3 - Deep-First-Search (DFS)\n");
printf(" 4 - Breadth-First-Search (BFS)\n");
printf(" 0 - Exit\n");
printf("Select: ");
scanf("%d", &a);
switch (a) {
case 0: return 0;
case 1: adjacency_list=f1(&KolVer); break;
case 2: f2(adjacency_list, KolVer); break;
case 3: dfs(); break;
case 4: bfs_main(); break;
default: printf("Wrong character!!!\n");
}
}
}
//----------------------------------------------------------------------------
main()
{
clrscr();
menu();
return 0;
}
|
|
DFS / BFS, обход в глубину / обход в ширину 
Загрузка ...
