Three ways to store a graph in memory, advantages and disadvantages

by

One way to analyze these is in terms of memory and time complexity (which depends on how you want to access the graph).

Storing nodes as objects with pointers to one another

  • The memory complexity for this approach is O(n) because you have as many objects as you have nodes. The number of pointers (to nodes) required is up to O(n^2) as each node object may contain pointers for up to n nodes.
  • The time complexity for this data structure is O(n) for accessing any given node.

Storing a matrix of edge weights

  • This would be a memory complexity of O(n^2) for the matrix.
  • The advantage with this data structure is that the time complexity to access any given node is O(1).

Depending on what algorithm you run on the graph and how many nodes there are, you’ll have to choose a suitable representation.

More Related Contents:

  1. Finding all cycles in undirected graphs
  2. Distributed tensorflow: the difference between In-graph replication and Between-graph replication
  3. How do you plot bar charts in gnuplot?
  4. Tensorflow: executing an ops with a specific core of a CPU
  5. Line plot in GnuPlot where line color is a third column in my data file?
  6. Tensorflow: How to convert .meta, .data and .index model files into one graph.pb file
  7. How to plot intersecting ranges in Excel/R/Matlab [closed]
  8. c++ error : Segmentation fault (core dumped)
  9. Generating a PNG with matplotlib when DISPLAY is undefined
  10. How to prevent numbers being changed to exponential form in Python matplotlib figure
  11. matplotlib (equal unit length): with ‘equal’ aspect ratio z-axis is not equal to x- and y-
  12. How to plot multiple functions on the same figure, in Matplotlib?
  13. Generating statistics from Git repository [closed]
  14. How to display all x labels in R barplot?
  15. draw polar graph in java
  16. Iterative DFS vs Recursive DFS and different elements order
  17. Dependency graph of Visual Studio projects
  18. How to implement depth first search for graph with a non-recursive approach
  19. How to convert to D3’s JSON format?
  20. Cytoscape like tools in java to build a graph
  21. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  22. How to combine 2 plots (ggplot) into one plot?
  23. Drawing a graph or a network from a distance matrix?
  24. How to add braces to a graph?
  25. Enumerating all paths in a directed acyclic graph
  26. Command-line Unix ASCII-based charting / plotting tool
  27. Planar Graph Layouts
  28. Plot inside a plot
  29. Cut set of a graph, Boost Graph Library
  30. adding custom vertices to a boost graph

Leave a Comment