Using the BFTraversal algorithm and the following graph, list the order that the

Question

Using the BFTraversal algorithm and the following graph, list the order that the vertices are visited starting from G and the distance to the vertex. For example: Node G means node G is the starting node. G will be your starting point in the graph above. Please complete you answer in form: G 0 B 1

Explanation / Answer

#include #include #include "input_error.h" #define VertexToSearch 1 typedef struct edge { int vertexIndex; struct edge *edgePtr; } edge; typedef struct vertex { int vertexKey; struct edge *edgePtr; int visited; int distance; } vertex; typedef struct queue { struct vertex v; struct queue* next; }queue; int vertexCount = 0; struct vertex graph[]; queue* q = NULL; void load_file(char*); void insertEdge(int, int, struct vertex[]); void InsertVertex(int, struct vertex[]); void printGraph(); void bfs(); void print_distances(); void enqueue(vertex); vertex dequeue(); enum error program_error; int count; int main(int argc, char** argv) { load_file(argv[1]); printGraph(); bfs(); print_distances(); return 0; } void load_file(char* filename) { int vertex1; int vertex2; FILE* file = fopen(filename, "r"); if (file == NULL) { printf("%s did not open ", filename); program_error = FILE_FAILED_TO_OPEN; exit(program_error); } fscanf(file, "%d", &count); graph[count]; for (int i = 0; i edgePtr; } e1 = (struct edge *) malloc(sizeof (*e1)); e1->vertexIndex = vertex2; e1->edgePtr = NULL; if (e) e->edgePtr = e1; else graph[vertex1 - 1].edgePtr = e1; e = graph[vertex2 - 1].edgePtr; while (e && e->edgePtr) { e = e->edgePtr; } e2 = (struct edge *) malloc(sizeof (*e2)); e2->vertexIndex = vertex1; e2->edgePtr = NULL; if (e) e->edgePtr = e2; else graph[vertex2 - 1].edgePtr = e2; } void printGraph() { int i; struct edge *e; for (i = 0; i vertexIndex); e = e->edgePtr; } printf(" "); } } void bfs() { graph[0].distance = 0; enqueue(graph[0]); while(q != NULL){ vertex u = dequeue(); while(u.edgePtr != NULL){ if(graph[u.edgePtr->vertexIndex].distance == -1){ graph[u.edgePtr->vertexIndex].distance = u.distance + 1; enqueue(q, graph[u.edgePtr->vertexIndex]); } u.edgePtr = u.edgePtr->edgePtr; } } } void print_distances() { for (int i = 0; i next = NULL; new->v = v; if (q == NULL) { q = malloc(sizeof(queue)); q = new; } else { while (q->next != NULL) { q = q->next; } //add new node at the end q->next = new; } } vertex dequeue() { vertex v; queue* tempPtr; tempPtr = q; //makes temp the address of the node to be deleted v = tempPtr->v; q = q->next; //sets the new head as the address of the next node return v; }

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.