#BFS and DFS

1 messages · Page 1 of 1 (latest)

meager timber
#

Can someone help with with this? I have no idea what I am supposed to do

Screenshot_2024-12-17_at_01.21.34.png
lapis heraldBOT
#

<@&987246746478460948> please have a look, thanks.

blissful jacinth
#

whats unclear to u? do u know what a spanning tree is? adjacency matrix? graph? bfs? dfs?

meager timber
#

I know what adjacency amtrix is

#

I can draw tree with this matrix

#

but

#

what am I supposed to do after that

blissful jacinth
#

ur not supposed to draw the graph

#

although if u can do that as a first step, it would be helpful

meager timber
#

what is spanning tree then I dont know

blissful jacinth
#

ur task is to draw the spanning tree that bfs/dfs would form while being executed on that graph

#

do u know bfs and dfs?

meager timber
#

breadth first search and depth first search

blissful jacinth
#

yeah but do u know how these algos work?

meager timber
#

kinda

blissful jacinth
#

they visit the nodes of the graph in a particular order and that order, if u draw it down, forms a tree

#

that's a spanning tree, as it spans the graph

meager timber
#

wait let me draw graoh for it

blissful jacinth
#

yes. draw the graph first, that will help u

#

and ull also notice what they mention in part 2

#

the graph isnt connected and ur spanning trees will show that depending on which node u started the bfs/dfs at

#

since it wont span the entire graph, only a subgraph

meager timber
#

something like this?

Screenshot_2024-12-17_at_01.42.17.png
#

more like this

blissful jacinth
#

is that the graph? why the two colors?

meager timber
#

nah I am wrong

#

wait let me do it again

frank girder
meager timber
#

on what?

blissful jacinth
#

let's first draw the graph itself

#

not the spanning trees or bfs/dfs stuff

#

step by step 🙂

#

u got two graphs, A and B

#

id say we focus on A for now

frank girder
#

or did I misunderstood ?

blissful jacinth
#

its an adjacency matrix. it's like OP attempted

frank girder
#

ah

#

my bad

#

so first draw graph

#

then draw algo

blissful jacinth
#

and it's possibly a directed graph

#

so not necessarily bidirectional

meager timber
#

this doesnt look like tree tho

ionic kindle
#

its a graph

blissful jacinth
#

u need the arrowheads, or is it bidirectional?

ionic kindle
blissful jacinth
#

its not supposed to be a tree

meager timber
#

ok

#

well is my graph correct?

blissful jacinth
#

if its bidirectional task 2 would be odd

#

so id say u should do it again

meager timber
#

here is with matrix

Screenshot_2024-12-17_at_01.48.14.png
blissful jacinth
#

but this time take care of the directions

ionic kindle
blissful jacinth
#

yes

#

okay, well. then we continue

meager timber
#

so graph is correct?

blissful jacinth
#

looks like it. but are u sure u understood that part? especially with the directions

meager timber
#

I just understand how to draw graph from matrix

#

I dont understand directions

blissful jacinth
#

like, u cant necessarily say that if 1 is connected to 2 that 2 is also connected to 1

#

if column 1 has a 1 entry in row 2,that doesn't mean that column 2 has a 1 entry in row 1 as well

#

edges have a direction and can't necessarily be traveled in both directions

meager timber
#

ok

blissful jacinth
#

think about one way streets

meager timber
#

so

#

if we go from A to B

#

we can't go back to A?

blissful jacinth
#

not sure what u mean with A and B. but my point is that u just drew ur graph with no arrowheads on ur edges

#

assuming each edge would exist in both directions

#

which isnt necessarily given

ionic kindle
meager timber
blissful jacinth
#

for example

#

only if the matrix is mirrored on the diagonal

ionic kindle
#

at first this is kinda unrelated to adjancency matrices

blissful jacinth
#

u have to understand how to read the adjacency matrix. it defines twice as many edges as u drew, technically

meager timber
#

yes

#

because when I drew it once it jsut reoeated

#

like when I connected 5 to 8

#

I didn't connect 8 to 5 again

blissful jacinth
#

yeah exactly. but technically these are two different edges

#

with direction

#

one from 5 to 8 and a second from 8 to 5

#

and they are directional

#

