4
$\begingroup$

This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing I have noticed, as I have used both Skiena's Algorithm Design Manual and CLRS is that, at least in the pseuducode in CLRS, several of them have a similar structure: do something with all the vertices of the graph, do something special to the root or the first vertex (for example, set its cost to 0, as in Prim), then create a queue or a priority queue, insert all the vertices and in a loop extract one by one, check some condition and do something to their adjacency list. Why do they follow such a structure? Some of the algorithms in CLRS are similar:

BFS in CLRS DFS in CLRS Prim's algorithm in CLRS

PS: as I mentioned, this is my first post, not only in CS, but in all the Stackoverflow network. Any suggestion or improvement on question posting is greatly appreciated.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

When we want to design an algorithm, we mainly consider how our data is organized. When we model a problem with graph for example, the things we could do are restricted to this specified model. For example we visit a vertex for the first time, we visit it’s neighboors, we may want to mark a vertex with specific color and so on.

But this is not necessary, we may solve problems in very strange ways. Take this example when we want to check if there does not exist a path from $u$ to $v$ in the input graph with $n$ number of vertices which path lengths has a size of $O(n)$ and we are limited to logarithmic space, the algorithm which introduced by Immerman-Szelepcśenyi is not trivial at all.

What i mean is for trivial algorithms, combination of basic operations seems similar but this is not necessary for non-trivial algorithms. we may combine basic operations in very strange way to solve a problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer. So you mean that in the adjacency list representation, which is the one used in the above algorithms, basically we can only traverse it as they do, and we are limited to be updateing a node and/or processing its adjacency list? $\endgroup$
    – George1917
    Commented Aug 19, 2021 at 15:34
  • $\begingroup$ @George191 7 A graph is a representation of finite set of objects and their relations between those objects. A Graph is represented in various data structures such as adjacency list, adjacency matrix , incidence matrix and so on. What i mean is for trivial algorithms, combination of basic operations seems similar but this is not necessary for non-trivial algorithms. we may combine basic operations in very strange way to solve a problem. $\endgroup$
    – Omid Yaghoubi
    Commented Aug 19, 2021 at 15:50
1
$\begingroup$

One way to see the similarities between BFS and DFS is to consider them as the same algorithm (or perhaps some sort of "meta algorithm"), but using a different underlying data-structure: BFS uses a queue, while DFS uses a stack. A nice illustration of that is this figure from "IDEA Instructions":

GRÅPH SKÄN from IDEA Instructions

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.