basically I am trying to explore all the vertices of the graph using DFS. there is not compile time error, but while execution it gives error. the graph is undirected so if there is an edge from 0 to 3, so there is from 3 to 0 as well.
the run time error is shown in picture bellow: enter image description here
this the program:
#include <stdio.h>
#include <stdlib.h>
struct tileList
{
int dest;
struct tileList* next;
};
struct list
{
struct tileList *head;
};
struct Map
{
int T; //Tiles
struct list* array;
}Map;
struct tileList* newtileList(int dest)
{
struct tileList* newNode =
(struct tileList*) malloc(sizeof(struct tileList));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
int visited[100];
void dfs(struct Map* gr, int t);
// A utility function that creates a map of T tile
struct Map* createMap(int T)
{
struct Map* map = (struct Map*) malloc(sizeof(struct Map));
map->T = T;
// Create an array of adjacency lists. Size of array will be T
map->array = (struct list*) malloc(T * sizeof(struct list));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < T; ++i)
map->array[i].head = NULL;
return map;
}
// Adds an edge to an undirected map
void directPath(struct Map* map, int src, int dest)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the beginning
struct tileList* newNode = newtileList(dest);
newNode->next = map->array[src].head;
map->array[src].head = newNode;
// Since map is undirected, add an edge from dest to src also
newNode = newtileList(src);
newNode->next = map->array[dest].head;
map->array[dest].head = newNode;
}
// function to print the adjacency list representation of map
void printMap(struct Map* map)
{
int t;
for (t = 0; t < map->T; ++t)
{
struct tileList* tiles = map->array[t].head;
printf("n Adjacency list of tiles %dn head ", t);
while (tiles)
{
printf("-> %d", tiles->dest);
tiles = tiles->next;
}
printf("n");
}
}
void dfs(struct Map* gr, int t)
{
printf("%d ", t);
visited[t]=1;
struct tileList* temp_node = gr->array[t].head;
while(temp_node!=NULL)
{
if(visited[temp_node->dest] !=1)
{
printf("tMoting from %d to %d", t, temp_node->dest);
printf("n");
dfs(&Map,temp_node->dest);
}
temp_node=temp_node->next;
}
return;
}
int main()
{
// create the map
int T = 8; //number of vertices(tiles)
struct Map* map = createMap(T);
directPath(map, 0, 1);
directPath(map, 0, 2);
directPath(map, 1, 2);
directPath(map, 1, 3);
directPath(map, 1, 4);
directPath(map, 2, 3);
directPath(map, 3, 4);
directPath(map, 4, 5);
directPath(map, 5, 6);
directPath(map, 6, 3);
directPath(map, 7, 3);
// print the adjacency list representation of the above map
printMap(map);
for(int i=0; i<T; i++)
{
visited[i] =0;
}
dfs(map, 0);
printf("n");
return 0;
}
Aucun commentaire:
Enregistrer un commentaire