Data Structures and Algorithms in Kotlin-3

This part includes:

5.Graphs

I suggest you try to code the examples while you’re reading or after, you can use online kotlin playground https://play.kotlinlang.org/

Part 1: Data Structures and Algorithms in Kotlin-1

Part 2: Data Structures and Algorithms in Kotlin-2

1.Graphs

A graph is a data structure that captures relationships between objects. It’s made up of vertices connected by edges. In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. This lets you choose the cheapest or shortest path between two vertices.

Directed Graphs: As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse, as an edge may only permit traversal in one direction.

Undirected Graphs: You can think of an undirected graph as a directed graph where all of the edges are bi-directional.

This interface describes the common operations for a graph:

createVertex(): Creates a vertex and adds it to the graph.

addDirectedEdge(): Adds a directed edge between two vertices.

addUndirectedEdge(): Adds an undirected (or bi-directional) edge between two vertices.

add(): Uses EdgeType to add either a directed or undirected edge between two vertices.

edges(): Returns a list of outgoing edges from a specific vertex.

weight(): Returns the weight of the edge between two vertices.

Here, you’ve defined a generic Vertex class. A vertex has a unique index within its graph and holds a piece of data

To connect two vertices, there must be an edge between them. An Edge connects two vertices and has an optional weight.

Adjacency list

For every vertex in the graph, the graph stores a list of outgoing edges.

Vertices -> Adjacency Lists

Singapore -> Tokyo, Hong Kong

Hong Kong -> Tokyo, Singapore, San Francisco

Tokyo -> Singapore, Hong Kong, Detroit, Washington

Detroit -> Tokyo

Washington -> Tokyo, San Francisco

San Francisco -> Hong Kong, Washington

There’s a lot you can learn from this adjacency list:

1. Singapore’s vertex has two outgoing edges. There’s a flight from Singapore to Tokyo and Hong Kong.
2. Detroit has the smallest number of outgoing traffic.
3. Tokyo is the busiest airport, with the most outgoing flights.

Here, we’ve defined an AdjacencyList that uses a map to store the edges.

Here, we create a new vertex and return it. In the adjacency list, we store an empty list of edges for this new vertex.

That there are directed and undirected graphs.

This method creates a new edge and stores it in the adjacency list.

Adding an undirected edge is the same as adding two directed edges.

add() is a convenient helper method that creates either a directed or undirected edge. This is where interfaces with default methods can become very powerful.

This is a straightforward implementation: You either return the stored edges or an empty list if the source vertex is unknown.

Here, you find the first edge from source to destination; if there is one, you return its weight

Visualizing the adjacency list

You’ve finally completed your first graph. You’re ready to try it out by building a network.

Building a network

That’s all for the final part. I hope everything is clear enough to understand. You can find full code and more examples with details in my github.

If you find this helpful, please don’t forget to follow, that motivates me so much to keep writing. 💙

GitHub - betulnecanli/Kotlin-Data-Structures-Algorithms: 📒Data Structures and Algorithms in Kotlin

Done!

Sources :

1-Data Structures & Algorithms in Kotlin ( Book by Irina Galata and Matei Suica)

2- www.geeksforgeeks.org