thbighead’s gists

thbighead / encontrar_ciclos_digrafo.py

Last active April 20, 2017 14:53

Encontra e salva os ciclos de um digrafo usando uma busca em profundidade (complexidade nao piora, continua O(n+m))

	from copy import deepcopy

	# coisos globais
	valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
	valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
	# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
	profundidades_entrada_saida = {}
	pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
	aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
	niveis = {} # nivel de cada vertice na arvore de busca em profundidade

thbighead / k_s.py

Last active April 20, 2017 01:27

Algoritmo k-s feito em Python (usado para descobrir os CFCs de um digrafo)

	# coisos globais
	valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
	valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
	# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
	profundidades_entrada_saida = {}
	pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
	aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
	niveis = {} # nivel de cada vertice na arvore de busca em profundidade
	# conjunto de vertices ainda nao visitados (nunca entraram (e portanto nem sairam) da pilha)
	nao_visitados = set()

thbighead / classificacao_arestas_profundidade_digrafo.py

Last active April 20, 2017 01:30

Classificando arestas da arvore de busca em profundidade feita em um digrafo com Python

	# coisos globais
	valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
	valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
	# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
	profundidades_entrada_saida = {}
	pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
	aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
	niveis = {} # nivel de cada vertice na arvore de busca em profundidade
	# conjunto de vertices ainda nao visitados (nunca entraram (e portanto nem sairam) da pilha)
	nao_visitados = set()

thbighead / transpor_digrafo.py

Created April 17, 2017 02:48

Calcular a transposicao de um digrafo feito com Python

	def transpor_digrafo(digrafo):
	digrafo_t = {}
	for vertice in digrafo:
	digrafo_t[vertice] = []
	for vertice in digrafo:
	for vizinho in digrafo[vertice]:
	digrafo_t[vizinho].append(vertice)
	return digrafo_t

thbighead / criador_de_grafos.py

Created April 17, 2017 00:55

Criador de grafos em representacao de matriz de adjacencias feito com Python

	def cria_grafo(lista_de_vertices, lista_de_arestas):
	grafo = {}
	for vertice in lista_de_vertices:
	grafo[vertice] = []
	for aresta in lista_de_arestas:
	grafo[aresta[0]].append(aresta[1])
	return grafo

thbighead / busca_em_profundidade.py

Last active October 29, 2019 22:55

Snippet em Python para criar uma busca em profundidade de Grafos

thbighead / busca_em_largura.py

Last active July 4, 2022 13:01

Snippet em Python para criar uma busca em largura de Grafos

	grafo = {
	'a': ['b', 'd', 'e'],
	'b': ['a', 'c', 'e'],
	'c': ['b', 'e'],
	'd': ['a', 'e'],
	'e': ['a', 'b', 'c', 'd', 'f'],
	'f': ['e']
	}

	def busca_em_largura(grafo, vertice_do_grafo):

Thales Nathan thbighead