Graph - kumarpranav1987/DataStructureOnGitHub GitHub Wiki

Data Structures For Graphs

• Adjacency Matrix
• Adjacency List

Graph Traversal

• BFS

• DFS

Types

Undirected Graph

DFS Edge Types
1)Tree Edge
2)Back Edge
Read and Solve below Topics from Hackerearth
a) Articulation Point Or Cut Vertex
b) Biconnected Graph
c) BiConnected Components

1. Hacker Earth Tutorial

d) Bridge In Graph

Directed

DFS Edge Types
1)Tree Edge
2)Back Edge
3)Forward Edge
4)Cross Edge

int edge_classification(int x, int y){  
   if (parent[y] == x) return(TREE);  
   if (discovered[y] && !processed[y]) return(BACK);  
   if (processed[y] && (entry_time[y]>entry_time[x])) return(FORWARD);  
   if (processed[y] && (entry_time[y]<entry_time[x])) return(CROSS);  
}

Topological Sorting And All Possible Topological Sort of a given Graph

1. Look at Second Approach in HackerEarth
2. Other Way to Find Topological Sort
3. Kahn's Topological Sort Algorithm

Strongly Connected Components

1. HackerEarth Strongly Connected Components Tutorial
2. Geeks For Geeks Strongly Connected Components Tutorial