Grafos

Breadth-first search - Busca em largura

Estrutura genérica:

1. Inicialização: enfileire o vértice de origem fornecido em uma fila e marque-o como visitado.
2. Exploração: Enquanto a fila não estiver vazia:
a. Retire um nó da fila e visite-o (por exemplo, imprima seu valor).
b. Para cada vizinho não visitado do nó retirado da fila:
i. Enfileirar o vizinho na fila
ii. Marque o vizinho como visitado
3. Término: Repita a etapa 2 até que a fila esteja vazia.

from collections import deque

def bfs(adj, s, visited):

# cria uma fila para BFS

q = deque()

# marca o nó de origem como visitado e coloca-o na fila

visited[s] = True

[Link](s)

# inteira a fila

while q:

# retira da fila um vértice da fila e imprime-o

curr = [Link]()

print(curr, end=" ")

# obtém todos os vértices adjacentes do vértice retirado da fila, se um adjacente não

foi visitado, marque-o como visitado e coloque-o na fila

for x in adj[curr]:

if not visited[x]:
 visited[x] = True

[Link](x)

# Function to add an edge to the graph

def add_edge(adj, u, v):

adj[u].append(v)

adj[v].append(u)

# Example usage

if __name__ == "__main__":

# Number of vertices in the graph

V=5

# Adjacency list representation of the graph

adj = [[] for _ in range(V)]

# Add edges to the graph

add_edge(adj, 0, 1)

add_edge(adj, 0, 2)

add_edge(adj, 1, 3)

add_edge(adj, 1, 4)

add_edge(adj, 2, 4)

# Mark all the vertices as not visited

visited = [False] * V

# Perform BFS traversal starting from vertex 0

print("BFS starting from 0: ")

 bfs(adj, 0, visited)

Depth First Search - Busca em Profundidade

def add_edge(adj, s, t):

# Adiciona uma aresta do vértice s para t

adj[s].append(t)

# Devido ao grafo não direcionado

adj[t].append(s)

def dfs_rec(adj, visited, s):

# Marca o vértice atual como visitado

visited[s] = True

# Imprime o vértice atual

print(s, end=" ")

# Visita recursivamente todos os vértices adjacentes

# que ainda não foram visitados

for i in adj[s]:

if not visited[i]:

dfs_rec(adj, visited, i)

def dfs(adj, s):

visited = [False] * len(adj)

# Chama a função recursiva DFS

dfs_rec(adj, visited, s)

if __name__ == "__main__":
 V=5

# Cria uma lista de adjacência para o grafo

adj = [[] for _ in range(V)]

# Define as arestas do grafo

edges = [[1, 2], [1, 0], [2, 0], [2, 3], [2, 4]]

# Popula a lista de adjacência com as arestas

for e in edges:

add_edge(adj, e[0], e[1])

source = 1

print("DFS a partir da fonte:", source)

dfs(adj, source)

Dijkstra’s Algorithm - Algoritmo de Dijkstra

Soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso
não negativo.
Estrutura genérica:

1. Marque o nó de origem com uma distância atual de 0 e o restante com infinito.

2. Defina o nó não visitado com a menor distância atual como o nó atual.
3. Para cada vizinho, N do nó atual adiciona a distância atual do nó adjacente com o peso da aresta
conectando 0->1. Se for menor que a distância atual de Node, defina-a como a nova distância
atual de N.
4. Marque o nó atual 1 como visitado.
5. Vá para a etapa 2 se houver algum nó não visitado.

# Python implementation of Dijkstra Algorithm

import heapq

class Node:

def __init__(self, v, distance):

self.v = v
 [Link] = distance

def __lt__(self, other):

return [Link] < [Link]

def dijkstra(V, adj, S):

visited = [False] * V

map = {}

q = []

map[S] = Node(S, 0)

[Link](q, Node(S, 0))

while q:

n = [Link](q)

v = n.v

distance = [Link]

