With advancements in technology, computer science is everywhere. It dictates the working of our lives. You may have completed your B.Com Hons, but you will still have to have a basic idea of computer science in order to survive. It has become like a language without which communication is impossible. Here’s a fundamental basic concept in computer science, graphs. Let’s start by defining data structures and slowly work our way down.
Data structure and its classification
A data structure is a mathematical or logical way of organizing and storing data. They are classified into-primitive and non-primitive data structures.
Under primitive data structures, we have integer (int), character (char), float, double. These are inbuilt or pre-defined data types which work according to a pre-defined set of rules.
Sometimes these primitive data structures are not enough for a programmer to implement his ideas and run a code. In such cases derived and user-defined data structures (non – primitive) are necessary. Non – primitive data structures are further divided into – linear and non–linear data structures. Linear data structures include arrays, stacks, queues, lists wherein data or elements are stored sequentially; whereas in non-linear data structures data is not stored sequentially but usually in a hierarchical order Trees and Graphs are examples of this.
What is a graph?
Consider a non-empty set of vertices V and an ordered set of edges E. A graph G (V, E)is a set of these vertices and edges. It is a non – primitive, non – linear data structure. Usually, vertices are represented using 1-D arrays and edges using 2-D arrays.
Definitions related to graphs
Vertex – Each node of the graph is a vertex.
Edge – The path between two nodes.
Adjacency – Two vertices are said to be adjacent if they are connected to each other through an edge.
Path – The sequence of edges between two vertices.
Complete graph – a graph who’s each vertex is connected to every other vertex.
Subgraph – A graph is said to be a subgraph of another graph if all the vertices and edges of the first graph are present in the second graph.
Connectivity – two vertices are said to be connected if there is a path in the graph between the two vertices.
Cycle – a cycle is a simple path in which the first and last vertex is the same.
Degree – the degree of a vertex implies the number of other edges incident on that vertex.
Types of graphs
Directed graphs – A graph is said to be directed if it consists of an ordered pair of vertices, i.e. all its edges are directed.
Undirected graph – A graph is said to be undirected if it consists of an unordered pair of vertices, i.e. all its edges are undirected.
Importance of graphs
A Graph is an important data structure because it represents relationships. Graphs are more expressive than trees as they can incorporate cycles, multiple edges etc. Being very powerful abstractions, graphs are important in data modeling. The concept of graphs is used in social networking, transportation networks, document links, for example searching for Best MBA Colleges in Pune and many links appear wherein each website is a vertex and each hyperlink is an edge. Also used neural networks, quantum field theory, robot planning etc.
We would like to thank Harshith Kulal for this Community Contribution of CoderInMe.
All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme