Published on

# Graphs

Authors
•  Name
Curtis Warcup

A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph.

Is a collection of nodes and connections between these nodes.

There is no parent node, starting place.

# Types of Graphs

## Undirected Graph

• No direction to the edges.
• think of a highway system, you can drive both ways on the highway.

## Directed Graph

• useful for modeling relationships where the direction matters.
• traffic flow

## Weighted Graph

• You can have information about the edges.
• Useful for modeling things like roads, where you might want to know the distance between two cities.
• used a lot for calculating optimal paths.

## Cyclic Graph

• when you can get back to the same node you started at.
• common in weighted graphs.

# Terminology

• Vertex: a node
• Edge: connection between nodes
• Weighted/Unweighted: values assigned to distances between vertices
• Directed/Undirected: directions assigned to distances between vertices Undirected = can go from A to B, or B to A.

Directed Graph - often represented with arrows. C is basically a dead end. Unweighted - each edge has no value assigned with it. Weighted graph - has information about the connection between vertices.

Data we are going to represented.

Can use a table. 0 = no connection 1 = has connection

Uses an array or list to store the edges. Can see there's a that `0` has an edge with `5` and `1`.

What if our nodes are not numeric? What is they are string? We use a hash table

Will be going forward using an ADJACENCY LIST because most real world data looks like this (larger and more sparse).

# Graph Class for undirected graph

``````class Graph {
constructor() {
}
}
``````

• write a method called addVertex, which accepts a name of a vertex.
• it should add a key to the adjacency list with the name of the vertex and set its value to be an empty array.
``````class Graph {
constructor() {
}
}
}

let g = new Graph()
``````

• edge represents a connection between vertexes.
• should accept two vertices.
• the function should find in the adjacency list the key of vertex 1 and push **vertex2 **to the array.
• The function should find in the adjacency list the key of vertex2 and push vertex1 to the array.
``````class Graph {
constructor() {
}
}
}
}

let g = new Graph();

console.log(g);
//
{ Dallas: [ 'Tokyo' ], Tokyo: [ 'Dallas' ], Aspen: [] }
``````

## Removing an edge

• This function should accept two vertices, we'll call them vertex1 and vertex2
• The function should reassign the key of vertex1 to be an array that does not contain vertex2
• The function should reassign the key of vertex2 to be an array that does not contain vertex1
``````class Graph {
constructor() {
}
}
}
removeEdge(vertex1, vertex2) {
(v) => v !== vertex2
);
(v) => v !== vertex1
);
//keep everything where it is NOT equal to vertex2
}
}

let g = new Graph();

console.log(g);
//
{
Dallas: [ 'Tokyo' ],
Tokyo: [ 'Dallas', 'Aspen' ],
Aspen: [ 'Tokyo' ]
}

g.removeEdge('Tokyo', 'Dallas');
g.removeEdge('Tokyo', 'Aspen');

console.log(g); // { Dallas: [], Tokyo: [], Aspen: [] }

``````

## Removing a vertex

• will need to remove the vertex AND the edge between them.
• The function should accept a vertex to remove
• The function should loop as long as there are any other vertices in the adjacency list for that vertex
• Inside of the loop, call our removeEdge function with the vertex we are removing and any values in the adjacency list for that vertex
• delete the key in the adjacency list for that vertex
``````    removeVertex(vertex){
}
}

let g = new Graph();

console.log(g);
// { Dallas: [ 'Tokyo', 'Aspen', 'Hong Kong' ],
Tokyo: [ 'Dallas', 'Hong Kong' ],
Aspen: [ 'Dallas', 'Los Angeles' ],
'Los Angeles': [ 'Hong Kong', 'Aspen' ],
'Hong Kong': [ 'Tokyo', 'Dallas', 'Los Angeles' ] }

g.removeVertex("Hong Kong");

console.log(g);
// { Dallas: [ 'Tokyo', 'Aspen' ],
Tokyo: [ 'Dallas' ],
Aspen: [ 'Dallas', 'Los Angeles' ],
'Los Angeles': [ 'Aspen' ] }
``````

``````class Graph {
constructor() {
}
}
}
removeEdge(vertex1, vertex2) {
}
removeVertex(vertex) {
}
}
}

let g = new Graph()