visited[v] = True

adjList = adj[v]

for adjLink in adjList:

if not visited[adjLink[0]]:

if adjLink[0] not in map:

map[adjLink[0]] = Node(v, distance + adjLink[1])

else:

sn = map[adjLink[0]]

if distance + adjLink[1] < [Link]:

sn.v = v

[Link] = distance + adjLink[1]

 [Link](q, Node(adjLink[0], distance + adjLink[1]))

result = [0] * V

for i in range(V):

result[i] = map[i].distance

return result

def main():

adj = [[] for _ in range(6)]

V=6

E=5

u = [0, 0, 1, 2, 4]

v = [3, 5, 4, 5, 5]

w = [9, 4, 4, 10, 3]

for i in range(E):

edge = [v[i], w[i]]

adj[u[i]].append(edge)

edge2 = [u[i], w[i]]

adj[v[i]].append(edge2)

S=1

result = dijkstra(V, adj, S)

print(result)

if __name__ == "__main__":
 main()

Warshall’s Algorithm - Algoritmo de Floyd Warshall

Resolve o problema de calcular o caminho mais curto entre todos os pares de vértices em um grafo
orientado (com direção) e valorado (com peso). Grafos Densos

Estrutura genérica

1. Inicialize a matriz Distancia[][] usando o gráfico de entrada de forma que Distancia[i][j]= peso da
aresta de i a j , também Distance[i][j] = Infinito se não houver aresta de i a j.
2. Trate cada nó N como um nó intermediário e calcule a Distância[][] para cada par de nós {i,j}
usando a fórmula:
1. = Distância[i][j] = mínimo (Distância[i][j], (Distância de i a N ) + (Distância de N a j ))
2. = Distância[i][j] = mínimo (Distância[i][j], Distância[i][ N ] + Distância[ N ][j])
3. Com todos os nós tratados como um nó intermediário, agora podemos retornar a matriz
Distance[][] atualizada como nossa matriz de resposta.

# Número de vértices no grafo

V=4

# Define infinito como um valor suficientemente grande.

# Este valor será usado para vértices não conectados entre si

INF = 99999

# Resolve o menor caminho entre todos os pares

# via Algoritmo de Floyd Warshall

def floydWarshall(graph):

""" dist[][] será a matriz de saída

que finalmente terá as menores distâncias

entre todos os pares de vértices """

""" inicializando a matriz de solução

igual à matriz do grafo de entrada

OU podemos dizer que os valores iniciais das menores distâncias

são baseados nos caminhos mais curtos considerando que

não há vértices intermediários """

dist = list(map(lambda i: list(map(lambda j: j, i)), graph))

""" Adiciona todos os vértices um por um

ao conjunto de vértices intermediários.

---> Antes do início de uma iteração,

temos as menores distâncias

entre todos os pares de vértices,

de modo que as menores distâncias consideram apenas

os vértices no conjunto

{0, 1, 2, .. k-1} como vértices intermediários.

----> Após o final de uma iteração, o vértice número k é

adicionado ao conjunto de vértices intermediários e o

conjunto torna-se {0, 1, 2, .. k}

"""

for k in range(V):

# seleciona todos os vértices como fonte, um por um

for i in range(V):

# Seleciona todos os vértices como destino para a

# fonte selecionada acima

for j in range(V):

# Se o vértice k estiver no menor caminho de

# i para j, então atualize o valor de dist[i][j]

