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.

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 A^T , then for undirected graph G as above, A = A^T.

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

Ask an Expert

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

Write your message here..

Related Questions

File organization, Define File organization''s and it''s types Define File organization''s and it''s types

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

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

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

Algorithms, Write an algorithm to print all even numbers in descending orde... Write an algorithm to print all even numbers in descending order and draw the flowchart

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

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

Determine the complexity, 1)    The set of the algorithms whose order is O ... 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:

Computer arhitecture, The controversy of RISC versus CISC never ends. Suppo... 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

Program to manipulate the data structure, Data Structure and Methods: ... 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 (