What is a directed graph and what are its main characteristics?

A directed graph (or digraph) is a data structure consisting of a set of vertices (nodes) and a set of directed edges (arcs) connecting these vertices. Each edge has a direction indicating which vertex is the start and which is the end.

Main characteristics:

• Vertices (Nodes / Vertices): Elements of the graph represented by points. They can denote objects, states, or stages.
• Edges (Edges / Arcs): Connections between vertices. In a directed graph, an edge has a direction indicating a transition from one vertex to another. They are denoted by an ordered pair (u, v), where u is the starting vertex and v is the ending vertex.
• Directionality: A key feature that distinguishes a directed graph from an undirected one. Movement is only possible along the direction of the edge. An edge from A to B does not imply the possibility of moving from B to A unless there is a separate edge from B to A.
• Loops: Edges that connect a vertex to itself (v, v).
• Multiple Edges: Several edges connecting the same pair of vertices in the same direction. Multiple edges are not allowed in simple directed graphs.
• Isolated vertices: Vertices without incoming or outgoing edges.
• Vertex degree:
  • In-degree: The number of edges entering a vertex.
  • Out-degree: The number of edges leaving a vertex.

Applications in QA:

• State graphs for testing finite automata.
• Control flow graphs for code analysis and test case generation.
• Modeling dependencies in systems (e.g., dependencies between services or modules).
• Testing usage scenarios with strict action sequences.