The indegree of a vertex in a directed graph refers to the number of incoming edges to that vertex. In simpler terms, it counts how many edges point towards a particular vertex.
If you’re working with a directed graph where each edge has a direction (e.g., from vertex AA to vertex BB), the indegree of vertex BB would be the number of edges that point towards BB.
Example:
Consider the following directed graph:
A → B → C
↑ ↓
D ← E
- Indegree of vertex A: 0 (no edges point to A)
- Indegree of vertex B: 2 (edges from A and E point to B)
- Indegree of vertex C: 1 (edge from B points to C)
- Indegree of vertex D: 1 (edge from A points to D)
- Indegree of vertex E: 1 (edge from D points to E)
Key points:
- Indegree measures how many edges point towards a vertex.
- It is an important concept in algorithms like topological sorting, where nodes with an indegree of 0 are typically processed first.
Would you like to dive into a specific example or concept related to indegree?