What are Graphs in Data Structure?

A graph in data structure is a collection of nodes (also called vertices) and edges that connect them. The nodes represent entities, such as people or places, and the edges represent relationships or connections between them. Graphs can be used to model a wide variety of real-world systems, such as social networks, transportation networks, and computer networks. They can also be used for solving problems in computer science, such as searching for the shortest path between two nodes or finding groups of connected nodes (also called clusters or communities). There are different types of graphs, including directed and undirected, weighted and unweighted, and simple and multigraph.

How Graphs Works in Data Structure

A graph works by representing entities as nodes and their relationships as edges. The nodes in a graph can be thought of as points or vertices, and the edges can be thought of as lines or arcs that connect them.

In an undirected graph, edges have no direction and can be traversed in both directions, while in a directed graph, edges have a direction and can only be traversed in one direction.

A weighted graph assigns a weight or cost to each edge, which can represent the distance or cost of traversing that edge. An unweighted graph does not assign any weight to its edges.

A simple graph has no parallel edges or self-loops, while a multigraph can have multiple edges between the same pair of nodes.

Graphs can be represented in different ways, such as:

  • Adjacency List: A list of all the nodes in the graph, with a list of the nodes that each node is connected to.
  • Adjacency Matrix: A matrix where the rows and columns represent the nodes in the graph, and the entries indicate whether there is an edge between two nodes.
  • Incidence Matrix: A matrix where the rows represent the nodes in the graph and the columns represent the edges, and the entries indicate whether a particular node is an endpoint of a particular edge.

Different algorithms can be applied to graph data structures, such as:

  • Searching: DFS, BFS
  • Shortest Path: Dijkstra, Bellman Ford
  • Minimum Spanning Tree: Prim, Kruskal
  • Strongly Connected Components: Tarjan, Kosaraju
  • Maximum Flow: Ford Fulkerson, Edmonds Karp

These algorithms can be used to solve various problems such as finding the shortest path between two nodes, detecting cycles in a graph, and identifying connected components.

Types of Graphs

There are several different types of graphs, each with their own characteristics and uses. Some common types of graphs include:

  • Undirected Graph: An undirected graph is a collection of nodes and edges where the edges have no direction. This means that the edges can be traversed in both directions, and there is no distinction between the "start" and "end" of an edge.

  • Directed Graph: A directed graph is a collection of nodes and edges where the edges have a direction. This means that the edges can only be traversed in one direction, and there is a distinction between the "start" and "end" of an edge.

  • Weighted Graph: A weighted graph assigns a weight or cost to each edge, which can represent the distance or cost of traversing that edge. This can be useful for modeling systems where the cost of traversing an edge is not constant, such as transportation networks.

  • Unweighted Graph: An unweighted graph does not assign any weight to its edges. This can be useful for modeling systems where the cost of traversing an edge is constant, such as a social network.

  • Simple Graph: A simple graph has no parallel edges or self-loops, meaning that there can be at most one edge between any two nodes, and a node cannot have an edge connecting it to itself.

  • Multigraph: A multigraph can have multiple edges between the same pair of nodes. This can be useful for modeling systems where there are multiple relationships between the same pair of entities, such as a social network where two people can have multiple types of relationships.

  • Cyclic Graph: A graph is said to be cyclic if it contains a cycle, which is a closed path that starts and ends at the same vertex.

  • Acyclic Graph: A graph is said to be acyclic if it does not contain any cycles, also known as a DAG(Directed Acyclic Graph).

  • Connected Graph: A graph is said to be connected if there is a path between any two vertices, meaning that every vertex is reachable from every other vertex.

  • Disconnected Graph: A graph is said to be disconnected if there is no path between some of the vertices, meaning that there are multiple connected components.

These are some of the common types of graphs, but there are many other variations and subtypes as well. The choice of graph type will depend on the specific problem or application, as well as the characteristics of the data.

Example of Graphs

Graphs can be implemented in various programming languages, and the specific implementation will depend on the language and the library or framework being used. Here are a few examples of how to create and work with a simple graph in different programming languages:


# Python: The popular library NetworkX can be used to create and work with graphs in Python. Here's an example of how to create an undirected, unweighted graph with three nodes and three edges:    

import networkx as nx 

G = nx.Graph() 
G.add_nodes_from([1, 2, 3]) 
G.add_edges_from([(1, 2), (2, 3), (3, 1)])

Applications of Graphs

