Graphs play a critical role in computer science. Here is an example of an undirected graph:

Undirected Graph Example

There are two main ways to represent a graph.

Adjacancy Matrix

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

Adjacancy Matrix

Adjacancy List In The Vertices (Nodes)

An array of lists is used. Size of the array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is adjacency list representation of the above graph.

Adjacancy List

(Examples and explanations taken from

Graph Exercise

Take the following graph showing cities and their distances.

Graph Example (Example taken from

  1. Choose the most appropriate representation for this graph.
  2. Implement the graph.
  3. Write a method that outputs the graph to console, in the way as described below.
    Mannheim: 85 km
    Würzburg: 217 km
    Kassel: 173 km
    Karlsruhe: 80 km
    Frankfurt: 85 km

Dijkstra Algorithm

The Dijkstra algorithm is an algorithm that allows finding the shortest path between two graph nodes. Please implement the Dijkstra algorithm on the graph shown above.

You find a good description (pseudocode + visual explanation) in the Wikipedia article on it:

results matching ""

    No results matching ""