Before we begin, lets briefly discuss what are graphs?

A graph is an abstract notation used to represent the connection between pairs of objects. It can be used to represent networks: systems of roads, airline flights from city to city, how the Internet is connected, or social connectivity on facebook, twitter etc. We use some standard graph algorithms to solve these otherwise difficult problems.

Representing Graphs

Graphs represent pairwise relationships between objects. Graphs are mathematical structures and therefore can be visualized by using two basic components, nodes and edges

A node, also known as a vertex, is a fundamental part of a graph. It is the entity that has a name, known as the key, and other information related to that entity. A relationship between nodes is expressed using edges. An edge between two nodes expresses a one-way or two-way relationship between the nodes.

Graphs can be represented as Adjacency Matrix and Adjacency List.

For the remainder of this course, we will be using Adjacency Lists because Algorithms can be performed more efficiently using this form of representation.

For example, the adjacency list representation allows you to easily iterate through the neighbors of a node. In the adjacency matrix representation, you will need to iterate through all the nodes to identify a node’s neighbors.

A path in a graph $G$ $=$ $(V, E)$ is a sequence of vertices $v1, v2, …, vk$ , with the property that there are edges between $vi$ and $vi+1$ . We say that the path goes from $v1$ to $vk$ . The sequence $6, 4, 5, 1, 2$ is a path from node $6$ to node $2$ in the graph above. A path is simple if its vertices are all different.

A cycle is a path $v1, v2, …, vk$ for which

$k > 2$ ,
the first $k - 1$ vertices are all different, and,
$v1 = vk$ .

The sequence $4, 5, 2, 3, 4$ is a cycle in the graph above.

A graph is connected if for every pair of vertices $u$ and $v$ , there is a path from $u$ to $v$ .

The Graph Class

Graph class consists of two data members:

The total number of vertices in the graph
A list of linked lists to store adjacent vertices

So let’s get down to the implementation!

C++

#include<iostream> 
#include <list> 
#include <vector>
using namespace std; 
class Graph { 
	int vertices;
	list<int> *adjacencyList; 
  public:
    Graph(int V);
    ~Graph();
    void addEdge(int v, int w);
}; 
Graph::Graph(int V=0) 
{ 
	this->vertices = V; 
	adjacencyList = new list<int>[V]; 
} 
void Graph::addEdge(int v, int w) 
{ 
  if (v < vertices && w < vertices) {
    adjacencyList[v].push_back(w);
    //adjacencyList[w].push_back(v); only for undirected graph
    //where reverse also allowed
  }
} 
Graph::~Graph() { //destructor
  delete[] adjacencyList;
}
/* Driver Program */
int main() {
    Graph myGraph(5);
    return 0;
}

1.Introduction

2.Algorithmic Paradigms

3.Introduction to Complexity Measures

4.Sorting & Searching

5.Graph Algorithms

6.Greedy Algorithms

7.Dynamic Programming

8.Divide and Conquer

9.Appendix: Auxiliary Source Code

10.Conclusion

Introduction to Graph Algorithms and Implementation

Representing Graphs

Mathematical Notation

The Graph Class