ur adjacency matrix has it so that all edges are doubled, but thats not the case for all adjacency matrices necessarily

#

just saying

meager timber
#

ok

blissful jacinth
#

okay, so far so good

ionic kindle
#

it not only tells you which nodes are connected, but also how they are connected

blissful jacinth
#

now, pick a node. perhaps node 3. and perform BFS starting from it

#

step by step

#

take note of the order in which it visits/explores notes

meager timber
#

ok let me try

blissful jacinth
#

draw it as u do bfs in ur head

#

for example ull start with node 3. next it will put nodes 4 and 8 into its queue

#

in the next step of bfs it might poll node 4

#

node 4 has no new neighbors, so that branch ends

#

bfs polls 8 next from the queue

meager timber
blissful jacinth
#

and then adds nodes 5, 6 and 7 to the queue

meager timber
#

I started from node 3 and finished on node 2

blissful jacinth
#

that edge from 5 to 1 shouldnt be purple

meager timber
#

new color?

blissful jacinth
#

yes. take note of the order

#

its nodes 4 and 8 first

#

if u do bfs

#

then nodes 5, 6 and 7

#

then nodes 1 and 2

meager timber
blissful jacinth
#

yes. now get rid of the black edges and look only at the colored ones

#

and dont forget the arrows on the edges

#

cause this time it's definitely directional

meager timber
blissful jacinth
#

add arrows please

meager timber
#

ok

blissful jacinth
#

now reorganize it so that it visually all goes from top to bottom, i. e. move nodes 5, 6, 7, 1, 2 downwards

meager timber
blissful jacinth
#

yup. now the reorganize step

meager timber
#

3,4

#

3 -> 4
3 -> 8 -> 5 -> 1
3 -> 8 -> 6
3 -> 8 -> 7 -> 2

blissful jacinth
#

nah i mean, change ur picture

ionic kindle
#

do it visually

#

to create a tree

blissful jacinth
#

ull see that what u have here is a tree

#

it becomes obvious after u draw it top to bottom

meager timber
#

yeah this is tree

#

ok

blissful jacinth
#

yeah. so what u have here is a so called spanning tree (rooted at node 3). it spans over the graph

meager timber
blissful jacinth
#

perfect

#

if u root it at a different node it will look completely different

meager timber
#

yeah

blissful jacinth
#

and if u do dfs instead of bfs it will look different as well

meager timber
#

this is how I perform bfs?

blissful jacinth
#

so. they just want u to draw some of these spanning trees rooted at various nodes u can pick at random

#

perhaps pick 2 nodes, do dfs, then bfs. do it on graph A and then on graph B, ull end up with 8 pictures of various spanning trees

#

and that's the first task

meager timber
#

how do I perform dfs? I knew what was bfs but I have no idea about dfs

#

I know it goes very deep

blissful jacinth
#

it differs in the order, thats all

#

bfs uses a FIFO queue for the nodes to visit

#

dfs a LIFO

#

that's all

meager timber
#

stacks?

blissful jacinth
#

so u just perform the same algorithm but with a LIFO in ur head

#

yes, a stack is an example for a lifo queue

lapis heraldBOT
#

Graph traversal can be accomplished easily using BFS or DFS. The algorithms only differ in the order in which nodes are visited: https://i.imgur.com/n9WrkQG.png

The code to accomplish them is identical and only differs in the behavior of the Queue they are based on. BFS uses a FIFO-queue and DFS a LIFO-queue.

Queue<Node> nodesToProcess = ... // depending on BFS or DFS
nodesToProcess.add(rootNode); // add all starting nodes

Set<Node> visitedNodes = new HashSet<>();
while (!nodesToProcess.isEmpty()) {
  // Settle node
  Node currentNode = nodesToProcess.poll();
  if (!visitedNodes.add(currentNode)) {
    continue; // Already visited before
  }

  // Do something with the node
  System.out.println(currentNode); // Replace by whatever you need

  // Relax all outgoing edges
  for (Node neighbor : currentNode.getNeighbors()) {
    nodesToProcess.add(neighbor);
  }
}

To get BFS, use a FIFO-queue:

Queue<Node> nodesToProcess = new ArrayDeque<>();

And for DFS a LIFO-queue:

