سلام دوستان ممکنه این تست را برام توضیح بدید:
پیچیدگی زمانی الگوریتم dfs برای دو حالت زیر:
الف )نمایش گراف با ماتریس مجاورت
ب) نمایش گراف با لیست مجاورت
جوابش می شه:
الف: ۲^|V|
ب:|E|
می شه لطفا برام توضیح بدید.
خوب توی ماتریس مجاورت V^2 تا درایه داریم که توی این الگوریتم همه باید بررسی بشوند چون یه سری از درایه های ماتریس صفر هستند ولی به هر حال عضوی از ماتریس هستند و بررسی میشوند و در پیچیدگی لحاظ میشه ولی توی لیست مجاورت فقط یالهایی که وجود دارند هستند یعنی E .