Trabalho da cadeira de Teoria dos Grafos sobre estrutura de dados para grafos utilizando Python.
- A biblioteca contém duas classes: uma correspondente à estrutura de dados "Grafo" e outra à "Digrafo".
- A biblioteca fornece os seguintes métodos para ambas as classes:
| Método | Retorno |
|---|---|
| G.n | Número de vértices do grafo |
| G.m | Número de arestas do grafo |
| G.viz(v) | Vizinhaça do vértice v |
| G.d(v) | Grau do vértice v |
| G.w(uv) | Peso da aresta uv |
| G.mind | Menor grau presente no grafo |
| G.maxd | Maior grau presente no grafo |
| G.bfs(v) | Executa uma busca em largura (BFS) a partir do vértice v e retorna duas listas: "distância" - representa a distância entre cada vértice e v - e "pi" - armazena o vértice predecessor (pai) no caminho de v até cada vértice |
| G.dfs(v) | Executa uma busca em profundidade (DFS) a partir do vértice v e retorna três listas: "pi" - armazena o vértice predecessor na árvore de busca, "v.ini" - indica o tempo de início da visita a cada vértice e "v.fim" - indicia o tempo de término da visita a cada vértice |
| G.bf(v) | Executa o algoritmo de Bellman-Ford a partir do vértice v como origem. Retorna duas listas: "distância" - representa as distâncias mínimas entre v e cada vértice e "pi" - armazena o vértice predecessor (pai) do caminho mínimo de v até cada vértice |
| G.dijkstra(v) | Executa o algoritmo de Dijkstra a partir do vértice v como origem. Retorna duas listas: "distância" - representa as distâncias mínimas entre v e cada vértice e "pi" - armazena o vértice predecessor (pai) do caminho mínimo de v até cada vértice |