An undirected graph is a graph in which edges have no orientation. The edge (u,v) is identical to the edge (u,v).
An directed graph is a graph in which edges have orientation. The edge (u,v) is the edge from node u to node v.
Many graphs can have edges that can contain a certain weight to represent an arbitrary value such as cost, distance, quantity, e.t.c..
It can be Directed or Undirected Graph
A tree is an undirected graph with no cycles. equivalently, it is a connected graph with N nodes and N-1 edges.
A rooted tree is a tree with a designated root node where every edge either points away from or towards the root node.
Out Tree - When edges point away from the root. In Tree - When edges point towards the root.
DAGs are directed graph with no cycles. These graph plays an important role in representing structures with dependencies. Several efficient algorithms exist to operate on DAGs.
Note: All out-trees are DAGs but not all DAGs are out-trees.
A bipartite graph is one whose vertices can be split into two independent groups U, V such that every edge connects between U and V. OR All vertices of group U can only connect to vertices of V and can not connect within U.
A complete graph is one where there is a unique edge between every pair of nodes.
A complete graph with n vertices is denoted as the graph kn.
A edge list is a way to represent a graph simply as an unordered list of edges. Assume the notation for any triplet (u,v,w) means:
the cost from node u to node v is w
[[0,1,0],[0, 4, 0],[1,0,0],[1, 4, 0],[1,3,0],[1,2,0],[2,1,0],[2,3,0],[3,1,0],[3, 2,0],[3,4,0],[4,0,0],[4,1,0],[4,3,0]]
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city ?
A bridge / cut edge is any edge in a graph whose removal increases the number of connected components.
An articulation point / cut vertex is any node in a graph whose removal increases the number of connected components.
Minimum spanning tree is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together, without any cycles and with the minimum possible total edge wait.
The Depth first search is the most fundamental search algorithm used to explore nodes and edges of a graph. It runs with a time complexity of O(V+E) and is often used as a building block in other algorithms.
import java.util.Iterator;
import java.util.LinkedList;
// This class represents a directed graph using adjacency list
// representation
class Graph {
private int V; // No. of vertices
// Array of lists for Adjacency List Representation private LinkedList<Integer> adj[];
// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Following is Depth First Traversal " +
"(starting from vertex 2)");
g.DFS(2);
}
//Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w); // Add w to v's list.
}
// A function used by DFS
void DFSUtil(int v, boolean visited[]) {
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v + " ");
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}
// The function to do DFS traversal. It uses recursive DFSUtil()
void DFS(int v) {
// Mark all the vertices as not visited(set as
// false by default in java) boolean visited[] = new boolean[V];
// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);
}
}The Breadth first search is another fundamental search algorithm used to explore nodes and edges of a graph. It runs with a time complexity of O(V+E) and is often used as a building block in other algorithms.