Graphs

Essential Graph Terms

• Vertex - a node
• Edge - connection between nodes
• Weighted / Unweighted - values assigned to distances between vertices.
  each edge has value associated with it or not.
• Directed / Undirected - directions assigned to distanced between vertices
  one way or both way relationship or not. the polarity of the edges.
  facebook : directed graphs, instagram: undirected graphs. 

Two diffent ways fo expressing the edges, the relationships between vertices.

 

Adjacency Matrix

undirected graph

A matrix is a two diemensional structure usually implemented with nested arrays.

Every time we add a new node, we have to add an entire new row and column.

Takes up more space

Slower to iterate over all edges

Faster to lookup specifc edge

 

Adjacency List

 

Could use hash tables

take uo less space in sparse graphs

Faster to iterate over all edges

Can be slower to lookup specific edge

 

// Adjacency List

class Graph{
    constructor() {
      this.adjacencyList = {};
    }
   addVertex(vertex) {
     if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(v1, v2) {
     this.adjacencyList[v1].push(v2);
     this.adjacencyList[v2].push(v1);
   }
   removeEdge(v1, v2) {
     this.adjacencyList[v1] = this.adjacencyList[v1].filter( v => v !== v2);
     this.adjacencyList[v2] = this.adjacencyList[v2].filter( v => v !== v1);
   }
   removeVertex(v1) {
     while(this.adjacencyList[v1].length) {
       const ajacentVertex = this.adjacencyList[vertex].pop();
       this.removeEdge(v1, adjacentyVertex);
     }
     delete this.adjacencyList[v1];
   }
}