Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #define size 500
- int no_of_vertex, i, graph[50][50], j, visited_seq = -1, f = 0, r = 0;
- char vertex[26];
- char visited_array[100];
- char q[size+1];
- void visit(char ch)
- {
- visited_seq++;
- visited_array[visited_seq] = ch;
- }
- int is_visit(char ch)
- {
- for(i = 0; i <= visited_seq ; i++)
- {
- if(visited_array[i] == ch)
- {
- return 1; // If Found
- }
- }
- return 0; // If not found
- }
- void print_array()
- {
- for(i = 0; i <= visited_seq ; i++)
- printf("%c ", visited_array[i]);
- }
- void enqueue(char ch)
- {
- r = (r+1) % (size + 1);
- q[r] = ch;
- }
- char dequeue()
- {
- f = (f+1) % (size+1);
- char ch = q[f];
- q[f] = '\0';
- return ch;
- }
- void findAdjacentList(char ch)
- {
- for(i = 0; i < no_of_vertex ; i++)
- {
- if(vertex[i] == ch)
- {
- for(j = 0 ; j < no_of_vertex ; j++)
- {
- if(graph[i][j] == 1)
- {
- if( is_visit(vertex[j]) == 0 ){
- enqueue(vertex[j]);
- }
- }
- }
- }
- }
- }
- void BFS()
- {
- enqueue(vertex[0]);
- while(f != r)
- {
- char ch = dequeue();
- findAdjacentList(ch);
- if(is_visit(vertex[j]) == 0)
- visit(ch);
- }
- }
- void createGraph()
- {
- for(i = 0 ; i < 26 ; i++)
- vertex[i] = i+65;
- printf("How many vertex: ");
- scanf("%d", &no_of_vertex);
- for(i = 0 ; i < no_of_vertex ; i++)
- {
- for(j = 0 ; j< no_of_vertex ; j++)
- {
- graph[i][j] = 0;
- }
- }
- for(i = 0 ; i < no_of_vertex ; i++)
- {
- for(j = i+1 ; j< no_of_vertex ; j++)
- {
- scanf("%d", &graph[i][j]);
- if(graph[i][j] == 1)
- graph[j][i] = 1;
- }
- }
- }
- int main()
- {
- createGraph();
- BFS();
- print_array();
- return 0;
- }
Add Comment
Please, Sign In to add comment