A graph is a data structure that consists of the following two components:
1. A finite set of vertices also called as nodes.
2: A finite set of order pair from (u,v) called as edge.
The following two are the most commonly used representations of a graph.
1. Adjacency Matrix
( N *N matrix where N is number of vertices)
class Graph
{
static void addEdge(LinkedList<int>[] adj,
int u, int v)
{
adj[u].AddLast(v);
adj[v].AddLast(u);
}
}
2. Adjacency List
(N List of Array of Link-lists, where N is number of vertices and each element will consist list of vertices connected to)
Adjacency Matrix:
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.
An undirected graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are bidirectional. An undirected graph is sometimes called an undirected network.
Adjacency List:
An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an 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 graph.
Detect Cycle In Graph:
The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle.
Both approaches above actually mean the same. However, this method can be applied only to undirected graphs.
The reason why this algorithm doesn’t work for directed graphs is that in a directed graph 2 different paths to the same vertex don’t make a cycle. For example: A–>B, B–>C, A–>C – don’t make a cycle whereas in undirected ones: A–B, B–C, C–A does.
Find a cycle in undirected graphs
An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge).
Find a cycle in directed graphs
In addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.
Site Title 