Embedded Files
Algorithm BFS
Input: Graph represented by the adjacency matrix a[][], number of vertices n, starting vertex v
Output: Visited nodes using BFS
For i = 0 to n - 1
q[i] = 0
visited[i] = 0
End For
Output "Enter the graph data in matrix:"
For i = 0 to n - 1
For j = 0 to n - 1
Read a[i][j]
End For
End For
Output "Starting Vertex:"
Read v
BFS(v)
Output "The nodes which are reachable are"
For i = 0 to n - 1
If visited[i] == 0
Output i, "is not visited"
Else
Output i, "is visited"
End If
End For
Return 0
End Algorithm
Algorithm BFS(v)
Input: Starting vertex v
Output: Visited nodes using BFS
f = 0
r = -1
For i = 0 to n - 1
If a[v][i] and not visited[i]
q[++r] = i
visited[q[f]] = 1
BFS(q[f++])
End If
End For
End Algorithm
Algorithm DFS
Input: Number of vertices n, Adjacency matrix cost[][], Arrays s[], i, j, connected, flag
Output: Whether the graph is connected or not
Output "Enter the number of vertices"
Read n
Output "Enter the Adjacency matrix :"
For i = 0 to n - 1
For j = 0 to n - 1
Read cost[i][j]
End For
End For
connected = 0
For j = 0 to n - 1
For i = 0 to n - 1
s[i] = 0
End For
DFS(n, cost, j, s)
flag = 0
For i = 0 to n - 1
If s[i] == 0
flag = 1
End If
End For
If flag == 0
connected = 1
End If
End For
If connected == 1
Output "Graph is Connected"
Else
Output "Graph is not Connected"
End If
Return 0
End Algorithm
// Function to perform Depth-First Search
Algorithm DFS(n, cost[][], u, s[])
Input: Number of vertices n, Adjacency matrix cost[][], Starting vertex u, Array s[] to track visited vertices
Output: Visits all vertices reachable from u
s[u] = 1
For v = 0 to n - 1
If cost[u][v] == 1 AND s[v] == 0
DFS(n, cost, v, s)
End If
End For
End Algorithm
Page updated
Google Sites
Report abuse