Adjacency List

Due on 2014-11-17, 23:59 IST

A graph is abstractly a collection of vertices which are labelled by

non-negative integers, and a collection of edges. A graph called an

undirected graph if we talk of merely the presence of an edge between

vertices i and j, rather than its direction.

For example, the following is a graph:

In this problem, you are given the edges in an undirected graph. An

edge is a pair of non-negative integers (i, j) which indicates that

the vetex i is connected to vetex j by an edge.

Afterwards, you will be given a vertex number n. You have to output

the list of vertices which are connected n by an edge, in the order in

which the edges were input.

Input

You are given the following.

1. The first line contains an integer, E, between 1 and 1000

2. This is followed by E lines, where each containing a pair of

numbers i and j where i and j are both non-negative integers <=

34,000. No edge will be listed more than once.

3. The last line contains a non-negative integer n <= 34,000. n is

assured to be a vertex listed in one of the E lines in part (2).

Output

You have to output the list of nodes to which n has an edge, in the

order in which the edges were input, one line for each vertex.

Source Code:

#include <stdio.h>
#include <stdlib.h>

// A structure to represent an adjacency list node
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};

// A structure to represent an adjacency liat
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;

// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;

return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, 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 begining
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph,int a1)
{
int v,i,j,temp;
// for (v = 0; v < graph->V; ++v)
// {
int a[35000],count;
count=0;
struct AdjListNode* pCrawl = graph->array[a1].head;
// printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl)
{
a[count++]=pCrawl->dest;
// printf("%d\n", pCrawl->dest);
pCrawl = pCrawl->next;
}
//To print in ascending order.
for(i=count-2;i>=0;i--){
for(j=0;j<=i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<count;i++)
{
printf("%d\n",a[i]);

}
// }
}

// Driver program to test above functions
int main()
{
// create the graph given in above fugure
int V ,v1,v2,i;
scanf("%d",&V);
struct Graph* graph = createGraph(V);
for(i=0;i<V;i++)
{
scanf("%d",&v1);
scanf("%d",&v2);
addEdge(graph,v1,v2);
}
// print the adjacency list representation of the above graph
scanf("%d",&v1);

printGraph(graph,v1);

return 0;
}

Adjacency List representation of graphs in C programming

Adjacency List

Source Code: