top of page
This site was designed with the
.com
website builder. Create your website today.Start Now

Graphs

Tutoring > Data Structures > Graphs

Graphs are made up of elements and connections between those elements. The elements and the connections can each be given values. A graph is much like a tree, in fact, a tree is just a restricted type of graph.

Graph properties

Compsition of graphs:

  • Nodes - The elements in a graph. Also called vertices.

  • Edges - The connections between the nodes in a graph.

Class of graphs:

  • Directed or undirected.

  • Weighted or unweighted. 

  • Sparse or dense.

Weighted and unweighted graphs

A graph is said to be weighted if the edges between the nodes are given a value. A simple analogy for this might be distances between cities on a map, where the nodes represent the cities and the weight of each edge is the distane between them.

An unweighted graph is one where no weight or value is specified for the edges.

Directed and undirected graphs

Direction - A directed graph is one such that we can travel from one node to another in a certain direction (these are unidirectional graphs).

Graphs are assumed to be bidirectional by default.

The graph in the picture is directed, in fact it is unidirectional.

 

Trees are directed graphs which do not contain cycles.

Sparse graphs, dense graphs

A graph is sparse if for n nodes, there is significantly less than n^2

(n squared) edges.

A graph is dense ifit has close to the maximum possible number of edges. The graph in the picture has the maximum number of edges so is dense.

Minimal Spanning Trees

A minimal spanning tree is a subgraph within another weighted graph. It is a tree that visits every node and does so using the overall  "least cost" paths, meaning the least weighted paths between the nodes. They have no cycles, a tree cannot have cycles. A connected graph without cycles is a tree.

The total weight of the edges connected together will be less than or equal to every other minimal spanning tree for the graph.

 

Prim's Algorithm

Finds a minimal spanning tree for a given graph. 

It is a greedy algorithm which means it chooses the optimal immediate step. So for example, we are looking for the least weight, if we had a choice of 1 or 3 we would choose 1 as this is the lowest. This may not necessarily give the global best result for all algorithms. Prim's algorithm is vertex based.

How to perform Prim's algorithm.

  1. Arbitrarily pick a vertex (node) to begin. Use this to initialise the tree, this is our first node.

  2. Grow the tree by one edge, choosing the path with the minimum weight. Do not pick one that will make a cycle!

  3. Repeat step 2 until all vertices are in the tree

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The efficiency of this algorithm can be improved by using a priority queue, either a binary heap or a Fibonacci heap.

 

Dijkstra's Algorithm

Finds the shortest path between nodes in a given graph. Given a node, it computes the shortest path to every other node (the path with the least total weight). The input is a directed weighted graph and the output is an array in sorted order of distance (weight).

  • We start with an adjacency matrix, assigning infinity to any nodes we cannot immediately access from the start node. We have a bunch of over-estimates of the shortest distance to each node. The over-estimates to any node we cannot immediately access is infinity.

  • The algorithm repeatedly decreases these over-estimates until it is no longer possible to do so. When this happens, the node is said to be "tight".

  • Because the algorthim records the predecessor of each node, and each step is chosen by the smallest weight, eventually we end up with the smallest total weight once we reach the goal node. So once all nodes have been visited, we can say that they all all tight, and the algorithm has finished.

  • We can improve the efficiency of Dijkstra's algorthim by using a priority queue, namely a heap tree. By assigning a priority to each weight we can more quickly traverse through.

  • For a fully connected graph, the time complexity would be O(n^2), however, in practice graphs tend to be much more sparse and so the time complexity using a heap tree is O(n log n).

bottom of page