Graphs

In the world of data structures and algorithms, a graph is a non-linear data structure that consists of a set of vertices (also called nodes) connected by edges. Graphs are widely used in many applications, including computer networks, social networks, and recommendation systems.

Basic Terminology

To understand graphs, it's important to be familiar with some basic terminology:

1. Vertex/Node: Each element in a graph is called a vertex or a node. A vertex can have a value associated with it.

2. Edge: An edge represents a connection or relationship between two vertices. It can be either directed (one-way) or undirected (two-way).

3. Degree: The degree of a vertex is the number of edges connected to it.

4. Path: A path is a sequence of vertices where each adjacent pair is connected by an edge.

Graph Traversal

There are two common ways to traverse or visit the vertices in a graph:

• Depth-First Traversal (DFS): In DFS, we start from a vertex and go as far as we can along each branch before backtracking. This traversal uses a stack to remember the next vertex to visit.

• Breadth-First Traversal (BFS): In BFS, we start from a vertex and visit all its neighbors first before moving on to their neighbors. This traversal uses a queue to remember the next vertices to visit.

Java Example

Let's take a look at an example of creating and traversing a graph using the Depth-First Traversal (DFS) algorithm:

1{{code}}

In this example, we create a graph with 4 vertices and add some edges between them. Then, we perform a DFS traversal starting from vertex 2 and print the visited vertices.

xxxxxxxxxx

}

public class Graph {

  private int V;

  private LinkedList<Integer>[] adj;

​

  public Graph(int v) {

    V = v;

    adj = new LinkedList[v];

    for (int i = 0; i < v; ++i) {

      adj[i] = new LinkedList();

    }

  }

​

  void addEdge(int v, int w) {

    adj[v].add(w);

    adj[w].add(v);

  }

​

  void DFSUtil(int v, boolean[] visited) {

    visited[v] = true;

    System.out.print(v + " ");

​

    Iterator<Integer> i = adj[v].listIterator();

    while (i.hasNext()) {

      int n = i.next();

      if (!visited[n]) {

        DFSUtil(n, visited);

      }

    }

  }