Graphs: Intro
#graphs #datastructures #devstudy
Definitions:
Graph: A network that helps define and visualize relationships between various compoenents. In other words: it is a set of vertices and edges where each edge is a connection between vertices.
Neighbours: Vertices are neighbours if connected by an edge
Degree: Number of edges connected to a vertex
Path: Sequence of vertices connect by edges. Paths have an expected length (n of edges in a path)
Cycle: path that starts and end at the same vertex. All cycles are paths but not all paths are cycles.
Connectivity: two vertices are connected if a path exists between them. A graph is connected when all vertices are connected.
Directed graph: Directed means that the edge is uni-directional. Directed graphs can be cyclic or Acyclic.
Weighted graph: Edges are not treated equally. (Usage case: traffic, maps, etc)
Tree Graphs:
Properties of Tree Graphs:
1. connected and acyclic meaning that all vertices are connected by edges but there are no paths that start and finish at the same vertex.
2. Removing edge disconnects graph
3. Adding edge creates a cycle
Ruby Implementation:
Methods Needed:
– initialize with root node
– add a new node (vertex) + validate that it has required edges
– add a new edge – to be called when new node is added
– remove a node + validate that its edges are removed
– remove edge when node is being removed
– sum of all node values