Adjacency list representation, Data Structure & Algorithms

Adjacency list representation

An Adjacency list representation of Graph G = {V, E} contains an array of adjacency lists mentioned by adj of V list. For each of the vertex u?V, adj[u] contains all vertices adjacent to u in the graph G.

Consider the graph of Figure.

636_Adjacency list representation.png

Figure: A Graph

Given is the adjacency list representation of graph of above Figure:

adj [1] = {2, 3, 5}

adj [2] = {1, 4}

adj [3] = {1, 4, 5}

adj [4] = {2, 3, 5}

 adj [5] = {1, 3, 4}

An adjacency matrix representation of a Graph G=(V, E) is a matrix

The adjacency matrix for the graph of Figure is following:

 

1

2

3

4

5

1

0

1

1

0

1

 

2

 

1

 

0

 

0

 

1

 

1

 

3

 

1

 

0

 

0

 

1

 

1

 

4

 

0

 

1

 

1

 

0

 

1

 

5

 

1

 

0

 

1

 

1

 

0

 

 

 

 

 

 

Observe that the matrix is symmetric along the main diagonal. If we described the adjacency matrix as A and the transpose as AT , then for undirected graph G as above, A = AT.

Posted Date: 4/11/2013 3:46:05 AM | Location : United States







Related Discussions:- Adjacency list representation, Assignment Help, Ask Question on Adjacency list representation, Get Answer, Expert's Help, Adjacency list representation Discussions

Write discussion on Adjacency list representation
Your posts are moderated
Related Questions
Define File organization''s and it''s types

how to draw a 5 inch square on the screen using * symbol

Define what an algorithm is and outline the characteristics of a good algorithm.

How To implement stack using two queues , analyze the running time of the stack operations ?

Write an algorithm to print all even numbers in descending order and draw the flowchart

Representation of data structure in memory is known as: Abstract data type

given the string "Data Structures & , Algorithms", write a program that uses sequential search to return index of ''&''

1)    The set of the algorithms whose order is O (1) would run in the identical time.  True/False 2)    Determine the complexity of the following program into big O notation:

The controversy of RISC versus CISC never ends. Suppose that you represent an advocate for the RISC approach; write at least a one-page critic of the CISC approach showing its disa

Data Structure and Methods: Build an array structure to accomodate at least 10 elements. Provide routines for the following: An initializer. A routine to populate (