Graph Algorithms

Graph algorithms studied in the Graph Theory and Application (TAG - Teoria e Aplicação de Grafos) class at Universidade de Brasília (UnB) in the first semester of 2021.

Available Algorithms

The notebooks are divided in two parts: "e1", where you can find more basic algorithms and applications of Graph Theory; and "e2", with more advanced algorithms and applications.

The algorithms are applied to graphs modeled as adcjacency lists - in most cases using sets with dicts.

You can see the list below of what is available in this repository:

E1 Algorithms

• Undirected Graph as Abstract Data Type (ADT)
• Depth First Search (DFS)
• Bron-Kerbosch Algorithm
• Local Clustering Coefficient and Average Clustering Coefficient
• Kahn Algorithm
• Kosaraju-Sharir Algorithm
• Topological Order (using DFS)

E2 Algorithms

• Breadth First Search (BFS)
• Bipartite Graph Detection
• Find Maximum Matching
• Find Minimum Cover Vertex
• Ford-Fulkerson Algorithm
• Gale-Shapley Algorithm (applied to hospitals and couples)
• Greedy Coloring Graph Algorithm
• Prim Algorithm

License

MIT