O que é um grafo orientado e quais são as suas características?

Um grafo dirigido é um grafo que possui um conjunto de vértices (nós) e um conjunto de arestas (arcos), onde cada arco tem uma direção.

Características:

• Arestas dirigidas: O movimento ao longo do arco é possível apenas em uma direção, indicada por uma seta.
• Grau do vértice: Para um grafo dirigido, define-se o grau de entrada (número de arestas que terminam no vértice) e o grau de saída (número de arestas que começam no vértice).
• Caminhos e ciclos: Um caminho é uma sequência de vértices conectados por arestas na direção correta. Um ciclo é um caminho que começa e termina no mesmo vértice. Grafos dirigidos podem conter ciclos dirigidos.
• Conectividade: Distingue-se entre conectividade fraca (ignorando as direções das arestas, o grafo é conexo como não dirigido) e conectividade forte (para quaisquer dois vértices A e B, existe um caminho dirigido de A para B e de B para A).
• Representação: Podem ser representados por listas de adjacência ou matrizes de adjacência, onde para um grafo dirigido, a matriz geralmente não é simétrica.

Exemplo de representação por lista de adjacência:

# Grafo G = (V, E), onde V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

grafo = {
    0: [1],
    1: [2],
    2: [0]
}

Exemplo de representação por matriz de adjacência:

# Grafo G = (V, E), onde V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matriz = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # sem arestas saindo de 2
]