Table of Contents

• A graph is a set of nodes connected by edges.
• A graph can have the following properties
  • Connected: There are no isolated/disconnected nodes.
    • You can get to any node in the graph from any starting node.
  • Directed: The edges have a direction. One node can point to other nodes.
  • Weighted: Each edge has a weight associated with it. This adds a cost to traveling along that edge.
  • Cyclic: There is cycle/loop in the graph. You can go from one node and loop back around to it.
    • If the graph is directed, you have to follow the arrows along the path.
• A simple graph is one that’s:
  • Undirected
  • Unweighted
  • Acyclic
  • Can’t have more than 1 edge between a pair of nodes.
• A tree is a connected simple graph.

Implementing a Graph

• There are two ways to represent a graph in code:
  1. Adjacency List
  2. Adjacency Matrix

Adjacency List

• An adjacency list is a list that tracks what’s adjacent to each node in a graph:

  • What node it is (Node name or ID)
  • The adjacent nodes, or nodes that it points to.
  • Additional data
    • If the graph is weighted, the weight of the edges connecting to adjacent nodes is included.
    • If the graph is undirected, both nodes will point to one another.

• Example

    ![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/aff4fc6f-c884-4656-bcf9-7fcf86c3438b/Untitled.png>)
  

    ![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/3e0efe58-396d-4d0e-b184-e95e55771fd0/Untitled.png>)
  

  • Node 0 points to node 1, which points to 2. Node 2 points to nodes 0 and 3.

• Implementation

    ![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/124ecb8c-e5dd-4717-a23e-8a861c763596/Untitled.png>)
  

  • The graph object is an array (or list) of references to Node objects.
  • Each node contains:
    • An identifier (name or ID)
    • An array (or list) of references to adjacent Nodes.

Adjacency Matrix

• An adjacency matrix is a 2D matrix that stores a value for every possible pair of nodes in your graph. That value determines whether or not that pair of nodes points to each other.

  • If array[i][j] = true or 1, that means node i points to node j.
  • If the graph is undirected (bidirectional), array[j][i] will be the same.
  • If the graph is weighted, the edge weight will be used as the value instead.

• Example

    ![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/677a3c65-1c99-4235-9161-8d2ab051a576/Untitled.png>)
  

• Properties

  • 2D
  • Size NxN, where N is the number of nodes in the graph.
    • The number of array elements is the number of nodes$^2$
  • If the graph is undirected, the matrix will be symmetric

Graph Searching Algorithms

• Search algorithms have several possible uses.
  1. To traverse (and perform some operation on) every node in the graph.
     • Isolated/disconnected nodes aren’t seen.
     • Tree traversal algorithms are a form of DFS.
  2. To find the shortest path between two points (the starting and target nodes).
• Some search algorithms
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Bidirectional Search
  • Dijkstra’s Algorithm
  • A* Search