Scribd
Upload
67 views3 pages

Daa Week 6

This lab manual provides instructions and examples for analyzing algorithms on graphs. It explains that graphs will be represented using adjacency matrices, with 1s indicating edges and 0s indicating no edge. For weighted graphs, the adjacency matrix will contain edge weights instead of 1s. It then outlines 3 problems to solve for Week 6: 1) check if a path exists between 2 vertices in a graph, 2) check if a graph is bipartite, and 3) check if a directed graph contains a cycle. The input and output formats are specified for each problem.

Uploaded by

Anushka Rawat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
67 views3 pages

Daa Week 6

This lab manual provides instructions and examples for analyzing algorithms on graphs. It explains that graphs will be represented using adjacency matrices, with 1s indicating edges and 0s indicating no edge. For weighted graphs, the adjacency matrix will contain edge weights instead of 1s. It then outlines 3 problems to solve for Week 6: 1) check if a path exists between 2 vertices in a graph, 2) check if a graph is bipartite, and 3) check if a directed graph contains a cycle. The input and output formats are specified for each problem.

Uploaded by

Anushka Rawat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Lab Manual

Course Title : Design and Analysis of Algorithms

Note: Consider the following input format in the form of adjacency matrix for
graph based questions (directed/undirected/weighted/unweighted graph).

Input Format: Consider example of below given graph in Figure (a).


A boolean matrix AdjM of size V X V is defined to represent edges of the graph. Each
edge of graph is represented by two vertices (start vertex u, end vertex v). That means,
an edge from u to v is represented by making AdjM[u,v] and AdjM[v,u] = 1. If there is
no edge between u and v then it is represented by making AdjM[u,v] = 0. Adjacency
matrix representation of below given graph is shown in Figure (b). Hence edges are
taken in the form of adjacency matrix from input. In case of weighted graph, an edge
from u to v having weight w is represented by making AdjM[u,v] and AdjM[v,u] = w.

Input format for this graph is shown in Figure (c).


First input line will obtain number of vertices V present in graph.
After first line, V input lines are obtained. For each line i in V, it contains V space
separated boolean integers representing whether an edge is present between i and all
V.

Figure (a) Figure (b) Figure


(c)

Week 6:
I. Given a (directed/undirected) graph, design an algorithm and implement it using a program to
find if a path exists between two given vertices or not. (Hint: use DFS)

Input Format:
Input will be the graph in the form of adjacency matrix or adjacency list.
Source vertex number and destination vertex number is also provided as an input.

Output Format:
Output will be 'Yes Path Exists' if path exists, otherwise print 'No Such Path Exists'.

Sample I/O Problem I:

II. Given a graph, design an algorithm and implement it using a program to find if a graph is
bipartite or not. (Hint: use BFS)

Input Format:
Input will be the graph in the form of adjacency matrix or adjacency list.

Output Format:
Output will be 'Yes Bipartite' if graph is bipartite, otherwise print 'Not Bipartite'.

Sample I/O Problem II:

III. Given a directed graph, design an algorithm and implement it using a program to find whether
cycle exists in the graph or not.

Input Format:
Input will be the graph in the form of adjacency matrix or adjacency list.

Output Format:
Output will be 'Yes Cycle Exists' if cycle exists otherwise print 'No Cycle Exists'.

Sample I/O Problem III:

You might also like