Estructura de teoría de grafos

En ciencias de la computación, los grafos se utilizan ampliamente para modelar redes sociales (los usuarios son puntos, las relaciones de amistad son líneas), enlaces web (las páginas web son puntos, los hipervínculos son líneas), redes de comunicación e incluso problemas de planificación de rutas.

grafoEs como un diagrama de relaciones de redes sociales:

  • Nodo (vértice): cada persona en la red social
  • arista: las relaciones entre personas (amistad, seguimiento, etc.)
  • Peso: la intensidad de la relación (cercanía, frecuencia de interacción, etc.)

Imagina la red de transporte de tu ciudad: cada lugar (como casa, escuela, centro comercial) esnodo, las carreteras que conectan estos lugares sonlínea. El grafo (Graph) es la abstracción matemática de esta relación de puntos y líneas, y se utiliza para representarrelaciones complejas entre entidadesuna estructura de datos.

Casos de la vida real:

  • Mapa: las ciudades son nodos, las carreteras son aristas, la distancia es el peso
  • Circuito eléctrico: los componentes son nodos, los cables son aristas, la resistencia es el peso
  • Internet: los sitios web son nodos, los enlaces son aristas, el tráfico es el peso
  • Red de transporte: las estaciones son nodos, las líneas son aristas, la tarifa es el peso
Escenario Otras estructuras Estructura de grafo
Relaciones sociales Difícil de expresar relaciones complejas Expresa naturalmente relaciones de muchos a muchos
Planificación de rutas Requiere estructuras de datos complejas Representa intuitivamente redes y rutas
Relaciones de dependencia Difícil de representar dependencias cíclicas Maneja fácilmente dependencias complejas
Análisis de redes No puede expresar la topología de red Describe perfectamente la estructura de la red

Términos básicos de grafos

Término Definición Analogía cotidiana Notación simbólica
Vértice (Vertex) Unidad básica en un grafo Personas en una red social V, u, v
Arista (Edge) Línea que conecta dos vértices Relación entre dos personas E, (u,v)
Grado (Degree) Número de aristas conectadas a un vértice Número de amigos de una persona deg(v)
Camino (Path) Secuencia de vértices Ruta de A a B v₁→v₂→…→vₙ
Ciclo (Cycle) Camino cuyo inicio y fin son el mismo Salir de casa y finalmente volver a casa v₁→v₂→…→v₁
Grafo conexo Hay un camino entre cualquier par de vértices Todos pueden contactarse entre sí
Peso (Weight) Atributo numérico de una arista Distancia entre dos ciudades w(u,v)

Clasificación de grafos

Criterio de clasificación Tipo Características Escenarios de aplicación
Direccionalidad Grafo no dirigido Las aristas no tienen dirección Relaciones de amistad, redes de carreteras
Grafo dirigido Las aristas tienen dirección Relaciones de seguimiento, flujos de trabajo
Peso Grafo no ponderado Todas las aristas tienen el mismo peso Relaciones en redes sociales
Grafo ponderado Las aristas tienen diferentes pesos Distancias en mapas, tráfico de red
Conectividad Grafo conexo Cualquier par de vértices es alcanzable Red de transporte
Grafo no conexo Existen vértices aislados Grupos sociales
ciclo Grafo acíclico No tiene ciclos Dependencias de tareas, árbol genealógico
Grafo cíclico Contiene ciclos Red de carreteras

Métodos de representación de grafos

Matriz de adyacencia

Propiedad Descripción Complejidad temporal Complejidad espacial
Método de almacenamiento Matriz bidimensional
Verificar si existe una arista matrix[i][j] != 0 O(1)
Agregar una arista matrix[i][j] = weight O(1)
Eliminar una arista matrix[i][j] = 0 O(1)
Recorrer los vértices adyacentes Escanear una fila/columna O(V)
Ocupación de espacio Matriz V×V O(V²)

Lista de adyacencia

Propiedad Descripción Complejidad temporal Complejidad espacial
Método de almacenamiento Arreglo + lista enlazada
Verificar si existe una arista Buscar en la lista enlazada O(deg(v))
Agregar una arista Agregar en la lista enlazada O(1)
Eliminar una arista Eliminar en la lista enlazada O(deg(v))
Recorrer los vértices adyacentes Recorrer la lista enlazada O(deg(v))
Ocupación de espacio Arreglo de vértices + lista enlazada de aristas O(V+E)

Conceptos básicos de grafos

