/Grafos

Primary LanguageC++

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.