BFS / DFS
Algorithm 2019. 8. 25. 17:53https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16
https://www.dotnetforall.com/breadth-first-searchbfs-in-c/
Breadth First Search(BFS) in C# • Dot Net For All
Pluralsight Free account with Unlimited Access - Learn Anything Hello Friends, In this article I will discuss one of the two traversing mechanisms used for tree and graphs. I will cover breadth first search(BFS) with C# example.Subscribe and get my free e-
www.dotnetforall.com
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
using System;
using System.Collections.Generic;
namespace Application
{
class MainClass
{
public static void Main(string[] args)
{
//var s = new Solution();
//s.solution();
Node topNode = new Node();
var node9 = new Node();
var node5 = new Node();
var node2 = new Node();
var node10 = new Node();
var node6 = new Node();
var node7 = new Node();
var node3 = new Node();
var node4 = new Node();
var node8 = new Node();
var s2 = new Solution2();
}
}
internal class Solution {
List<int>[] arr = new List<int>[8];
bool[] c = new bool[8];
public void solution() {
{
arr[i] = new List<int>();
}
arr[1].Add(2);
arr[2].Add(1);
arr[1].Add(3);
arr[3].Add(1);
arr[2].Add(3);
arr[3].Add(2);
arr[2].Add(4);
arr[4].Add(2);
arr[2].Add(5);
arr[5].Add(2);
bfs(1);
}
public void bfs(int start) {
Queue<int> q = new Queue<int>();
q.Enqueue(start);
c[start] = true;
while (q.Count > 0) {
int x = q.Dequeue();
Console.WriteLine(x);
for (int i = 0; i < arr[x].Count; i++) {
int y = arr[x][i];
if (!c[y])
{
q.Enqueue(y);
c[y] = true;
}
}
}
}
}
public class Solution2 {
public void BFS(Node topNode) {
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(topNode);
var element = queue.Dequeue();
foreach(var item in element.Neighbours){
queue.Enqueue(item);
}
}
}
}
}
public class Node {
public int Value { get; set; }
public IList<Node> Neighbours { get; set; }
public Node() {
Neighbours = new List<Node>();
}
}
}
|
https://senravi.wordpress.com/2016/09/22/bfs-and-dfs-example-in-c/
BFS and DFS example in C#
From WikiPedia: Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referr…
senravi.wordpress.com
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
using System;
namespace Application
{
class MainClass
{
public static void Main(string[] args)
{
Console.WriteLine("Graph");
var graph = new Graph(4);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 2);
graph.AddEdge(2, 0);
graph.AddEdge(2, 3);
graph.AddEdge(3, 3);
//Console.WriteLine("BFS traversal starting");
Console.WriteLine("DFS traversal starting");
graph.DFS(2);
}
}
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
using System;
using System.Collections.Generic;
namespace Application
{
public class Graph
{
private int vertices; //정점의 갯수
private List<int>[] adj; //인접노드 배열
//constructor
public Graph(int v)
{
this.vertices = v;
this.adj = new List<int>[v];
for (int i = 0; i < v; i++) {
this.adj[i] = new List<int>();
}
}
//edge추가 v->w
public void AddEdge(int v, int w) {
this.adj[v].Add(w);
}
//print
public void Print() {
for(int i = 0; i<this.vertices; i++) {
Console.Write(i + ":[");
string s = "";
foreach(var k in this.adj[i]) {
s = s + (k + ",");
}
s = s.Substring(0, s.Length - 1);
s = s + "]";
Console.Write(s);
Console.WriteLine();
}
}
//bfs
public void BFS(int start) {
//Queue<List<int>> q = new Queue<List<int>>();
//q.Enqueue(this.adj[start]);
//while(q.Count > 0) {
// var item = q.Dequeue();
// foreach (var n in item) {
// Console.WriteLine(n);
// q.Enqueue(this.adj[n]);
// }
//}
bool[] visited = new bool[this.vertices];
Queue<int> q = new Queue<int>();
visited[start] = true;
q.Enqueue(start);
while (q.Count > 0) {
start = q.Dequeue();
Console.WriteLine("next -> " + start);
foreach(int next in this.adj[start])
{
if (!visited[next]) {
visited[next] = true;
q.Enqueue(next);
}
}
}
}
public void DFS(int start) {
bool[] visited = new bool[this.vertices];
Stack<int> stack = new Stack<int>();
visited[start] = true;
start = stack.Pop();
Console.WriteLine("next -> " + start);
foreach(int i in this.adj[start])
{
if (!visited[i]) {
visited[i] = true;
}
}
}
}
}
}
|
https://rextester.com/YUYX6886
BFS DFS stack vs recursive, C# - rextester
Language:Ada Assembly Bash C# C++ (gcc) C++ (clang) C++ (vc++) C (gcc) C (clang) C (vc) Client Side Common Lisp D Elixir Erlang F# Fortran Go Haskell Java Javascript Kotlin Lua MySql Node.js Ocaml Octave Objective-C Oracle Pascal Perl Php PostgreSQL Prolog
rextester.com
https://www.koderdojo.com/blog/depth-first-search-algorithm-in-csharp-and-net-core
KoderDojo - Depth-First Search Algorithm in C# and .NET Core
I am a C# ASP.NET MVC Developer learning Python and computer science. This website is a playground where I share code examples both in Python and C# on Data Structures, Algorithms, Data Science, etc. Many of these examples are taken from problem sets in my
www.koderdojo.com
'Algorithm' 카테고리의 다른 글
| 프로그래머스 | 문자열 내 마음대로 정렬하기 (0) | 2019.08.26 |
|---|---|
| 프로그래머스 | Collatz(콜라츠) 추측 (0) | 2019.08.26 |
| 프로그래머스 | 타겟 넘버 (0) | 2019.08.23 |
| c# 알고리즘 (0) | 2019.08.23 |
| 프로그래머스 | H-Index (정렬) (0) | 2019.08.23 |