Question

DepthFirstSearch operation can be implemented by using recession. Write the algorithm for a recursive depth first search. Then test the algorithm to verify the results are valid in a driver program

These are the values and weights for the graph

Current After Weight

A B 80

B E 153

E F. 67

F G 67

E D 98

F D 89

D C 78

C F 74

B B 79

Answer 1

Since you have not mentioned the language of your preference, I am providing the code in Java.

CODE

import java.util.*;

class Edge implements Comparable<Edge> {
    private char src, dest;
    private int weight;

    public Edge(char src, char dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    public char getSrc() {
        return src;
    }

    public void setSrc(char src) {
        this.src = src;
    }

    public char getDest() {
        return dest;
    }

    public void setDest(char dest) {
        this.dest = dest;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "src=" + src +
                ", dest=" + dest +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Edge o) {
        if (this.weight > o.getWeight()) {
            return 1;
        } else if (this.weight < o.getWeight()) {
            return -1;
        } else {
            return 0;
        }
    }
}

class Graph {
    private int V;
    private LinkedHashMap<Character, LinkedList<Edge>> adj;

    Graph(int v) {
        V = v;
        adj = new LinkedHashMap<>();
    }

    void addEdge(char src, char dest, int weight) {
        if (!adj.containsKey(src)) {
            adj.put(src, new LinkedList<>());
        }
        adj.get(src).add(new Edge(src, dest, weight));
    }

    void sortMap() {
        for (Map.Entry<Character, LinkedList<Edge>> entry : adj.entrySet()) {
            Collections.sort(entry.getValue());
        }
    }

    void DFSUtil(char v, Map<Character, Boolean> visited) {
        visited.put(v, true);
        System.out.print(v + " ");

        if (adj.get(v) != null) {
            Iterator<Edge> i = adj.get(v).iterator();
            while (i.hasNext()) {
                Edge n = i.next();
                if (!visited.containsKey(n.getDest()))
                    DFSUtil(n.getDest(), visited);
            }
        }
    }

    void DFS(char v) {
        Map<Character, Boolean> visited = new HashMap<>();
        DFSUtil(v, visited);
    }
}

public class Main {


    public static void main(String[] args) {
        Graph g = new Graph(7);

        g.addEdge('A', 'B', 80);
        g.addEdge('B', 'E', 153);
        g.addEdge('E', 'F', 67);
        g.addEdge('F', 'G', 67);
        g.addEdge('E', 'D', 98);
        g.addEdge('F', 'D', 89);
        g.addEdge('D', 'C', 78);
        g.addEdge('C', 'F', 74);
        g.addEdge('B', 'B', 79);

        System.out.println("Following is Depth First Traversal (starting from vertex A): ");

        g.DFS('A');
    }
}

OUTPUT

Following is Depth First Traversal (starting from vertex A):
A B E F G D C
Process finished with exit code 0