dist[i][j] = min(dist[i][j],
 dist[i][k] + dist[k][j]

printSolution(dist)

# Função utilitária para imprimir a solução

def printSolution(dist):

print("A matriz a seguir mostra as menores distâncias\

entre todos os pares de vértices")

for i in range(V):

for j in range(V):

if(dist[i][j] == INF):

print("%7s" % ("INF"), end=" ")

else:

print("%7d\t" % (dist[i][j]), end=' ')

if j == V-1:

print()

# Código do driver

if __name__ == "__main__":

"""

10

(0)------->(3)

| /|\

5| |

| |1

\|/ |

(1)------->(2)
 3 """

graph = [[0, 5, INF, 10],

[INF, 0, 3, INF],

[INF, INF, 0, 1],

[INF, INF, INF, 0]

# Chamada da função

floydWarshall(graph)

Busca e Ordenação
Binary Search - Busca Binária
O Algoritmo de Busca Binária é um algoritmo de busca usado em uma matriz ordenada dividindo
repetidamente o intervalo de busca pela metade .
Estrutura genérica:

1. Divida o espaço de busca em duas metades encontrando o índice do meio “mid” .

2. Compare o elemento do meio do espaço de busca com a chave .
3. Se a chave for encontrada no elemento do meio, o processo será encerrado.
4. Se a chave não for encontrada no elemento do meio, escolha qual metade será usada como o
próximo espaço de busca.
5. Se a chave for menor que o elemento do meio, o lado esquerdo será usado para a próxima
pesquisa.
6. Se a chave for maior que o elemento do meio, o lado direito será usado para a próxima pesquisa.
7. Esse processo continua até que a chave seja encontrada ou o espaço total de busca seja
esgotado

# Código em Python3 para implementar a Busca Binária

# de forma iterativa.

# Retorna a localização de x no array arr

def binarySearch(arr, low, high, x):

while low <= high:

mid = low + (high - low) // 2

 # Verifica se x está presente no meio

if arr[mid] == x:

return mid

# Se x for maior, ignora a metade esquerda

elif arr[mid] < x:

low = mid + 1

# Se x for menor, ignora a metade direita

else:

high = mid - 1

# Se chegar aqui, o elemento

# não estava presente

return -1

# Código do driver

if __name__ == '__main__':

arr = [2, 3, 4, 10, 40]

x = 10

# Chamada da função

result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1:

print("Elemento está presente no índice", result)

else:

print("Elemento não está presente no array")

Quick Sort
QuickSort é um algoritmo de ordenação baseado em Dividir e Conquistar que escolhe um elemento
como pivô e particiona o array fornecido em torno do pivô escolhido, colocando o pivô em sua
posição correta no array classificado.
Estrutura genérica:

1. Escolha um pivô
2. Particione o array em torno do pivô. Após a partição, é garantido que todos os elementos sejam
menores que todos os direitos e obtemos o índice do ponto final dos elementos menores. A
esquerda e a direita não podem ser classificadas individualmente.
3. Chame recursivamente os dois subarrays particionados esquerdo e direito.
4. Paramos a recursão quando há apenas um elemento restante.

def partition(arr, low, high):

# Escolhe o pivô

pivot = arr[high]

i = low - 1

# Percorre arr[low..high] e move todos os elementos menores

# para o lado esquerdo. Os elementos de low a i são menores

# após cada iteração

for j in range(low, high):

if arr[j] < pivot:

i += 1

arr[i], arr[j] = arr[j], arr[i]

# Move o pivô após os elementos menores e

# retorna sua posição

arr[i + 1], arr[high] = arr[high], arr[i + 1]

return i + 1

# Implementação da função QuickSort

def quick_sort(arr, low, high):

if low < high:

 # pi é o índice de partição retornado pelo pivô

pi = partition(arr, low, high)

# Chamadas recursivas para elementos menores

# e elementos maiores ou iguais

quick_sort(arr, low, pi - 1)

quick_sort(arr, pi + 1, high)

# Função para imprimir um array

def print_array(arr):

for i in arr:

print(i, end=" ")

print()

# Código do driver

if __name__ == "__main__":

arr = [10, 7, 8, 9, 1, 5]

print("O array fornecido é")

print_array(arr)

quick_sort(arr, 0, len(arr) - 1)

print("\nO array ordenado é")

print_array(arr)

Merge Sort
Merge sort é um algoritmo de ordenação que segue a abordagem de dividir e conquistar . Ele funciona
dividindo recursivamente o array de entrada em subarrays menores e classificando esses subarrays e,
em seguida, mesclando-os novamente para obter o array classificado.

Estrurura Genérica:
 1. Dividir: Divide a lista ou matriz recursivamente em duas metades até que não possa mais ser
dividida.
2. Conquistar: Cada submatriz é classificada individualmente usando o algoritmo de classificação
por mesclagem.
3. Mesclar: Os subarrays classificados são mesclados novamente em ordem classificada. O processo
continua até que todos os elementos de ambos os subarrays tenham sido mesclados.

def merge(arr, left, mid, right):

n1 = mid - left + 1

n2 = right - mid

# Cria arrays temporários

L = [0] * n1

R = [0] * n2

# Copia os dados para os arrays temporários L[] e R[]

for i in range(n1):

L[i] = arr[left + i]

for j in range(n2):

R[j] = arr[mid + 1 + j]

i = 0 # Índice inicial do primeiro subarray

j = 0 # Índice inicial do segundo subarray

k = left # Índice inicial do subarray mesclado

# Mescla os arrays temporários de volta

# em arr[left..right]

while i < n1 and j < n2:

if L[i] <= R[j]:

arr[k] = L[i]

i += 1
 else:

arr[k] = R[j]

j += 1

k += 1

# Copia os elementos restantes de L[],

# se houver algum

while i < n1:

arr[k] = L[i]

i += 1

k += 1

# Copia os elementos restantes de R[],

# se houver algum

while j < n2:

arr[k] = R[j]

j += 1

k += 1

def merge_sort(arr, left, right):

if left < right:

mid = (left + right) // 2

merge_sort(arr, left, mid)

merge_sort(arr, mid + 1, right)

merge(arr, left, mid, right)

def print_list(arr):

for i in arr:
 print(i, end=" ")

print()

# Código do driver

if __name__ == "__main__":

arr = [12, 11, 13, 5, 6, 7]

print("O array fornecido é")

print_list(arr)

merge_sort(arr, 0, len(arr) - 1)

print("\nO array ordenado é")

print_list(arr)

Counting Sort
Counting Sort é um algoritmo de ordenação não baseado em comparação . Ele é particularmente
eficiente quando o intervalo de valores de entrada é pequeno comparado ao número de elementos a
serem classificados. A ideia básica por trás do Counting Sort é contar a frequência de cada elemento
distinto no array de entrada e usar essa informação para colocar os elementos em suas posições
corretas classificadas.

1.
Estrutura genérica:
2. Declare um array auxiliar countArray[] de tamanho max(inputArray[])+1 e inicialize-o com 0 .
3. Percorra o array inputArray[] e mapeie cada elemento de inputArray[] como um índice do array
countArray[] , ou seja, execute countArray[inputArray[i]]++ para 0 <= i < N .
4. Calcula a soma do prefixo em cada índice do array inputArray [].
5. Crie uma matriz outputArray[] de tamanho N .
6. Percorrer a matriz inputArray[] do fim e atualizar outputArray[ countArray[ inputArray[i] ] – 1] =
inputArray[i] . Além disso, atualizar countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

def count_sort(input_array):

# Encontrando o elemento máximo de input_array.

M = max(input_array)

# Inicializando count_array com 0

 count_array = [0] * (M + 1)

# Mapeando cada elemento de input_array como um índice de count_array

for num in input_array:

count_array[num] += 1

# Calculando a soma prefixada em cada índice de count_array

for i in range(1, M + 1):

count_array[i] += count_array[i - 1]

# Criando output_array a partir de count_array

output_array = [0] * len(input_array)

for i in range(len(input_array) - 1, -1, -1):

output_array[count_array[input_array[i]] - 1] = input_array[i]

count_array[input_array[i]] -= 1

return output_array

# Código do driver

if __name__ == "__main__":

# Array de entrada

input_array = [4, 3, 12, 1, 5, 5, 3, 9]

# Array de saída

output_array = count_sort(input_array)

for num in output_array:

print(num, end=" ")

KMP Algorithm - Algoritmo KMP para pesquisa de padrões

Dadas duas strings txt e pat de tamanho N e M, onde N > M . As strings txt e pat representam o texto e
o padrão, respectivamente. A tarefa é imprimir todos os índices de ocorrências da string pattern na
string text. Use indexação baseada em um ao retornar os índices.

Estrurura Geral: Quando encontramos um conflito entre txt[i] e pat[j], não é necessário retroceder i e
passar a comparar txt[i-j+1..] com pat[0..]. Basta

1. encontrar o comprimento do maior prefixo de pat[0..] que é sufixo de txt[..i],

2. ou seja, encontrar o maior k tal que pat[0..k-1] é igual a txt[i-k+1..i],
3. e passar a comparar txt[i+1..] com pat[k..].

def computeLPSArray(pat):

M = len(pat)

lps = [0] * M

# Comprimento do prefixo-sufixo mais longo anterior

length = 0

i=1

# O loop calcula lps[i] para i = 1 até M-1

while i < M:

if pat[i] == pat[length]:

length += 1

lps[i] = length

i += 1

else:

if length != 0:

length = lps[length - 1]

else:

lps[i] = 0

i += 1
 return lps

def KMPSearch(pat, txt):

M = len(pat)

N = len(txt)

# Cria lps[] que vai manter os valores de prefixo

# sufijo mais longo para o padrão

lps = computeLPSArray(pat)

result = []

i = 0 # índice para txt

j = 0 # índice para pat

while (N - i) >= (M - j):

if pat[j] == txt[i]:

j += 1

i += 1

if j == M:

[Link](i - j + 1)

j = lps[j - 1]

elif i < N and pat[j] != txt[i]:

if j != 0:

j = lps[j - 1]

else:

i += 1

return result
# Código do driver

txt = "geeksforgeeks"

pat = "geeks"

result = KMPSearch(pat, txt)

# Imprime todas as ocorrências (índices baseados em 1)

for index in result:

print(index, end=' ')

Greedy Algorithm - Algoritmo Guloso

Algoritmos gulosos são uma classe de algoritmos que fazem escolhas localmente ótimas em cada
etapa com a esperança de encontrar uma solução global ótima, eles pensam no agora e não nas
consequências futuras, funciona para casos em que a minimização ou maximização leva à solução
necessária.
Estrutura genérica:

1. Declarar um resultado vazio = 0.

2. Fazer a escolha gulosa para selecionar. Se a escolha for viável, adicionamos isso ao resultado
final.
3. Retornar o resultado.

Divide and Conquer Algorithm - Algoritmo Dividir para Conquistar

Uma estratégia de resolução de problemas que envolve dividir um problema complexo em partes
menores e mais gerenciáveis, resolver cada parte individualmente e, então, combinar as soluções para
resolver o problema original
Estrutura genérica:

1. Dividir o problema original em subproblemas menores.

2. Resolver cada um dos subproblemas menores individualmente.
3. Combinar os subproblemas para obter a solução final do problema inteiro.

Problema da Mochila
Dada uma mochila com capacidade máxima de peso de W e um conjunto de itens, cada um tendo um
peso e um valor associado a ele. Decida o número de cada item para levar em uma coleção de modo
que o peso total seja menor que a capacidade e o valor total seja maximizado.

Fractional Knapsack Problem - Quando podemos ““quebrar”” o item para maximizar a capacidade

Estrutura genérica:

1. Calcule a relação ( lucro/peso ) para cada item.

2. Classifique todos os itens em ordem decrescente da proporção.
3. Inicialize res = 0 , limiteAtual = limiteMax.
4. Faça o seguinte para cada item i na ordem classificada:
5. Se o peso do item atual for menor ou igual à capacidade restante, adicione o valor desse item ao
resultado
6. Caso contrário, adicione o item atual o máximo que pudermos e saia do loop.
7. Retornar res .

class Item:

def __init__(self, valor, peso):

[Link] = valor

[Link] = peso

def fractionalKnapsack(W, arr):

# ordena os itens com base na razão

[Link](key=lambda x: ([Link]/[Link]), reverse=True)

res = 0.0

for item in arr:

# se adicionar o item não utrapassa o peso máximo, é adicionado

if [Link] <= W:

W -= [Link]

res += [Link]

# senão, adiciona parte dele

else:

res += [Link] * W / [Link]

 break

return res

# Código Piloto

if __name__ == "__main__":

W = 50

arr = [Item(60, 10), Item(100, 20), Item(120, 30)]

max_val = fractionalKnapsack(W, arr)

print(max_val)

0/1 Knapsack Problem - Quando ou o item é colocado ou não é.

~ solução recursiva ~

Estrutura genérica:

1. considerar todos os subconjuntos de itens

2. calcular o peso total e o lucro de todos os subconjuntos
3. considerar os únicos subconjuntos cujo peso total é menor que W
4. escolher o subconjunto com lucro máximo

def knapSack(W, wt, val, n):

# caso base

if n == 0 or W == 0:

return 0

# se o peso do n-ésimo item é maior que a capacidade máxima, o item nao pode ser incluido

if (wt[n-1] > W):

return knapSack(W, wt, val, n-1)

#retorna o maximo entre os dois casos:

 # (1) n-ésimo item incluso

# (2) n-ésimo item não incluso

else:

return max(

val[n-1] + knapSack(

W-wt[n-1], wt, val, n-1),

knapSack(W, wt, val, n-1))

# codigo piloto

if __name__ == '__main__':

profit = [60, 100, 120]

weight = [10, 20, 30]

W = 50

n = len(profit)

print knapSack(W, weight, profit, n)

~ solução dinamica ~

def knapsack(wt, val, W, n):

# base conditions

if n == 0 or W == 0:

return 0

if t[n][W] != -1:

return t[n][W]

# choice diagram code

if wt[n-1] <= W:

t[n][W] = max(
 val[n-1] + knapsack(

wt, val, W-wt[n-1], n-1),

knapsack(wt, val, W, n-1))

return t[n][W]

elif wt[n-1] > W:

t[n][W] = knapsack(wt, val, W, n-1)

return t[n][W]

# Driver code

if __name__ == '__main__':

profit = [60, 100, 120]

weight = [10, 20, 30]

W = 50

n = len(profit)

# We initialize the matrix with -1 at first.

t = [[-1 for i in range(W + 1)] for j in range(n + 1)]

print(knapsack(weight, profit, W, n))

Bounded Knapsack Problem - Quando além do peso a quantidade de itens é limitada.

~ solução dinamica ~

dp=[]

def maxProfit(profit, weight, n, max_W,

max_E):

# for each element given

for i in range(1,n+1) :

# For each possible

 # weight value

for j in range(1,max_W+1) :

# For each case where

# the total elements are

# less than the constra

for k in range(1, max_E+1) :

# To ensure that we dont

# go out of the array

if (j >= weight[i - 1]) :

dp[i][j][k] = max(

dp[i - 1][j][k],

dp[i - 1][j - weight[i - 1]][k - 1]

+ profit[i - 1])

else :

dp[i][j][k] = dp[i - 1][j][k]

return dp[n][max_W][max_E]

# Driver Code

if __name__ == '__main__':

n=5

profit = [2, 7, 1, 5, 3 ]

weight = [ 2, 5, 2, 3, 4 ]

max_weight = 8

max_element = 2
dp = [[[0 for j in range(max_element + 1)]for i in range(max_weight + 1)] for k in range(n+1)]

print(maxProfit(profit, weight, n, max_weight,

max_element))