98 lines
3.0 KiB
Markdown
98 lines
3.0 KiB
Markdown
---
|
|
type: mixed
|
|
---
|
|
## Definition of a Graph
|
|
|
|
A data structure that consists of:
|
|
- A set of vertices (or nodes).
|
|
- A set of edges, which connect pairs of vertices.
|
|
|
|
### Types of Graphs
|
|
1. **Directed Graph**:
|
|
- Edges have a direction, going from one vertex to another.
|
|
- Example: Websites linked via hyperlinks.
|
|
|
|
2. **Undirected Graph**:
|
|
- Edges have no direction; they simply connect two vertices.
|
|
- Example: Social networks where a connection is mutual.
|
|
|
|
3. **Weighted Graph**:
|
|
- Each edge is assigned a weight or cost.
|
|
- Example: Road networks where edge weights represent distances.
|
|
|
|
## Binary Tree
|
|
|
|
A hierarchical data structure where each node has at most two children, referred to as the left and right child. This structure is foundational for tasks such as expression parsing and hierarchical data representation.
|
|
|
|
- Maximum of two children per node.
|
|
- Recursive structure: subtrees are binary trees themselves.
|
|
|
|
|
|
|
|
---
|
|
|
|
## Binary Search Tree (BST)
|
|
|
|
A Binary Search Tree is a binary tree that maintains sorted order:
|
|
- For any node:
|
|
- All values in the left subtree are smaller.
|
|
- All values in the right subtree are larger.
|
|
- Enables $O(\log n)$ search, insertion, and deletion.
|
|
|
|
|
|
|
|
---
|
|
|
|
## Balanced Tree (AVL Tree)
|
|
|
|
A self-balancing binary search tree where:
|
|
- The balance factor (difference in heights of left and right subtrees) of any node is at most one.
|
|
- Rotations are used to maintain balance during insertions and deletions.
|
|
- Guaranteed $O(\log n)$ operations.
|
|
- Ensures balanced growth for fast access.
|
|
|
|
|
|
|
|
---
|
|
|
|
## Grids as Graphs
|
|
|
|
Can be modeled as a graph:
|
|
- Vertices: Represent grid cells.
|
|
- Edges: Represent valid movements between cells (e.g., up, down, left, right).
|
|
|
|
---
|
|
|
|
## Famous Graph Problems
|
|
Solved using [Graph Algorithms](Graph%20Algorithms.md).
|
|
### Shortest Path Problems
|
|
- Find the minimum distance or cost to travel between two nodes.
|
|
- **We can use**:
|
|
- Dijkstra's Algorithm (if non-negative weights).
|
|
- Bellman-Ford Algorithm (handles negative weights).
|
|
- Floyd-Warshall Algorithm (if we want all-pairs shortest paths).
|
|
|
|
### Minimum Spanning Tree (MST)
|
|
- Find a subset of edges that connects all vertices with the minimum total weight.
|
|
- **We can use**:
|
|
- Kruskal's Algorithm.
|
|
- Prim's Algorithm.
|
|
|
|
### Topological Sorting
|
|
- Arrange the vertices of a DAG in linear order such that for every directed edge $(u, v)$, $u$ appears before $v$.
|
|
|
|
### Max Flow / Min Cut
|
|
- Find the maximum flow possible in a network from a source to a sink.
|
|
- Ford-Fulkerson Algorithm.
|
|
- Edmonds-Karp Algorithm.
|
|
|
|
### Traveling Salesman Problem (TSP)
|
|
- Find the shortest tour that visits each vertex exactly once and returns to the starting point.
|
|
|
|
### Pathfinding in Grids
|
|
- Find the shortest path in a grid-based graph.
|
|
- **We can use**:
|
|
- A* Algorithm (heuristic-based).
|
|
- Breadth-First Search (BFS) for unweighted grids.
|
|
|
|
--- |