**Representation of Graphs**

We can represent any type of graph, directed, undirected, weighted, unweighted, simple, etc using any of the below methods:

- Adjacency list
- Adjacency matrix

We will use the below directed and undirected graphs respectively as our reference and represent them through list and matrix.

__Fig 1:__

__Fig 2: __

**Adjacency List**

Follow the steps and match your answer with my answer.

**Step 1:** choose any graph, whichever you like from the above two given ones

**Step 2:** create an array named Adj with size as the number of vertices of your chosen graph

**Step 3:** this array will have indices as the vertices name, let us say, I chose fig 1, then my indices are 1, 2, 3, 4, 5. this array will look as below

__Fig 3:__

**Step 4:** this array you created is an array of pointers. don't store any value. instead, you will be storing addresses in step 5

**Step 5:** create a node with two fields, value and next(address).

**Step 6:**

now, this is a very simple step, very very simple, just pay heed carefully. in fig 1, vertex 1 is connected to vertex 2 and vertex 5.

so create two nodes, store value 2 in one node and value 5 in other.

these nodes will look like below

__Fig 4: __

Now, Adj[1] will connect to these two newly created nodes. (You can connect 2 first or 5 first, your wish)

This step will look something like:

__Fig 5:__

So that was it.

Now complete your adjacency list.

You can match your adjacency list with the below fig 6 corresponding to fig 1 and fig 7 corresponding to fig 2

__Fig 6:__

__Fig 7:__

Congrats :)

**Adjacency Matrix**

Follow the steps and match your answer with my answer.

**Step 1:** choose any graph, whichever you like

**Step 2:** create a 2-d array named Adj with size as the (number of vertices x number of vertices) of your chosen graph, I chose Fig 1

**Step 3:** this array will look like this

__Fig 8: __

**Step 4:** use the following definition for storing the values in the adjacency matrix

Adj[i][j]={ 0 or ∞ when edge ij do not belong to the graph, 1 when edge ij do belong to graph }

depending on the problem, the absence of an edge is represented by 0 or ∞

**Step 5:** match your adjacency matrix with below fig 9 corresponding to fig 1 and fig 10 corresponding to fig 2

__Fig 9:__

__Fig 10:__

Congrats once again :)

__Analysis of Space__

i) Adjacency List

Can you analyze how much space an adjacency list will be using? Look carefully.

First, you need an array of pointers of size=number of vertices in graph. So you need O(V) space for this....(actually, O(v) has to be multiplied by size of a pointer, but we are doing asymptotic analysis, so we will ignore that part for now)

Now, this is a very simple step, how many nodes you need in adjacency list representation of Fig 1? You need eight nodes. How many edges you have? You have 4 edges. See a pattern? You are required to have '2 x number of edges' extra nodes. So you need O(2E) space, which is aysmptotically equal to O(E)

A second observation, how many nodes you need in adjacency list representation of Fig 2? You need eight nodes. How many edges you have? You have 4 edges. See a pattern again? You are required to have 'number of edges' extra nodes. So you need O(E) space.

Hence total space needed for fig 1=O(V+2E)=O(V+E)

And total space needed for fig 2=O(V+E)

To be noted, adjacency listrepresentation has always a need of O(V+E) space irrespective of graph being directed/undirected/weighted/unweighted, etc

ii)Adjacency Matrix

This is easier than adjacency list. You have a 2-d square matrix of V*V elements. Space needed? O(V^{2}).

To be noted, adjacency matrix representation has always a need of O(V^{2}) space irrespective of graph being directed/undirected/weighted/unweighted, etc

__Some useful terminologies of graphs__

**Transpose of a graph:** Transpose of a graph G=(V,E) is G^{T}=(V,E^{T}) such that, G^{T} is G with all its edges reversed. For example, (a,b) is an edge in a directed graph, then its transpose will have now (b,a)
**Handshaking Lemma:**

****i) The sum of degrees of all the vertices in an undirected graph equals twice the number of edges.

ii) The sum of indegrees of all the vertices in a directed graph equals the number of edges.

The sum of outdegrees of all the vertices in a directed graph equals the number of edges.

Explanation for undirected graph: Each edge is incident on two vertices. Therefore each edge is counted twice