Βοήθεια με αλγόριθμο

[skoobydoo]

θα ηθελα καποιος αν μπορει να μου εξηγησει τον παρακατω αλγοριθμο γιατι δεν μπορω να καταλαβω τι γινεται ακριβως.Ευχαριστω αν μπορει να βοηθησει καποιος

 

 

 

# include<stdio.h>

 

# define size 20

 

# define T 1

 

# define F 0

 

struct Edge

 

{ int terminal;

 

struct Edge *next;

 

};

 

struct Vertex

 

{ int visit;

 

int vertex_no;

 

char info;

 

int path_length;

 

struct Edge *Edge_Ptr;

 

};

 

struct Q

 

{ int info;

 

struct Q *next;

 

};

 

void Table(int , int matrix , struct Vertex vert);

 

struct Edge *Insert_Vertex (int , struct Edge *);

 

void BFS ( int , struct Vertex vert );

 

void Input(int, int mat );

 

void Output(int number, int mat );

 

struct Q *Insert_Queue(int vertex_no, struct Q *first);

 

struct Q *Delete_Queue(int *vertex_no, struct Q *first);

 

/* Insert vertex into connectivity list */

 

struct Edge * Insert_Vertex (int vertex_no, struct Edge

 

*first) {

 

struct Edge *new1, *current;

 

new1 = (struct Edge *) malloc(sizeof(struct Edge));

 

new1->terminal = vertex_no;

 

new1->next = NULL;

 

if (!first)

 

return (new1);

 

for (current = first; current->next; current = current->next);

 

current->next = new1;

 

return (first);

 

}

 

/* Insert vertices into queue */

 

struct Q * Insert_Queue(int vertex_no, struct Q *first)

 

{ struct Q *new1, *current;

 

new1 =(struct Q *) malloc(sizeof(struct Q));

 

new1->info = vertex_no;

 

new1->next = NULL;

 

if (!first)

 

return (new1);

 

for (current = first; current->next; current = current->next);

 

current->next = new1;

 

return (first);

 

}

 

struct Q * Delete_Queue(int *vertex_no, struct Q *first)

 

{ struct Q *previous;

 

if (!first)

 

return (NULL);

 

*vertex_no = first->info;

 

previous = first;

 

first = first->next;

 

free(previous);

 

return (first);

 

}

 

/* Initializing entries */

 

void Table(int vertex_num, int matrix ,

 

struct Vertex vert)

 

{

 

int i, j;

 

for (i = 0; i < vertex_num; i++)

 

{ vert .visit = F;

 

vert .vertex_no = i+1;

 

vert .info = ‘A’+ i;

 

vert .path_length = 0;

 

vert .Edge_Ptr = NULL;

 

}

 

for (i =0; i < vertex_num ; i++)

 

for (j =0; j < vertex_num ; j++)

 

if (matrix [j] > 0 )

 

vert .Edge_Ptr = Insert_Vertex (j, vert .Edge_Ptr);

 

}

 

/* Computing path length */

 

void BFS ( int index, struct Vertex vert )

 

{ struct Q *queue = NULL;

 

struct Edge *Link;

 

vert [index].visit = T;

 

queue = Insert_Queue(index, queue);

 

while(queue)

 

{ queue = Delete_Queue(&index, queue);

 

for ( Link = vert [index].Edge_Ptr; Link; Link = Link->next)

 

{ if (vert [Link->terminal].visit == F)

 

{

 

vert[Link->terminal].visit = T;

 

vert[Link->terminal].path_length=vert[index].path_length+1;

 

queue = Insert_Queue(Link->terminal, queue);

 

}

 

}

 

}

 

}

 

 

 

/* Input function to read adjacency matrix */

 

void Input(int number, int mat )

 

{ int i, j;

 

printf(”\n Input the adjacency matrix \n”);

 

for (i =0; i < number; i++)

 

{ for (j=0; j < number; j ++)

 

{ scanf(”%d”, &mat [j]);

 

}

 

printf(”\n”);

 

}

 

}

 

/* Output function to display adjacency matrix */

 

void Output(int number, int mat )

 

{ int i, j;

 

printf(”\n Adjacency matrix \n”);

 

for (i =0; i < number; i++)

 

{ for (j=0; j < number; j ++)

 

{ printf(” %d”, mat [j]);

 

}

 

printf(”\n”);

 

}

 

}

 

/* Function main */

 

void main()

 

{ int i, number, index;

 

int mat ;

 

struct Vertex vert ;

 

struct Edge *List;

 

printf(”\n Input the number of vertices in the graph: “);

 

scanf(”%d”, &number);

 

Input(number, mat);

 

Output(number, mat);

 

Table(number, mat, vert);

 

printf(”\n Input the starting vertex 0- %d :”,number-1);

 

scanf(”%d”, &index);

 

BFS (index, vert);

 

printf(”\n Path length of the vertex from %c”, vert[index].info);

 

printf(”\n Vertex Length Vertex Connectivity \n “);

 

for (i = 0; i < number; i++)

 

{ printf(”\n %c %d “,vert.info, vert.path_length);

 

for (List= vert.Edge_Ptr; List; List = List->next)

 

{ printf(” “);

 

putchar(List->terminal+’A');

 

}

 

}

 

}

[evabb]

γαμησε τα φιλε μου με μια πρωτη ματια δεν ειναι απλα αλγοριθμος αλλα ολοκληρος ορισμος του ειδους edge. ολο αυτο ειναι μεσα σε ενα αρχειο και εσυ μετα χρησιμοποιεις τις συναρτησεις αυτες για να κανεις την δουλεια που θελεις. απλα τις καλεις... λειπει το header file παντως νομιζω.... που δινει απλα τα ονομα των συναρτησεων που εχεις εδω

[drm]

Μία δομή με Vertices και edges, μάλλον γράφος ή δέντρο (δεν διαφέρουν και πολύ...)

[xwtiko]

Απο το λίγο που είδα ορίζει ενα γράφο με τα στοιχεία των κόμβων στο Vertex και εφαρμόζει αναζήτηση κατα πλάτος απο ενα κόμβο (BFS - Breadth-first search). Για περισσότερες πληροφορίες, ενδεικτικά δες :

http://en.wikipedia.org/wiki/Breadth-first_search

http://hamilton.bell.ac.uk/swdev2/notes/notes_18.pdf