Graph

Introduction

This repository contains an implementation of various types of graphs with the collection of graph algorithms made for educational purposes.

Graphs

The following types of graphs are implemented:

• Undirected graph

  • unweighted
  • weighted

• Directed graph

  • unweighted
  • weighted

• Mixed graph

  • unweighted
  • weighted

Algorithms

The following graph algorithms are implemented:

• Traversal/searching

  • Depth-first search (DFS)
  • Breadth-first search (BFS)

• Finding shortest distances

  • Dijkstra's algorithm
  • Floyd-Warshall's algorithm
  • Lee's algorithm

• Finding the graph's spanning tree of minimal weight

  • Prim's algorithm
  • Kruskal's algorithm

• Cycles

  • Detecting cycles in graph
  • Finding Euler cycle in graph

• Connected components

  • Counting graph's connected components
  • Bridges searching
  • Articulation points searching

• Other

  • Topological sorting
  • Graph vertex coloring