Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #8199 > unrolled thread
| Started by | Victor Porton <porton@narod.ru> |
|---|---|
| First post | 2017-12-11 04:09 +0200 |
| Last post | 2017-12-13 21:02 -0800 |
| Articles | 5 — 3 participants |
Back to article view | Back to comp.programming
Breadth first search or depth first search? Victor Porton <porton@narod.ru> - 2017-12-11 04:09 +0200
Re: Breadth first search or depth first search? David Brown <david.brown@hesbynett.no> - 2017-12-11 11:17 +0100
Re: Breadth first search or depth first search? Öö Tiib <ootiib@hot.ee> - 2017-12-11 14:30 -0800
Re: Breadth first search or depth first search? Victor Porton <porton@narod.ru> - 2017-12-12 11:16 +0200
Re: Breadth first search or depth first search? Öö Tiib <ootiib@hot.ee> - 2017-12-13 21:02 -0800
| From | Victor Porton <porton@narod.ru> |
|---|---|
| Date | 2017-12-11 04:09 +0200 |
| Subject | Breadth first search or depth first search? |
| Message-ID | <p0kpcd$r18$1@gioia.aioe.org> |
Small graph, need to check if two given nodes are connected. Breadth first search or depth first search? (which of two is better?) Or incidence matrix? -- Victor Porton - http://portonvictor.org
[toc] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2017-12-11 11:17 +0100 |
| Message-ID | <p0llvs$179$1@dont-email.me> |
| In reply to | #8199 |
On 11/12/17 03:09, Victor Porton wrote: > Small graph, need to check if two given nodes are connected. > > Breadth first search or depth first search? (which of two is better?) > If the graph is small, it will not make much difference. It normally makes most difference when you have cache effects, or want to limit recursion depth, or want to avoid more advanced data structures, or have trees/graphs of a particular shape, or know a bit about where you are most likely to find a result. None of that typically matters for a small graph - use whatever makes it easier to write correct and clear code. > Or incidence matrix? >
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2017-12-11 14:30 -0800 |
| Message-ID | <59c65503-8b41-45a3-96f5-00076e082cff@googlegroups.com> |
| In reply to | #8199 |
On Monday, 11 December 2017 04:09:24 UTC+2, Victor Porton wrote: > Or incidence matrix? Incidence matrix is one of typical ways to represent a graph. Both searches can be ran on it.
[toc] | [prev] | [next] | [standalone]
| From | Victor Porton <porton@narod.ru> |
|---|---|
| Date | 2017-12-12 11:16 +0200 |
| Message-ID | <p0o6p7$d77$2@gioia.aioe.org> |
| In reply to | #8201 |
Öö Tiib wrote: > On Monday, 11 December 2017 04:09:24 UTC+2, Victor Porton wrote: > > >> Or incidence matrix? > > Incidence matrix is one of typical ways to represent a graph. Both > searches can be ran on it. I wanted to say "connectivity matrix". -- Victor Porton - http://portonvictor.org
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2017-12-13 21:02 -0800 |
| Message-ID | <f1a69ef5-a944-4878-9124-29310b6a7d0c@googlegroups.com> |
| In reply to | #8202 |
On Tuesday, 12 December 2017 11:16:28 UTC+2, Victor Porton wrote: > Öö Tiib wrote: > > > On Monday, 11 December 2017 04:09:24 UTC+2, Victor Porton wrote: > > > > > >> Or incidence matrix? > > > > Incidence matrix is one of typical ways to represent a graph. Both > > searches can be ran on it. > > I wanted to say "connectivity matrix". Adjacency matrix (sometimes called connectivity matrix) is also a way to represent a graph. Again both searches can be ran on it.
[toc] | [prev] | [standalone]
Back to top | Article view | comp.programming
csiph-web