To com um tabalho na faculdade pra fazer mas ainda estou meio perdido sobre grafos. Preciso implementar dois algorítmos de construção de uma estrutura de adjacência, um para o grafo direcionado e outra para o grafo não direcionado, para qualquer que seja a matriz.
quem puder dar um help agradeço.
obs: pode ser em C ou JAVA.
Que tipo de “help” você precisa? Não sabe fazer uma matriz?
Não tem nenhum material de grafos aí, descrevendo como é uma matriz de adjacência?
Seu algoritmo deve retornar uma matriz ou deve retornar se o grafo é direcionado ou não, de acordo com uma matriz?
Do jeito que você descreveu, parece que quer alguém faça pra você. É isso mesmo?
Abraço.
não cara, só to perdido na lógica e queria que alguém explicasse, só tive uma aula de grafo e ele ja pediu a implementação.
só coloquei a obs como complemento mesmo, pois ele quer em c ou java.
abçs
Eu criaria as classes Grafo, Vertice e Aresta.
Um grafo é composto de Vértices.
Uma Aresta conecta dois Vértices.
A diferença entre um grafo dirigido (ou direcionado) para um grafo não dirigido (ou não direcionado) é que em um grafo não dirigido você pode tanto ir quanto voltar de um vértice para o outro.
Na implementação a diferença é que se o Grafo é não dirigido, quando você cria uma aresta V1–>V2 você também cria uma Aresta V2–>V1, de forma que você possa ir de V1 pra V2 e voltar de V2 pra V1.
2 curtidas
Mas o que esse programa deve fazer? Só exibir um grafo qualquer como uma matriz de adjacência? Deve permitir adicionar e remover vértices e arestas?
Matriz de adjacência é um dos conceitos mais básicos de grafos, e uma das formas mais simples de representá-lo. Tanto que, se você não quiser, não precisa criar classes para vértices e arestas como sugerido pelo staroski (mas ajuda, caso você queira trabalhar com o grafo). Pode trabalhar o grafo diretamente como uma matriz de adjacência.
Exemplo:
As matrizes ficariam:
// não direcionado
grafoA = [
[ 0, 1, 1, 1 ], // arestas de A
[ 1, 0, 0, 1 ], // arestas de B
[ 1, 0, 0, 1 ], // arestas de C
[ 1, 1, 1, 0 ] // arestas de D
]
// direcionado
grafoB = [
[ 0, 1, 1, 1 ], // arestas de A
[ 0, 0, 0, 1 ], // arestas de B
[ 0, 0, 0, 1 ], // arestas de C
[ 0, 0, 1, 0 ] // arestas de D
]
Se seu professor não te passou nenhum material, dê uma procurada na internet. Tem vários recursos explicando esse e outros conceitos. Se estiver disposto à pegar um livro, o Grafos Teoria, Modelos, Algoritmos, do Boaventura Neto, explica isso logo no começo.
Abraço.
1 curtida
deve apenas exibir um grafo qualquer.
obrigado pela ajuda.
obrigado pela sugestão =D