Lab_11

#include<stdio.h>
#include<stdlib.h>
int i;
struct node
{
int vertex;
struct node* next;
};
struct node* createNode(int v);
struct Graph
{
int numVertices;
int* visited;
struct node** adjLists;
};
void DFS(struct Graph* graph, int vertex)
{
struct node* adjList = graph->adjLists[vertex];
struct node* temp = adjList;
graph->visited[vertex] = 1;
printf("Visited %d \n", vertex);
while (temp != NULL)
{
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0)
{
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}
struct node* createNode(int v)
{
struct node* newNode =(struct node ) malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
struct Graph createGraph(int vertices)
{
struct Graph* graph = (struct Graph )malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices* sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
for(i=0;i< vertices;i++)
{
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v< graph->numVertices; v++)
{
struct node* temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp)
{
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
int main()
{
struct Graph* graph = createGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 0, 3);
addEdge(graph, 1, 2);
addEdge(graph, 2, 4);
printGraph(graph);
DFS(graph, 2);
getch();
return 0;
}