Un grafoGse compone de dos conjuntos:

  • Conjunto de vértices V (Vertex Set): el conjunto de todos los puntos en el grafo.
  • Conjunto de aristas E (Edge Set): el conjunto de líneas que conectan estos puntos. Una arista se representa por los dos vértices(u, v)que conecta.

Ejemplo

# Un ejemplo simple de grafo: representar relaciones de amistad en una red social con un diccionario
# Vértices: Alice, Bob, Charlie, Diana
# Aristas: representan las relaciones de amistad entre ellos

social_graph = {
    'Alice': ['Bob', 'Charlie'],   # Alice es amiga de Bob y Charlie
    'Bob': ['Alice', 'Charlie', 'Diana'],
    'Charlie': ['Alice', 'Bob'],
    'Diana': ['Bob']
}

print(fVértices (usuarios): {list(social_graph.keys())})
print(fAmigos de Alice (aristas): {social_graph['Alice']})

Salida:

顶点(用户): ['Alice', 'Bob', 'Charlie', 'Diana']
Alice 的好友(边): ['Bob', 'Charlie']

Clasificación de grafos y conceptos importantes

Los grafos se pueden clasificar en varios tipos según las características de sus aristas; comprender esto es la base para dominar la teoría de grafos.

Grafo no dirigido vs grafo dirigido

Tipo Características de la arista (Edge) Analogía cotidiana Ejemplo
Grafo no dirigido Las aristas no tienen dirección,(A, B)lo que significa que A y B están conectados mutuamente. Amistad bidireccional: si Alice es amiga de Bob, entonces Bob también es amigo de Alice. Relaciones de amistad en redes sociales, conexiones en circuitos.
Grafo dirigido Las aristas tienen dirección,A -> Blo que indica una conexión unidireccional de A a B. Seguimiento en Weibo: puedes seguir a alguien, pero esa persona no necesariamente te sigue a ti. Hipervínculos web, dependencias de tareas, calles de sentido único.

Grafo ponderado

En un grafo ponderado, cada arista recibe un valor numérico (peso) que puede representar distancia, costo, tiempo o intensidad de la relación.

Ejemplo

# Un grafo ponderado que representa distancias entre ciudades (en forma de lista de adyacencia)
weighted_graph = {
    'Pekín': {('Shanghái', 1200), ('Tianjin', 100)},  # Distancia de Pekín a Shanghái 1200, a Tianjin 100
    'Shanghái': {('Pekín', 1200), ('Hangzhou', 200)},
    'Tianjin': {('Pekín', 100)},
    'Hangzhou': {('Shanghái', 200)}
}

Términos clave

  • Grado (Degree): el número de aristas conectadas a un vértice. En un grafo dirigido, se divide engrado de entrada(número de aristas que apuntan al vértice) ygrado de salida(número de aristas que salen del vértice).
  • Camino (Path): Secuencia de aristas que se recorre de un vértice a otro. Por ejemplo,A -> B -> C。
  • Ciclo (Cycle): Camino cuyo punto de inicio y punto final son el mismo vértice.
  • Grafo conexo (Connected Graph): En un grafo no dirigido, existe un camino entre cualquier par de vértices.
  • Grafo fuertemente conexo (Strongly Connected Graph): En un grafo dirigido, entre cualquier par de vértices existeen ambos sentidosun camino.

Métodos de almacenamiento de grafos

¿Cómo representar un grafo en una computadora? Hay dos métodos principales.

Matriz de adyacencia

Usar un arreglo bidimensional (matriz)matrixpara representar el grafo.matrix[i][j]El valor de ... representa el vérticeial vérticejel estado de la arista.

  • Para un grafo no dirigido, la matriz es simétrica.
  • Para un grafo ponderado, el valor de la matriz almacena el peso (usando un valor especial como0o∞para representar la ausencia de arista).
  • Ventajas: verificar si existe una arista entre dos vértices cualesquiera es muy rápido (O(1))。
  • Desventajas: ocupa mucho espacio (O(V^2)), y desperdicia espacio en los "grafos dispersos" con pocas aristas.

Ejemplo

# Representar un grafo no dirigido usando una matriz de adyacencia
# Vértices: 0-A, 1-B, 2-C
# Aristas: A-B, A-C

V = 3  # Número de vértices
adj_matrix = [[0] * V for _ in range(V)]

