What Is Undirected Graph in Data Structure?

//

Angela Bailey

An undirected graph is a fundamental data structure in computer science and mathematics. It is a collection of vertices (also known as nodes) connected by edges. Unlike a directed graph, the edges in an undirected graph have no specific direction, meaning that they can be traversed in both directions.

Vertices and Edges
In an undirected graph, vertices represent entities or objects, while edges represent the relationships between these entities. Each edge connects two vertices and denotes that there is a connection or interaction between them. The absence of a direction on the edges implies that the relationship between the vertices is symmetric.

Example:
Consider a simple undirected graph representing a social network. The vertices could represent individuals, and the edges could represent friendships between these individuals. Since friendships are usually mutual, an undirected graph accurately models this scenario.

Adjacency Matrix
One way to represent an undirected graph is through an adjacency matrix. An adjacency matrix is a square matrix where each row and column correspond to a vertex in the graph. The elements of the matrix indicate whether there is an edge between two vertices.

Example:
Let’s consider a small undirected graph with four vertices labeled A, B, C, and D. The adjacency matrix for this graph would be as follows:

    A   B   C   D
A   0   1   1   0
B   1   0   0   1
C   1   0   0   1
D   0   1   1   0

This matrix tells us that there is an edge between A and B (indicated by “1” at row A, column B), as well as between A and C, B and D, and C and D.

Adjacency List
Another way to represent an undirected graph is through an adjacency list. In this representation, each vertex is associated with a list of its adjacent vertices. The adjacency list efficiently captures the connections between vertices.

Example:
For the same graph as before, the adjacency list representation would be:

  • A: B, C
  • B: A, D
  • C: A, D
  • D: B, C

This list tells us that vertex A is adjacent to vertices B and C, vertex B is adjacent to vertices A and D, and so on.

Applications of Undirected Graphs
Undirected graphs have various applications in computer science and beyond. Some common use cases include:

Social Networks:

Undirected graphs are used to model connections between individuals in social networks like Facebook or LinkedIn.

Web Page Ranking:

Search engine algorithms like Google’s PageRank use undirected graphs to determine the importance of web pages based on their links.

Molecular Chemistry:

In chemistry, undirected graphs are used to represent molecules and their bonds.

Transportation Networks:

Undirected graphs model road networks or flight routes between cities in transportation systems.

Conclusion
Undirected graphs play a crucial role in representing relationships between entities or objects. They provide a flexible and intuitive way to analyze connections in various domains. Whether you’re exploring social networks or optimizing web page rankings, understanding undirected graphs is essential for solving complex problems.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy