An Interest In:
Web News this Week
- April 15, 2024
- April 14, 2024
- April 13, 2024
- April 12, 2024
- April 11, 2024
- April 10, 2024
- April 9, 2024
Some of Our Sources
- BoingBoing
- Technology Review
- Smashing Apps
- Vandelay Design
- Creative Curio
- Noupe
- Wal You
- Willems Lab
- Dev To
- The Verge
Help Webnuz
Referal links:
Criando um algoritmo de pesquisa em largura em grafos
Grafos so estruturas de dados que consistem em vrtices (ou ns) conectados por arestas (ou arcos). Eles so amplamente utilizados em vrias reas, como cincia da computao, matemtica, fsica, biologia, entre outras.
Na cincia da computao, por exemplo, os grafos so usados para representar relaes entre objetos, como usurios em uma rede social, ou para modelar rotas e caminhos em mapas, como as ruas no Google Maps. Eles permitem a anlise de dados complexos, possibilitando a descoberta de padres e informaes teis. Vejamos o seguinte grafo:
Para responder perguntas como "existe um caminho do vrtice A ao vrtice B?" ou "qual o caminho mnimo do vrtice A ao vrtice B?", uma das solues utilizar o algoritmo de pesquisa em largura (BFS - breadth-first search). Ele comea no vrtice A e expande sua pesquisa para os vrtices conectados a ele, que so B e C. Em seguida, avana para os vrtices conectados a B e C, e assim por diante, buscando em largura.
Vamos criar um exemplo de algoritmo de pesquisa em largura usando JavaScript, para responder a seguinte questo: Qual o caminho mais curto do vrtice A ao vrtice F?
Primeiro vamos definir as vrtices e suas conexes como um objeto:
const connections = { A: [ 'B', 'C' ], B: [ 'A', 'D', 'F' ], C: [ 'A', 'D', 'E' ], D: [ 'B', 'C' ], F: [ 'B', 'E' ], E: [ 'C', 'F' ]}Estamos dizendo que A se conecta com B e C, que B se conecta com A, D e F e assim sucessivamente.
Agora vamos comear a criar nosso algoritmo. Primeiro precisamos que ele faa um loop por todos os vrtices do grafo e identifique quais j foram visitados.
function findShortestPath(graph, startNode, endNode) { // fila dos vertices que sero visitados const queue = [startNode]; // objeto contendo os vrtices que j foram visitados const visited = { [startNode]: true }; // objeto que vai identificar quais os vrtices anteriores a um determinado vrtice pra montarmos o caminho const predecessor = {}; // Loop enquanto houverem vrtices para ser visitados while (queue.length) { // Obtm e remove o primeiro vrtice da lista const currNode = queue.shift(); // RESTO DO NOSSO ALGORITMO } return null;}Agora precisamos fazer com que, a cada novo vrtice buscado, a funo obtenha o vrtice anterior que se ligue a ele e adicione o caminho no nosso objeto predecessor.
function findShortestPath(graph, startNode, endNode) { const queue = [startNode]; const visited = { [startNode]: true }; const predecessor = {}; while (queue.length) { const currNode = queue.shift(); // Obtm os vrtices que esto conectados ao vrtice atual // aqui so chamados de vizinhos const neighbors = graph[currNode]; // Itera sobre cada vrtice vizinho for (const neighbor of neighbors) { // Apenas continua a busca se ele ainda no tiver sido visitado if (!visited[neighbor]) { visited[neighbor] = true; // Adiciona no objeto predecessor o vrtice que est ligado a ele predecessor[neighbor] = currNode; // Adiciona ele mesmo na fila de vrtices para serem pesquisados queue.push(neighbor); // RESTO DO NOSSO ALGORITMO } } }Agora que o algoritmo j busca todos os vrtices do nosso grafo, precisamos fazer com que ele obtenha o vrtice de destino e, a partir do objeto predecessor, construa o caminho de volta ao ponto inicial.
function findShortestPath(graph, startNode, endNode) { const queue = [startNode]; const visited = { [startNode]: true }; const predecessor = {}; while (queue.length) { const currNode = queue.shift(); const neighbors = graph[currNode]; for (const neighbor of neighbors) { if (!visited[neighbor]) { visited[neighbor] = true; predecessor[neighbor] = currNode; queue.push(neighbor); // Observa se o vizinho que est sendo checado atualmente... // o nosso destino if (neighbor === endNode) { // Comea a reconstruir o caminho mais curto a partir do vrtice... // de chegada const shortestPath = [endNode]; // Obtm o vrtice atual de onde os vizinhos foram obtidos let prevNode = currNode; // Loop enquanto o caminho ainda no tiver sido reconstrudo... // at o ponto de partida while (prevNode !== startNode) { // Adiciona no comeo da array `shortestPath` o vrtice `prevNode` shortestPath.unshift(prevNode); // Obtm o predecessor do `prevNode` e faz dele o `prevNode` atual prevNode = predecessor[prevNode]; } shortestPath.unshift(startNode); return shortestPath; } } } } return null;}Ao executar o nosso cdigo vemos o resultado da busca:
const connections = { A: [ 'B', 'C' ], B: [ 'A', 'D', 'F' ], C: [ 'A', 'D', 'E' ], D: [ 'B', 'C' ], F: [ 'B', 'E' ], E: [ 'C', 'F' ]}const shortestPath = findShortestPath(connections, 'A', 'F');console.log(shortestPath); // ['A', 'B', 'F']Podemos ver que o caminho mais curto do vrtice ao vrtice F de fato A -> B -> F:
O algoritmo de busca em largura uma ferramenta essencial na resoluo de problemas que envolvem a descoberta do menor caminho entre dois pontos em um grafo. Mas importante lembrar que cada aplicao pode ter suas particularidades e o algoritmo de pesquisa em largura no o nico e pode no ser o melhor algoritmo de busca pelo menor caminho em muitos casos.
Saber implementar um algoritmo de pesquisa em largura pode ajudar a solucionar problemas complexos em diversas reas, como redes de transporte, otimizao de rotas e at mesmo jogos.
Original Link: https://dev.to/antiduhring/criando-um-algoritmo-de-pesquisa-em-largura-em-grafos-3af3
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To