🧭 Cómo se recorre un grafo

Recorrer (o «hacer el recorrido») y visitar los nodos de un grafo siguiendo las aristas. Hay dos maneras básicas, y la elección entre ellas no es un detalle técnico: es una decisión estratégica que vas a repetir con agentes.

Qué observar: e o mismo grafo de ambos lados — solo cambia el orden de los números. En anchura, el 4 y el 5 solo aparecen después de todo el segundo nivel. En profundidad, el 3 y el 4 aparecen antes de que siquiera se toque la rama de la derecha. Ninguno de los dos es “mejor”: la anchura encuentra primero lo más cercano, la profundidad encuentra una responde rápido.

«Camino mínimo» casi siempre significa menor suma de pesos, no menos saltos. Son cosas diferentes y confundirlas cuesta dinero. Un camino de 2 aristas caras puede ser peor que uno de 5 aristas baratas.

En la rutina matutina del módulo anterior quedó claro: el atajo tenía menos nodos y también costaba menos. Pero cambia el peso por «riesgo» y el diseño se invierte: el atajo puede ser el camino más corto y el más peligroso al mismo tiempo. El peso que eliges define qué es “mejor”.

Orden topológico y es una fila de ejecución válida en un DAG: nadie aparece antes que alguien de quien depende. Es lo que el make calcula, es lo que calcula tu CI — y es lo que calculará el orquestador de tu grafo de agentes.

// grafo: no -> lista de quem DEPENDE dele (roda depois)
const dep = {
  "pesquisar": ["escrever"],
  "escrever":  ["revisar"],
  "coletar_dados": ["escrever"],
  "revisar":   []
};

function ordenar(g) {
  const grau = {}, saida = [];
  Object.keys(g).forEach(n => grau[n] = 0);
  Object.values(g).flat().forEach(n => grau[n] = (grau[n] || 0) + 1);
  let prontos = Object.keys(grau).filter(n => grau[n] === 0);

  while (prontos.length) {
    console.log("rodam em PARALELO agora:", prontos.join(", "));
    const proximos = [];
    for (const n of prontos) {
      saida.push(n);
      for (const viz of (g[n] || [])) if (--grau[viz] === 0) proximos.push(viz);
    }
    prontos = proximos;
  }
  if (saida.length !== Object.keys(grau).length)
    throw new Error("CICLO detectado — nao existe ordem valida");
  return saida;
}

console.log("ordem final:", ordenar(dep).join(" → "));

El script anterior ya imprimió la respuesta: cada línea “se ejecuta EN PARALELO ahora” es un nivel del grafo, y el tamaño de esa línea es cuántos trabajadores caben en ese momento. Esto vale igual para personas y agentes. Lanzar 20 agentes en un grafo que solo libera 3 nodos a la vez no acelera nada: solo gasta.

Qué observar: las tres franjas tienen anchos diferentes — 2, 3 y 1. El último nivel (“unir”) es un cuello de botella: por muchos agentes que tengas, por ahí pasa uno a la vez. Este patrón — abrir en varios y luego converger en uno solo — es el fan-out / fan-in que la Trilha 4 nombrará.

El ciclo no es un defecto: es lo que permite repetir el trabajo hasta que quede bien. El defecto es un ciclo sin salida. Hay exactamente tres tipos de salida, y todo ciclo que dibujes necesita tener al lado escrito al menos uno de ellos.

En la práctica, un grafo es un diccionario: para cada nodo, la lista de vecinos. Eso se llama lista de adyacencia y resuelve el 95% de los casos. El truco para los agentes es sencillo: además de los vecinos, guarda los datos del nodo — modelo, herramientas, prompt, límite de costo. Eso es lo que transforma un grafo común en un grafo agéntico.

{
  "nos": {
    "pesquisar": {
      "papel": "Levanta fontes sobre <o tema> e resume em notas curtas",
      "modelo": "<modelo rapido e barato>",
      "ferramentas": ["busca_web", "ler_url"],
      "teto_custo_usd": 0.50
    },
    "escrever": {
      "papel": "Escreve o texto usando SO as notas recebidas",
      "modelo": "<modelo bom de escrita>",
      "ferramentas": [],
      "teto_custo_usd": 1.00
    },
    "revisar": {
      "papel": "Confere fatos e clareza. Responde aprovado: true|false",
      "modelo": "<modelo forte de raciocinio>",
      "ferramentas": ["busca_web"],
      "contexto_limpo": true,
      "teto_custo_usd": 1.00
    }
  },
  "arestas": [
    { "de": "pesquisar", "para": "escrever", "quando": "sempre",  "passa": "notas" },
    { "de": "escrever",  "para": "revisar",  "quando": "sempre",  "passa": "rascunho" },
    { "de": "revisar",   "para": "escrever", "quando": "aprovado == false", "passa": "criticas",
      "max_voltas": 2 },
    { "de": "revisar",   "para": "FIM",      "quando": "aprovado == true" }
  ]
}