Graphs - andrewkyllo-401-advanced-javascript/seattle-javascript-401d34 GitHub Wiki

  • A non-linear data structure that can be looked at as a collection of vertices potentially connected by line segments named edges.

Vertex - Also called a "node", is a data object that can have zero or more adjacent vertices

Edge - A connection between two nodes

Neighbor - Adjacent nodes connected via an edge

Degree - The number of edges connected to a vertex

Directed vs Undirected

Undirected Graphs

  • A graph where each edge is undirected or bi-directional. This means that the undirected graph does not move in any direction.

Directed Graphs (Digraph)

  • A graph where every edge is directed
  • Each node is directed towards another node with a specific requirement of what node should be referenced next

Complete vs Connected vs Disconnected

Complete Graphs

  • All nodes are connected to other nodes

Connected

  • All vertices/nodes have at least one edge

Disconnected

  • Some vertices may no have edges

Acyclic vs Cyclic

Acyclic Graph

  • A directed graph without cycles
  • A cycle is when a node can be traversed through and potentially end back at itself

Cyclic Graphs

  • A graph that has cycles
  • A path of defined length that starts and ends at the same vertex

Graph Representation

Adjaceny Matrix

  • Represented through a 2-dimensional array. If there are n vertices, then we are looking at an n x n Boolean matrix
  • Each row and column represents each vertex of the data structure. The elements of both the column and the row must add up to 1 if there is an edge that connects the two, or zero if there isnt a connection

Adjacency List

  • The most common way to represent graphs.
  • A collection of linked lists or array that lists all of the other vertices that are connected.

Weighted Graphs

  • A grap with numbers assigned to its edges called weights
  • Represented by setting elements in a 2D array to weight between paths

Traversals

Breadth First
  • Similar to the breadth first traversal of a tree.
  • The possibility of cycles allow for infinite loops
  • Create a visited flag to ensure we havent visited a node before Algorithm for breadth first traversal:
    1. Enqueue the declared start node into the Queue
    2. Create a loop that will run while the node still has nodes present
    3. Dequeue the first node from the queue
    4. If the Dequeue'd node has unvisited child nodes, mark the unvisited children as visited and re-insert them back into the queue
Depth First
  1. Push the root node into the stack
  2. Start a while loop while the stack is not empty
  3. Peek at the top node in the stack
  4. If the top node has unvisited children, mark the top node as visited and then Push any unvisited children back into the stack
  5. If the top node does not have any unvisited children, `Pop that node off the stack
  6. Repeat until stack is empty