Graphs are a data structure that consists of a set of vertices (or nodes) and edges that connect them. Some common applications of graphs include:

  1. Network analysis: Graphs are used to represent and analyze networks, such as social networks, transportation networks, and communication networks.

  2. Computer science: Graphs are used in computer science to represent problems like shortest path, maximum flow, and minimum spanning tree.

  3. Machine learning: Graphs are used in machine learning to represent data in a structured way, such as representing images, text, and other types of data.

  4. Maps and location-based services: Graphs are used to represent geographical information, such as roads and buildings, and can be used to power map-based applications and location-based services.

  5. Modeling relationships: Graphs can be used to represent and analyze relationships between different entities, such as in bioinformatics, chemistry, and social science.

  6. Web crawlers: Graphs are used in web crawlers to navigate and index the web, by representing links between webpages as edges.

  7. Game AI: Graphs are used in game AI to represent game levels, character interactions, and in pathfinding and navigation.

  8. Recommendation systems: Graphs are used in recommendation systems to represent the relationships and interactions between users, products, and other entities, to make personalized recommendations.

Time and Space Complexity of Graphs

The time and space complexity of a graph algorithm depends on the specific algorithm and the characteristics of the input graph. Here are a few examples of the time and space complexity of some common graph algorithms:

  • Breadth-First Search (BFS): The time complexity of BFS is O(V+E) where V is the number of vertices and E is the number of edges. The space complexity is O(V)

  • Depth-First Search (DFS): The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The space complexity is O(V)

  • Dijkstra's Shortest Path: The time complexity of Dijkstra's shortest path algorithm is O((V+E) log V) where V is the number of vertices and E is the number of edges. This is because the algorithm uses a priority queue to efficiently find the next vertex to visit. The space complexity is O(V)

  • A* algorithm : The time complexity of A* algorithm is O(E + V log V) and the space complexity is O(V)

  • Bellman-Ford Shortest Path: The time complexity of Bellman-Ford algorithm is O(VE) where V is the number of vertices and E is the number of edges. The space complexity is O(V)

  • Kruskal's Minimum Spanning Tree: The time complexity of Kruskal's algorithm is O(E log E) where E is the number of edges. The space complexity is O(E + V)

  • Prim's Minimum Spanning Tree: The time complexity of Prim's algorithm is O(E log V) where V is the number of vertices and E is the number of edges. The space complexity is O(V)

  • Ford-Fulkerson Maximum Flow: The time complexity of Ford-Fulkerson algorithm is O(max_flow * E) where E is the number of edges. The space complexity is O(E + V)

It's important to note that these complexities are for the worst-case scenarios, in most cases the actual running time is much less than the worst-case time complexity. It also important to note that the complexities don't take into account the time and space complexity of the data structure used to represent the graph.

It's also important to consider the size of the graph before choosing a specific algorithm, if the graph is dense and have high number of edges then O(V^2) or O(VE) complexity algorithm might work faster than O(Elog V) or O(Elog E) complexity algorithm, but in case of sparse graph, O(Elog V) or O(E*log E) complexity algorithms will perform better.

Advantages and Disadvantages of Graphs

Advantages of graphs as a data structure:

  1. Flexibility: Graphs can be used to represent a wide variety of data structures, from simple relationships between objects to more complex structures like networks.

  2. Hierarchical organization: Graphs provide a natural way to organize data in a hierarchical manner, making it easy to understand the relationships between elements.

  3. Efficient representation of relationships: Graphs can efficiently represent the relationships between different entities, making it easy to analyze and understand the connections between them.

  4. Scalability: Graphs are highly scalable and can handle large amounts of data.

  5. Versatile: Graphs can be used in a wide variety of domains, such as computer science, transportation, social networks, and many others.

Disadvantages of graphs as a data structure:

  1. Complexity: Graphs can be more complex to implement and understand than other data structures, making them more difficult to work with.

  2. Limited flexibility: Graphs are not always the best data structure for certain types of problems. For example, they may not be the best choice for a data set that is constantly changing or one that needs to be sorted in a specific order.

  3. Space complexity: Storing graphs require more memory than other data structures, especially when the number of edges is large.

  4. Time complexity: Some graph algorithms like Dijkstra's shortest path algorithm or Prim's minimum spanning tree algorithm can have a high time complexity.

  5. Not cache-friendly: Graphs are not always cache friendly as they tend to have a high degree of spatial locality.