introduction to graphs
A Graph is a data structure that consists of a set of vertices (nodes) and a set of ordered pair of the form (u, v) called as edge. ordered because (u, v) is not the same as (v, u) in case of a directed graph. The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.
Pros: Saves space O(|V|+|E|). In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.
Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).
Directed and Undirected Graphs
- Directed Graphs: The Directed graphs are such graphs in which edges are directed in a single direction.
For Example, the below graph is a directed graph: - Undirected Graphs: Undirected graphs in which the edges are bi-directional. That is,in an edge we can go from both u to v and v to u.
Following is an example of an undirected graph with 5 vertices:
Representing Graphs
most commonly used representations of a graph:- Adjacency Matrix.
- Adjacency List.
- Adjacency Matrix: The Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
The adjacency matrix for the above example undirected graph is:
Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time. Queries like whether there is an edge from vertex 'u' to vertex 'v' are efficient and can be done O(1).
Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges), it consumes the same space. Adding a vertex is O(V^2) time.
Please see this for a sample Python implementation of adjacency matrix. - Adjacency List: Graph can also be implemented using an array of lists. That is every index of the array will contain a complete list. Size of the array is equal to the number of vertices and every index i in the array will store the list of vertices connected to the vertex numbered i. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation of the above example undirected graph.
Below is the implementation of the adjacency list representation of Graphs:
Note: In below implementation, we use dynamic arrays (vector in C++/ArrayList in Java) to represent adjacency lists instead of a linked list. The vector implementation has advantages of cache friendliness.
c++:
// A simple representation of graph using c++ STL #include<bits/stdc++.h> using namespace std; // A utility function to add an edge in an // undirected graph. void addEdge(vector<int> adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // A utility function to print the adjacency list // representation of graph void printGraph(vector<int> adj[], int V) { for (int v = 0; v < V; ++v) { cout << "\n Adjacency list of vertex " << v << "\n head "; for (auto x : adj[v]) cout << "-> " << x; printf("\n"); } } // Driver code int main() { int V = 5; vector<int> adj[V]; addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj, V); return 0; }
java:
// Java code to demonstrate Graph representation
// using ArrayList in Java
import java.util.*;
class Graph {
// A utility function to add an edge in an
// undirected graph
static void addEdge(ArrayList<ArrayList<Integer> > adj,
int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// A utility function to print the adjacency list
// representation of graph
static void printGraph(ArrayList<ArrayList<Integer> > adj)
{
for (int i = 0; i < adj.size(); i++) {
System.out.println("\nAdjacency list of vertex" + i);
for (int j = 0; j < adj.get(i).size(); j++) {
System.out.print(" -> "+adj.get(i).get(j));
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
// Creating a graph with 5 vertices
int V = 5;
ArrayList<ArrayList<Integer> > adj
= new ArrayList<ArrayList<Integer> >(V);
for (int i = 0; i < V; i++)
adj.add(new ArrayList<Integer>());
// Adding edges one by one
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj);
}
}
Output:
Adjacency list of vertex 0 head -> 1-> 4 Adjacency list of vertex 1 head -> 0-> 2-> 3-> 4 Adjacency list of vertex 2 head -> 1-> 3 Adjacency list of vertex 3 head -> 1-> 2-> 4 Adjacency list of vertex 4 head -> 0-> 1-> 3
Pros: Saves space O(|V|+|E|). In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.
Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).
Graphs real-life applications:
- Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. For example Google GPS
- linkedIn, Facebook and other social networks use graphs For example,On facebook, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link .anything that has data is a node.Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page, etc., a new edge is created for that relationship.All of facebook is then a collection of these nodes and edges. This is because facebook uses a graph data structure to store its data.
