Data structure - Graphs

GRAPHS

class graph

{

       int v;      //number of vertices

       LinkedList<Integer> adj[]; // “array of” linked lists.

       void AddEdge(int v, int w)

       {

            Adj[v].add(w); //adj[0], adj[1],….adj[v-1] are initialized in the ctor of the graph class.

       }

}

Couple of points –

a)      Graph contains a set of vertices called nodes.

b)      Graph contains ordered pair of the form (u, v) called EDGE.

c)       (u, v) is not same as (v, u) in a directed graph (di-graph).

Real life uses – Social network, paths in a city, network, web crawler, garbage collection.

Representation –

Adjacency list. Pros – less space. Cons – To find if edge exits, it will take O(v) time.

Adjacency matrix. Pros – Quick to find edge exists or not O(1). Con – more space.