/graph-python

Graphs implementation using Adjacency Matrix, coded in Python.

Primary LanguagePythonMIT LicenseMIT

Graph implementation

This is a graph implementation, using adjacency matrix on Python.

Graph

Following methods are included:

  • Number of vertices and edges
  • Number of pending and isolated vertices
  • Number of components
  • Degree of vertices and its neighbors
  • Checks if the graph is simple, regular, null, complete, eulerian and unicursal
  • Complementary graph
  • Checks if the graph is biparted
  • Depth First Search
  • Breadth First Search
  • Checks if the graph is a tree
  • Minimum spanning tree, obtained by Prim's Algorithm
  • Minimum spanning tree, obtained by Kruskal's Algorithm
  • Number of cut-vertices/articulation points

Digraph

  • Checks if graph is regular, balanced, strongly connected and eulerian
  • Dijkstra: shortest path to all vertices starting from 0

Inputs

The graph will be read from a .txt file. There are samples on the folder input.

They were taken from: VisuAlgo - Graph Data Structures

License

This code is released under MIT License.