Question

Using Java Code. Thankyou.

The file has 1 edge per line in the format (origin,destination)

- Assume the graph is not directional

- (2,5) means there is a path from 2 to 5 and from 5-2

For the Lab write the following code.

1) Write a function to find all adjacent vertices to a node N ( find_adjacent(n))

2) Write a function that will return true or false that an edge exists ( edge_exists(origin,destination))

3) Print out all Vertices using BFS

Bonus +5

Print out all Vertices using DFS

Bonus +5

Write a function to print out the shortest path between two vertices (shortest_path(origin,destination))

Bonus +5

Find all Cliques in the graph and print them out

Answer 1

Answer 1

import java.util.LinkedList;
  
public class GFG
{
// A user define class to represent a graph.
// A graph is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
static class Graph
{
int V;
LinkedList<Integer> find_adjacent[];
  
// constructor
Graph(int V)
{
this.V = V;
  
// define the size of array as
// number of vertices
find_adjacent = new LinkedList[V];
  
// Create a new list for each vertex
// such that adjacent nodes can be stored
for(int n = 0; n < V ;n++){
find_adjacent[n] = new LinkedList<>();
}
}
}
  
// Adds an edge to an undirected graph
static void addEdge(Graph graph, int src, int dest)
{
// Add an edge from src to dest.
graph.find_adjacent[src].add(dest);
  
// Since graph is undirected, add an edge from dest
// to src also
graph.find_adjacent[dest].add(src);
}

// A utility function to print the adjacency list
// representation of graph
static void printGraph(Graph graph)
{
for(int v = 0; v < graph.V; v++)
{
System.out.println("Adjacency list of vertex "+ v);
System.out.print("head");
for(Integer pCrawl: graph.find_adjacent[v]){
System.out.print(" -> "+pCrawl);
}
System.out.println("\n");
}
}

// Driver program to test above functions
public static void main(String args[])
{
// create the graph given in above figure
int V = 5;
Graph graph = new Graph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);

// print the adjacency list representation of
// the above graph
printGraph(graph);
}
}

Answer 2

import java.io.*;
import java.util.*;
import java.util.LinkedList;
  
// This class represents a directed graph using adjacency list
// representation
public class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency List
  
//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
  
//Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }
  
//prints BFS traversal from a given source s
Boolean edge_exists(int s, int d)
{
LinkedList<Integer>temp;
  
// Mark all the vertices as not visited(By default set
// as false)
boolean visited[] = new boolean[V];
  
// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
  
// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);
  
// 'i' will be used to get all adjacent vertices of a vertex
Iterator<Integer> i;
while (queue.size()!=0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
  
int n;
i = adj[s].listIterator();
  
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
while (i.hasNext())
{
n = i.next();
  
// If this adjacent node is the destination node,
// then return true
if (n==d)
return true;
  
// Else, continue to do BFS
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
  
// If BFS is complete without visited d
return false;
}
  
// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
  
int u = 1;
int v = 3;
if (g.edge_exists(u, v))
System.out.println("There is a path from " + u +" to " + v);
else
System.out.println("There is no path from " + u +" to " + v);

}

Answer 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Breadth_First_Search {
// Function to perform breadth first search
static void breadth_First_Search(int[][] origin, int source){
boolean[] visited = new boolean[origin.length];
visited[source-1] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(source);
System.out.println("The breadth first order is");
while(!queue.isEmpty()){
System.out.println(queue.peek());
int x = queue.poll();
int i;
for(i=0; i<origin.length;i++){
if(origin[x-1][i] == 1 && visited[i] == false){
queue.add(i+1);
visited[i] = true;
}
}
}
}
// Function to read user input
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int vertices;
System.out.println("Enter the number of vertices in the graph");
try{
vertices = Integer.parseInt(br.readLine());
}catch(IOException e){
System.out.println("An error occurred");
return;
}
int[][] origin = new int[vertices][vertices];
System.out.println("Enter the adjacency matrix");
int i,j;
for(i=0; i<vertices; i++){
for(j=0; j<vertices; j++){
try{
origin[i][j] = Integer.parseInt(br.readLine());
}catch (IOException e){
System.out.println("An error occurred");
}
}
}
int source;
System.out.println("Enter the source vertex");
try{
source = Integer.parseInt(br.readLine());
}catch(IOException e){
System.out.println("An error occurred");
return;
}
breadthFirstSearch(origin,source);
}
}