GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

Grafo não direcionado


#1

Olá,
Alguem me pode explicar o que difere um grafo direcionado de um não direcionado
Obrigado


#2

https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/graphs.html
Nesse site tem a resposta


#3

Um grafo direcionado temos uma direção, 1 --> 2, ou seja, um arco, na matriz de adjacência:

0 1
0 0

No grafo não direcionado, temos uma aresta, 1-- 2 , na matriz de adjacência:
0 1
1 0

Pense em grafos não direcionado como uma rua de mão única, direcionado como uma rua de mão dupla.

Dê uma olhado no livro do Boa Ventura.


#4

Na verdade é o contrário.
No grafo direcionado a aresta tem um único sentido, ou seja, uma rua de mão única.
No grafo não direcionado a aresta tem dois sentidos, ou seja, uma rua de mão dupla.

Inclusive ao implementar, o que se faz para representar as ligações em grafos não direcionados é criar duas arestas direcionadas em sentidos opostos.
Por exemplo uma aresta a--b, na prática é implementada criando duas arestas, uma a-->b e outra b-->a.