Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos, bfs(v), DFS(G), BFS(G), dfs(v), a (c), G = <V,E>, V = {a,b…
Grafos
Conjunto de vértices e arestas
Vértices são elementos
Arestas ligam vértices
Possuem direção ou não
Possuem peso ou não
Representação
Matriz de adjacência
Lista de adjacência
Se todas as arestas possuem direção
Direcionado ou Digrafo
Se todas as arestas não possuem direção
Não direcionado
Todos os vértices ligados
Completo
Poucas arestas faltando
Denso
Poucas arestas existentes
Esparso
Caminho
Conjunto de arestas
Ligam vértice a ao vértice b
Simples
Vértices visitados uma única vez
Não simples
Vértices visitados mais de uma vez
Conectado
Para todo vértice a e todo vértice b
Existe caminho de a para b
Ciclo
Existe caminho de a para a
Sem que uma mesma aresta seja visitada mais de uma vez
bfs(v)
input v
contador++
v.marcado = contador
cria fila
coloca v na fila
enquanto fila não vazia
para cada w em V & ((v,w)|(w,v)) em E
se w.marcado == 0
contador++
w.marcado = contador
coloca v na fila
remove primeiro da fila
DFS(G)
input G = <V,E>
para cada v em V
contador = 0
v.marcado = 0
para cada v em V
se v.marcado == 0
dfs(v)
BFS(G)
input G = <V,E>
para cada v em V
contador = 0
v.marcado = 0
para cada v em V
se v.marcado == 0
bfs(v)
dfs(v)
input v
contador++
v.marcado = contador
para cada w em V & ((v,w)|(w,v)) em E
se w.marcado == 0
dfs(w)
a
c
b
Vértice
Aresta
G = <V,E>
V = {a,b,c}
E={(a,b),(a,c),(b,c)}