Grafos

• Um grafo é par G = (V, E), onde

  • V é um conjunto finito de elementos chamados vértices
  • E é um conjunto finito de pares não-ordenados de vértices chamados de arestas (edges).

• Representação

  • Matriz de Adjacências
    É uma matriz quadrada A de ordem |V|, cujas linhas e colunas são indexadas pelos vértices em V, e tal que:

   A[i, j] = { 1 se (i, j) pertence a E,
   	        { 0 caso contrário.
  

  

  

  • Lista de Adjacências
    Para cada vértice v, temos uma linked list Adj[v] dos vértices adjacentes a v, ou seja, w aparece em Adj[v] se (v, w) é uma aresta de G. Os vértices podem estar em qualquer ordem em uma lista.

  

  

---

Busca em Largura

Busca em Profundidade

Verificacao de Bipartição

Mostrar um caminho de um nó a outro

Ordenação topológica