Graph¶
- Graph is a very generic/loose term. following other DS can be considered as graph too
- Trees / Tries
- Linked list
- Graph is defined as set of vertices and edges where vertices are entities and edges are relationship among those entities.
- Simple Graphs with maximum number of edges (no parallel edge) is called clique (K2 : clique of 2 nodes and NC2 edges)
Types of Graphs¶
- cyclic / acyclic
- if you start from a vertex of graph an by some path, you can reach back to that vertex again without re-using any edge, then graph is said to be cyclic. Be careful when dealing with directional graphs
- connected / disconnected
- connected means from any vertex, you can reach any other vertex. So, you have to be carefull when dealing with directed graphs.
- graph with only one connected component
- directional / undirectional
- weighted / unweighted
Graph Representation¶
- set of vertices, pair of vertices as an edge
O(e), where e is number of edges to check if there is an edge between two vertices.O(n + e)space complexity.- Adjacency list
O(n)to check if there is an edge between two vertices.O(n + e)space complexity.- preferred when few edges or sparse graph.
- Adjacency matrics
O(n)to check if there is an edge between two vertices.O(n2)space complexity.- preferred when e ~= max no of edges possible.
Trail: Going from Node a to node e like: a - e1 - b - e3 - c - e2 - d - e1 - e
Path: A trail from one node to another without re-using a vertex
Walk: A trail from one node to another without re-using an edge. every path is a walk.
a > b > a > c : this is a walk, but not a path
Graph Traversal¶
- BFS
- DFS