# Añadir arista A-B (0-1)
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1  # En un grafo no dirigido, hay que establecer la posición simétrica
# Añadir arista A-C (0-2)
adj_matrix[0][2] = 1
adj_matrix[2][0] = 1

print("Matriz de adyacencia:")
for row in adj_matrix:
    print(row)
# Salida:
# [0, 1, 1]
# [1, 0, 0]
# [1, 0, 0]

Lista de adyacencia

Mantener una lista (lista enlazada, arreglo, etc.) para cada vértice, registrando todos los vértices (y pesos) conectados directamente a él.

  • Ventajas: alta eficiencia de espacio (O(V + E)), especialmente adecuada para grafos dispersos. Permite encontrar rápidamente todos los vecinos de un vértice.
  • Desventajas: comprobar si existe una arista entre dos vértices cualesquiera es más lento (O(degree(V)))。

Ejemplo

# Representar el mismo grafo no dirigido usando una lista de adyacencia (diccionario + lista)
adj_list = {
    'A': ['B', 'C'],  # A está conectado a B y C
    'B': ['A'],       # B está conectado a A
    'C': ['A']        # C está conectado a A
}

print("Lista de adyacencia:")
for vertex, neighbors in adj_list.items():
    print(f"{vertex}: {neighbors}")

Algoritmos de recorrido de grafos

El recorrido es la base de los algoritmos de grafos; significa visitar sistemáticamente cada vértice del grafo.

Principalmente hay dos estrategias:

Búsqueda en anchura

La búsqueda en anchura (BFS) es como la "propagación de ondas en el agua": desde el punto de partida, primero visita todos los vecinos directos, luego los vecinos de los vecinos, y así sucesivamente. Usauna colapara implementarlo.

Pasos del algoritmo:

  1. Colocar el punto de partida en la cola y marcarlo como visitado.
  2. Cuando la cola no esté vacía:va. Extraer el vértice del frente de la cola.vb. Visitar
  3. todos los vecinos no visitados de este vértice, ponerlos en la cola y marcarlos como visitados.

Ejemplo

from collections import deque

def bfs(graph, start):
    """Recorrer el grafo usando BFS y devolver el orden de visita"""
    visited = set([start])  # Registrar los vértices visitados
    queue = deque([start])  # Inicializar la cola
    result = []             # Almacenar el orden de visita

    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        # Recorrer los vecinos del vértice actual
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

# Datos de prueba
test_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("Orden de recorrido BFS (comenzando desde A):", bfs(test_graph, 'A'))
# La salida podría ser: ['A', 'B', 'C', 'D', 'E', 'F']

Búsqueda en profundidad

La búsqueda en profundidad (DFS) es como "recorrer un laberinto": se elige un camino hasta el final, luego se retrocede y se toma otro camino. Usapila(o recursión) para implementarlo.

Pasos del algoritmo recursivo:

  1. Desde el vérticevinicial, marcarlo como visitado.
  2. Paravcada vecino no visitado de vu:DFS(u)。

Ejemplo

def dfs_recursive(graph, vertex, visited=None, result=None):
    """Implementar DFS usando recursión"""
    if visited is None:
        visited = set()
    if result is None:
        result = []

    visited.add(vertex)
    result.append(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)
    return result

print("Orden de recorrido DFS (comenzando desde A):", dfs_recursive(test_graph, 'A'))
# La salida podría ser: ['A', 'B', 'D', 'E', 'F', 'C']

Comparación de algoritmos de recorrido de grafos:


Escenarios de aplicación clásicos e introducción a los algoritmos

Una vez que domines la representación y el recorrido de grafos, podrás explorar muchos problemas clásicos:

  1. Problema del camino más corto: en la navegación por mapas, encontrar la distancia de viaje más corta entre dos puntos.

    • Algoritmo de Dijkstra: adecuado parapesos no negativosen grafos.
    • Algoritmo de Floyd: calcula el camino más corto entre todos los pares de vértices.
  2. Árbol de recubrimiento mínimo: eligiendo el conjunto de aristas con el peso total mínimo, garantizando que todos los vértices estén conectados (por ejemplo, tender una red de fibra óptica de costo mínimo para varios pueblos).

    • Algoritmo de Prim
    • Algoritmo de Kruskal
  3. Ordenamiento topológico: ordenar linealmente los vértices de un grafo acíclico dirigido (DAG), de modo que para cualquier arista dirigidau->v,uen la ordenación, se coloquevantes

(por ejemplo, organizar el orden de estudio de los cursos).