Skip to content

Instantly share code, notes, and snippets.

@criskgl

criskgl/graphsGeneral.md

Last active August 31, 2019 11:52
Show Gist options
  • Save criskgl/b8f21d7a9fb0c387d5dfb1197a6d942b to your computer and use it in GitHub Desktop.
Save criskgl/b8f21d7a9fb0c387d5dfb1197a6d942b to your computer and use it in GitHub Desktop.
Download ZIP
Raw
graphsGeneral.md

Graphs

Components

  • vertex: each node of the graph
  • edges: describe realationships between vertices

Types

  • Weigthed / Not Weigthed
  • Directed / Undirected

Representation

1. Adjacency Matrix

An adjacency matrix, once it has been formed can give us another piece of infromatio looking at rows and columns. Adjacency Lists which hive us the neighbours of a given node. For example if we want to know the node 4 neighbours we just look at row or column 4.

  • For an undirected graph the SPACE USAGE is
  • n^2 | For n vertices

2. Linked Lists storage

Properties

  • For an undirected graph the SPACE USAGE is
  • n + e*2*2 | For n vertices and e vertices

Maximum total number of edges with n vertices

Undirected graph

  • (n*(n-1))/2

Directed graph

  • (n*(n-1))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment