Graphs

Graphs can be represented in various ways in code, depending on the requirements and use cases. Each representation has its own advantages and disadvantages, and understanding them is essential for efficiently working with graphs.

One commonly used representation of a graph is the adjacency matrix. In this representation, a matrix of size V x V is used, where V is the number of vertices in the graph. The value at matrix position (i, j) represents the weight of the edge between vertices i and j. If there is no edge between the vertices, the value at that position is usually set to infinity or a special value to indicate the absence of an edge.

// Adjacency Matrix representation of a graph

class Main {
    public static void main(String[] args) {
        int V = 5; // Number of vertices
        int[][] adjacencyMatrix = new int[V][V];

        // Add edges
        adjacencyMatrix[0][1] = 1;
        adjacencyMatrix[1][2] = 1;
        adjacencyMatrix[2][3] = 1;
        adjacencyMatrix[3][4] = 1;
        adjacencyMatrix[4][0] = 1;

        // Print adjacency matrix
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Another common representation is the adjacency list. In this representation, each vertex in the graph is associated with a list of its adjacent vertices. This representation is more memory-efficient when the graph has a large number of vertices but relatively fewer edges.

// Adjacency List representation of a graph

class Graph {
    int V;
    ArrayList<ArrayList<Integer>> adjacencyList;

    public Graph(int v) {
        V = v;
        adjacencyList = new ArrayList<>(V);

        for (int i = 0; i < V; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjacencyList.get(src).add(dest);
        adjacencyList.get(dest).add(src); // Uncomment this line for undirected graph
    }

    public void printGraph() {
        for (int i = 0; i < V; i++) {
            System.out.print(i + " -> ");
            for (int j = 0; j < adjacencyList.get(i).size(); j++) {
                System.out.print(adjacencyList.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }
}

// Usage

class Main {
    public static void main(String[] args) {
        int V = 5; // Number of vertices
        Graph graph = new Graph(V);

        // Add edges
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(4, 0);

        // Print adjacency list
        graph.printGraph();
    }
}

These are just a few examples of how graphs can be represented in code. Depending on the specific use case, other representations such as edge list, incidence matrix, or adjacency set might be more suitable and efficient.

Which representation of a graph is more memory-efficient when the graph has a large number of vertices but relatively fewer edges?

Graph traversal algorithms are used to explore or visit all the vertices of a graph. They are essential for understanding the structure and connectivity of a graph. Two commonly used graph traversal algorithms are depth-first search (DFS) and breadth-first search (BFS).

Depth-First Search (DFS):

In DFS, we start at a given vertex (usually called the source vertex) and explore as far as possible along each branch before backtracking. This means that we go depth-first, exploring vertices in the order they are encountered until we reach a dead end, and then backtrack to the previous vertex and explore another branch.

DFS can be implemented using either recursion or an explicit stack. Here is a recursive implementation of DFS in Java: ```java public class DFS { private boolean[] visited; private Graph graph;

public DFS(Graph g) {
    graph = g;
    visited = new boolean[graph.getVertices()];
}

public void traverse(int source) {
    visited[source] = true;
    System.out.print(source + " ");

    for (int neighbor : graph.getNeighbors(source)) {
        if (!visited[neighbor]) {
            traverse(neighbor);
        }
    }
}

public static void main(String[] args) {
    int V = 6; // Number of vertices
    Graph graph = new Graph(V);

    // Add edges
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(3, 5);

    DFS dfs = new DFS(graph);
    dfs.traverse(0);
}

} ```

Breadth-First Search (BFS):

In BFS, we explore all the vertices at the current level before moving to the next level. This means that we visit all the neighbors of a vertex before visiting the neighbors' neighbors.

BFS can be implemented using a queue data structure. Here is an implementation of BFS in Java: ```java import java.util.LinkedList; import java.util.Queue;

public class BFS { private boolean[] visited; private Graph graph;

public BFS(Graph g) {
    graph = g;
    visited = new boolean[graph.getVertices()];
}

public void traverse(int source) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(source);
    visited[source] = true;

    while (!queue.isEmpty()) {
        int vertex = queue.poll();
        System.out.print(vertex + " ");

        for (int neighbor : graph.getNeighbors(vertex)) {
            if (!visited[neighbor]) {
                queue.offer(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

public static void main(String[] args) {
    int V = 6; // Number of vertices
    Graph graph = new Graph(V);

    // Add edges
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(3, 5);

    BFS bfs = new BFS(graph);
    bfs.traverse(0);
}

} ```

Breadth-first search is a graph traversal algorithm that visits all of the direct neighbors of a node before visiting any of its descendants.

Dijkstra's algorithm is a well-known algorithm used to find the shortest path between two vertices in a weighted graph. It guarantees the shortest path from a source vertex to all other vertices. This algorithm is widely used in various applications, such as GPS navigation systems, network routing protocols, and airline travel planning.

The basic idea behind Dijkstra's algorithm is to continuously update the shortest path distances from the source vertex to all other vertices in the graph. It maintains a priority queue of vertices to explore, sorted by their current shortest distance from the source. At each step, it selects the vertex with the smallest current distance and relaxes the edges connected to it.

Let's take a look at an implementation of Dijkstra's algorithm in Java:

class Graph {
    private int V;
    private int[][] graph;

    public Graph(int V) {
        this.V = V;
        graph = new int[V][V];
    }

    public void addEdge(int src, int dest, int weight) {
        graph[src][dest] = weight;
    }

    public void dijkstra(int source) {
        // Initialize distance array
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // Initialize visited array
        boolean[] visited = new boolean[V];

        // Initialize priority queue
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
        pq.offer(source);

        while (!pq.isEmpty()) {
            int vertex = pq.poll();
            visited[vertex] = true;

            // Relax edges connected to the current vertex
            for (int neighbor = 0; neighbor < V; neighbor++) {
                int weight = graph[vertex][neighbor];

                if (weight > 0 && !visited[neighbor]) {
                    int newDistance = dist[vertex] + weight;

                    if (newDistance < dist[neighbor]) {
                        // Update shortest distance to neighbor
                        dist[neighbor] = newDistance;

                        // Add neighbor to priority queue
                        pq.offer(neighbor);
                    }
                }
            }
        }

        // Print the shortest distances from the source vertex
        System.out.println(Arrays.toString(dist));
    }

    public static void main(String[] args) {
        int V = 5; // Number of vertices
        Graph graph = new Graph(V);

        // Add edges
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 3, 1);
        graph.addEdge(2, 1, 2);
        graph.addEdge(2, 3, 5);
        graph.addEdge(3, 4, 3);

        graph.dijkstra(0);
    }
}

```java
import java.util.Arrays;
import java.util.PriorityQueue;

class Graph {
    private int V;
    private int[][] graph;

    public Graph(int V) {
        this.V = V;
        graph = new int[V][V];
    }

    public void addEdge(int src, int dest, int weight) {
        graph[src][dest] = weight;
    }

    public void dijkstra(int source) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);

        boolean[] visited = new boolean[V];

        dist[source] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
        pq.offer(source);

        while (!pq.isEmpty()) {
            int vertex = pq.poll();
            visited[vertex] = true;

            for (int neighbor = 0; neighbor < V; neighbor++) {
                int weight = graph[vertex][neighbor];

                if (weight > 0 && !visited[neighbor]) {
                    int newDistance = dist[vertex] + weight;

                    if (newDistance < dist[neighbor]) {
                        dist[neighbor] = newDistance;
                        pq.offer(neighbor);
                    }
                }
            }
        }

        System.out.println(Arrays.toString(dist));
    }

    public static void main(String[] args) {
        int V = 9; // Number of vertices
        Graph graph = new Graph(V);
        
        // Add edges
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 7, 8);
        graph.addEdge(1, 2, 8);
        graph.addEdge(1, 7, 11);
        graph.addEdge(2, 3, 7);
        graph.addEdge(2, 5, 4);
        graph.addEdge(2, 8, 2);
        graph.addEdge(3, 4, 9);
        graph.addEdge(3, 5, 14);
        graph.addEdge(4, 5, 10);
        graph.addEdge(5, 6, 2);
        graph.addEdge(6, 7, 1);
        graph.addEdge(6, 8, 6);
        graph.addEdge(7, 8, 7);
        
        graph.dijkstra(0);
    }
}
```

Which data structure is commonly used in the implementation of Dijkstra's algorithm?

REPLACE_WITH_YOUR_CONTENT

```java
REPLACE_WITH_YOUR_JAVA_CODE
```

Which algorithm is used to find the minimum spanning tree of a graph?

Generating complete for this lesson!