34. Graph Theory

Introduction

Vertices/Nodes - Circles
Edges/Links - Arrows

1. Directed Edge - One-way edge
2. Undirected Edge - Two-way edge.

Representation

1. Adjacency Matrix - 2D Array, A[i][j] = 1, if there is an edge from vertex i to vertex j
2. Adjacency List - Each A[i] is list of nodes Xi reachable from i.

DFS

1. Go deep enough.
2. Traversals - Pre, Post, In - Order
3. Implemented using stack

BFS

1. Go Layer by layer.

Terminologies

1. Directed Graph - Arrows are uni or bi-directional.
2. Undirected Graph - Arrows are bi-directional only.
3. Adjacent Vertices - Two vertices connected directly by an edge.
4. Degree - Number of edges of a vertex.
5. In-Degree - Number of incoming edges of a vertex.
6. Out-Degree - Number of outgoing edges of a vertex.
7. Path - Number of vertices come in the path of two given vertices.
8. Connected Graph - Every vertex has a path.
9. Disconnected Graph - There is one vertex that doesn't have a path.
10. Connected Components - Each connected graph is the disconnected graph.
11. Cycle - Path from a vertex to the same vertex.
12. Cyclic Graph - Graph that contains a cycle. it can be disconnected graph also
13. Acyclic Graph - Graph that doesn't contain a cycle.
14. Tree - The tree is a connected acyclic graph.
15. DAG(Directed Acyclic Graphs) - Directed + Acyclic
16. Complete Graph - Each vertex is connected to every other vertex directly by an edge. nC2 = n(n-1)/2 = Edges
17. Weighted Graph - Graph with weighted edges.