Queue<Node> nodesToProcess = Collections.asLifoQueue(new ArrayDeque<>());

Thats all, very simple to setup and use.

For directed graphs relax all outgoing edges.
For trees the visitedNodes logic can be dropped, since each node can only have maximally one parent, simplifying the algorithm to just:

Queue<Node> nodesToProcess = ... // depending on BFS or DFS
nodesToProcess.add(rootNode); // add all starting nodes

while (!nodesToProcess.isEmpty()) {
  // Settle node
  Node currentNode = nodesToProcess.poll();

  // Do something with the node
  System.out.println(currentNode); // Replace by whatever you need

  // Relax all outgoing edges
  for (Node child : currentNode.getChildren()) {
    nodesToProcess.add(child);
  }
}
zabuzard • used /tag id: bfs ·
ionic kindle
#

I would visually look at it, though this is for a tree and not a graph

02a68-3911860635.png
meager timber
#

so in bfs when I finished with 2 now when I finish it with 2 again I will start drawing tree with 2?

blissful jacinth
#

do it step by step. start at node 3

#

it adds nodes 4 and 8

#

then it polls node 4

#

so that part is the same

#

node 4 is a leaf, so no new nodes added

#

next is node 8

meager timber
blissful jacinth
#

now it adds nodes 5 6 7.

ionic kindle
blissful jacinth
#

it adds all of them but they are polled in different order now

#

it polls node 5 now, adds nodes 1 next

meager timber
blissful jacinth
#

bfs would now poll node 6

#

but dfs polls node 1

#

so 1 is relaxed before 6

#

but its a leaf, so whatever

ionic kindle
#

sounds wrong to me how you explain it

meager timber
#

i think we are heading to same answer as bfs

blissful jacinth
#

the picture ur drawing isnt right

#

nodes 6 and 7 werent relaxed yet

#

only added to the queue

#

not polled

meager timber
ionic kindle
blissful jacinth
#

the difference between bfs and dfs is that one uses a fifo queue and the other a lifo queue

#

a stack is a queue

#

a lifo queue to be specific

ionic kindle
#

well sure

#

makes it hard to understand though imo

#

whatever wont disrupt this anymore peepo_heart

blissful jacinth
#

either case, the spanning trees formed by both are identical

#

the coloring is different. but the structure is the same

meager timber
#

what am I doing next

blissful jacinth
#

ull end up with the same image

meager timber
#

so what is difference then

blissful jacinth
#

the order in which u explored nodes. so if u color each edge in order, it will be different

meager timber
#

is that it can go back?

blissful jacinth
#

not sure what u mean

meager timber
#

like this

#

and what I got from the picuute other guy send it means we can go back

blissful jacinth
#

technically every edge needs its own color. in both dfs and bfs

#

if u give some the same color that's incorrect

meager timber
#

like this or smth

Screenshot_2024-12-17_at_02.21.44.png
blissful jacinth
#

no. the spanning tree formed by bfs/dfs isnt a representation of how the algo moves

meager timber
blissful jacinth
#

its rather the edges explored by the algo as it walks along

#

u dont need to color anything. that's just for u to understand stuff

meager timber
#

ok

#

so either way we will get same sketch?

blissful jacinth
#

if u want to understand bfs vs dfs its about order

#

but the spanning tree is the same

meager timber
#

ok

blissful jacinth
#

example:

blissful jacinth
#

this is the order in which bfs walks along these edges

#

dfs would be

blissful jacinth
meager timber
#

order is different

blissful jacinth
#

but the spanning tree is in both cases just

meager timber
#

I thought it was much harder

blissful jacinth
#

if u now start the algo on a different node, it will look different

meager timber
#

chatGPT explained it way harder

blissful jacinth
#

for example if u start at node 8 the spanning tree is a different tree

meager timber
#

yeah it will look totally different

blissful jacinth
#

so that's task 1, just drawing a bunch of these

#

task 2 wanta u to think about graphs that aren't connected

#

that is, u can end up in dead ends

#

a graph where some nodes can't reach all other nodes

meager timber
#

this is what it looks like with starting node of 8

Screenshot_2024-12-17_at_02.27.54.png
blissful jacinth
#

an extreme example would be two totally independent mini graphs in one graph that just sit next to each other with no direct connection

