Notes on Graph Data Structure

Graphs

flowchart LR; classDef FixFont font-size:11px Cycle:A,B,C,D,E,F,A; id1((A)):::FixFont---|One|id2((B)):::FixFOnt; id1---|Six|id6; id2---|Two|id3((C)):::FixFont; id1---id3; id3((C))---|Three|id4((D)):::FixFont; id4---id5((F)):::FixFont; id5---|Five|id6; id4---|Four|id6((E)):::FixFont; linkStyle 1 font-size:1px

Graphs are used to show relationships between data and can sometimes be called a network. They consist of edges and a “node” or “vertex”. Nodes and edges can store data, so graphs are abstract. A representation of how a graph could look like for a social network is this.

Real Life Graph Example

flowchart LR; Edges-Connection:Met,Lived-In-Same-city,Worked-TogetherEdges-Data:Amount-messaged-to-person:::FF id1(Jing)---|Two|id2(Brynn); id1---|Four|id3(Pranav); id3---|Zero|id2; id2---|Ten|id4(Trish); id3---|Six|id4; classDef default font-size:11px;

Flight Path Example

flowchart LR; Edges-Data:Flight-time D(Delhi)---|5.5 hours|K(KL) K---|8 hours| T(Tokyo) T---|11 hours|S(SF) classDef default font-size:11px;

Graph Types

Directed Graph

Edges can have a direction, meaning the relationship applies one way not the other. Below we see a directed graph showing the origin point and the city you travel to. You could also have two edges displaying a round trip.

Undirected Graph

Are graphs that have no sense of direction with edges, if for example you have a graph with people who know each other, directed edges are unnecessary.

Cycles Cycles are graph exclusive, and allow you to come back to that node if you were to follow edges back to it. They are dangerous when implementing algorithms due to infinite loops. You need to make sure the graph is acyclic(meaning it has no cycles). One common type is a DAG(Directed Acyclic Graph, a graph with no cycles).

flowchart LR; A((A))-->B((B)) A-->C((C)) classDef default font-size:11px;

A connected graph has no disconnected vertices

flowchart LR; A((A))---B((B))---C((C))---D((D))---E((E)) classDef default font-size:11px;

Weakly Connected

A directed graph is weakly connected when only replacing all of the directed edges with undirected edges can cause it to be connected. Imagine that your graph has several vertices with one outbound edge, meaning an edge that points from it to some other vertex in the graph. There’s no way to reach all of those vertices from any other vertex in the graph, but if those edges were changed to be undirected all vertices would be easily accessible.

Connected and strongly Connected

Here we only use “connected graph” to refer to undirected graphs. In a connected graph, there is some path between one vertex and every other vertex. Strongly connected directed graphs must have a path from every node and every other node. So, there must be a path from A to B AND B to A.

Graph Representation

in an OOP language, vertex and edges could be represented as

class Vertex {  
constructor(name, id)  
this.name = name  
this.id = id

class Edge 
{  
constructor(strength, id) 
 this.strength = strength  
this.id = id
}

// A way to represent connections on simple graphs that only use listsEdge List(see diagram below)[[0,1],[1,2], [1,3],[2,3]] 2D Array//Another way is, vertex has an id that corresponds to index in arrayAdjacency List(see diagram below)[[1],[0,2,3], [1,3],[1,2]] 2d array// Finally an adjacency matrix(2d array with subarrays of same length, sometimes called a rectangular array). The outer array corresponsed to the id, and the inner array tells you whether or not it has a connection with a node of that index id, with a boolean check of sortsAdjacency matrix(see diagram below)[[0,1,0,0], [1,0,1,1], [0,1,0,1], [0,1,1,0]]/* You will end up choosing the representation based on your needs, and what operation you will be performing the most. If you are looking for the number of edges connected to a particular node, adjacency matrix will probably be the fastest. */

flowchart LR; 0((0))---1((1)) 1---2((2)) 1---3((3)) 2---3 classDef default font-size:11px;

Published Apr 18, 2022

Front End Developer focused on accessibility, functional programming and UI/UX.