#

but less extreme examples would be literal dead ends where a node leads to another node with a one way street with no way out for example

meager timber
#

I think that is the question 2 on my screenshot

blissful jacinth
#

yes

#

so if u have such a graph

#

and now run bfs/dfs on it

meager timber
#

there is no graph here

blissful jacinth
#

depending on which node u start ull notice that the spanning tree wont include all nodes of the graph

meager timber
#

I got smth like this

blissful jacinth
#

it will just include all nodes reachable from the starting node

#

once u understand this connection task 2 is simple

#

it wants u to show that using bfs/dfs and spanning trees will tell u if a graph is connected or not

meager timber
#

is either bfs or dfs considered greedy?

blissful jacinth
#

thats another task though, not task 2. isnt it

meager timber
#

no I am just asking

#

if they are greedy

blissful jacinth
#

no they are not

meager timber
#

I know one dijstra

blissful jacinth
#

dijkstra is the adaption of bfs for weighted graphs

#

its bfs but with a priority queue of tentative distances

#

instead of a regular fifo queue

#

ur supposed to find a minimal spanning tree in that task

#

i. e. a spanning tree that has the least amount of edges

meager timber
#

I am not that advanced to do that task

#

if you can help with 2nd part of my bfs and dfs

blissful jacinth
#

okay. so first make urself a graph that isnt fully connected

#

and then do some bfs with different starting nodes, drawing the spanning trees

meager timber
blissful jacinth
#

ull notice that the spanning trees wont include all nodes of the graph then

#

please dont go for bidirectional/unidirectional graphs all the time

#

that will make this harder

#

make a graph with some well connected cluster plus a one way street instead

meager timber
blissful jacinth
#

again, ur drawing bidirectional graphs

#

dont do that.

#

add arrow heads

meager timber
#

what is bidirectiona; 😭

blissful jacinth
#

make a circle and then a one way street line extending out of it

#

ur making edges that can be walked in both directions

#

edges have a single direction only

#

ur always leaving out the arrowheads

meager timber
#

oh u want me to draw bipartite graph?

blissful jacinth
#

no

#

that's sth else

#

ur drawing lines instead of arrows

#

edges have a direction

#

indicated by an arrow

meager timber
#

so u want me to draw arros instead of edges?

blissful jacinth
#

edges are arrows

#

edges are always one direction

meager timber
blissful jacinth
#

yes

#

better

#

that example isnt will suited though. don't make a fully lonely node

#

draw 5 nodes connected in a circle

meager timber
blissful jacinth
#

connect them to a circle please

meager timber
blissful jacinth
#

that's not a circle, its two one way streets ending in the node on the bottom left

#

change the direction of the edges so it forms a circle please

meager timber
#

oh I get it

blissful jacinth
#

okay. so now we have a connected graph. now we add stuff to it that isnt fully connected

#

add two more nodes on the top which the circle extends to

#

with a one way street

#

think of a dead end street connected to a roundabout

meager timber
blissful jacinth
#

connect it to the circle with a one way street

#

wait...

meager timber
blissful jacinth
meager timber
#

ok

blissful jacinth
#

now, make bfs on node 2

#

then bfs on node 6

#

draw the spanning trees for both

#

and pay attention to the direction of the edges as u do that. bfs cant explore edges backwards

#

edges can only be travelled in one direction

meager timber
#

spanning tree for 6 will be just

6

7

blissful jacinth
#

yes, please draw it as tree

#

yeah okay. i think u got it

meager timber
blissful jacinth
#

so. what u witnessed now is that doing bfs will only give u nodes that are reachable from the start (obviously)

blissful jacinth
meager timber
blissful jacinth
#

so. if u do these bfs/spanning tree things and ull notice that ull get a tree that doesnt include all nodes, it means that the graph isnt fully connected

#

i.e. some nodes cant reach all other nodes

#

task 2 wants u to show this.

now, i lack context of this task and ur course to tell u whether ur supposed to mathematically prove this or perhaps to just make an example (like we just did together) and draw a picture or two

meager timber
#

its Discrete Mathematics for CS

#

I am not supposed to prive anything

#

I have lot of proving things in my course it would say if I had to prove something

#

well I got it thank u so much