주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공한다.
int SequentialSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return i;
}
}
return -1;
}
int BinarySearch(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}
- DFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가능한 깊이 들어가서 노드를 탐색, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식이다.
- 시간 복잡도 : 최악의 경우 O(V + E)이다. (V는 노드 수, E는 간선 수)
- BFS는 트리나 그래프를 탐색하는 알고리즘 중 하나로, 루트에서 시작하여 가까운 노드부터 방문, 그 다음 레벨의 노드를 방문하는 방식이다.
- 시간 복잡도 : 최악의 경우 O(V + E)이다. (V는 노드 수, E는 간선 수)
using System;
using System.Collections.Generic;
public class Graph
{
private int V; // 그래프의 정점 개수
private List<int>[] adj; // 인접 리스트
public Graph(int v)
{
V = v;
adj = new List<int>[V];
for (int i = 0; i < V; i++)
{
adj[i] = new List<int>();
}
}
// 간선 추가
public void AddEdge(int v, int w)
{
adj[v].Add(w);
}
public void DFS(int v)
{
bool[] visited = new bool[V];
DFSUtil(v, visited);
}
private void DFSUtil(int v, bool[] visited)
{
visited[v] = true;
Console.Write($"{v} ");
foreach (int n in adj[v])
{
if (!visited[n])
{
DFSUtil(n, visited);
}
}
}
public void BFS(int v)
{
bool[] visited = new bool[V];
Queue<int> queue = new Queue<int>();
visited[v] = true;
queue.Enqueue(v);
while (queue.Count > 0)
{
int n = queue.Dequeue();
Console.Write($"{n} ");
foreach (int m in adj[n])
{
if (!visited[m])
{
visited[m] = true;
queue.Enqueue(m);
}
}
}
}
}
public class Program
{
public static void Main()
{
Graph graph = new Graph(6);
// 그래프 생성
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 3);
graph.AddEdge(2, 4);
graph.AddEdge(3, 4);
graph.AddEdge(3, 5);
graph.AddEdge(4, 5);
Console.WriteLine("DFS traversal:");
graph.DFS(0);
Console.WriteLine();
Console.WriteLine("BFS traversal:");
graph.BFS(0);
Console.WriteLine();
}
}
using System;
class DijkstraExample
{
static int V = 6; // 정점의 수
// 주어진 그래프의 최단 경로를 찾는 다익스트라 알고리즘
static void Dijkstra(int[,] graph, int start)
{
int[] distance = new int[V]; // 시작 정점으로부터의 거리 배열
bool[] visited = new bool[V]; // 방문 여부 배열
// 거리 배열 초기화
for (int i = 0; i < V; i++)
{
distance[i] = int.MaxValue;
}
distance[start] = 0; // 시작 정점의 거리는 0
// 모든 정점을 방문할 때까지 반복
for (int count = 0; count < V - 1; count++)
{
// 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음
int minDistance = int.MaxValue;
int minIndex = -1;
for (int v = 0; v < V; v++)
{
if (!visited[v] && distance[v] <= minDistance)
{
minDistance = distance[v];
minIndex = v;
}
}
// 최소 거리를 가진 정점을 방문 처리
visited[minIndex] = true;
// 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트
for (int v = 0; v < V; v++)
{
if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v])
{
distance[v] = distance[minIndex] + graph[minIndex, v];
}
}
}
// 최단 경로 출력
Console.WriteLine("정점\t거리");
for (int i = 0; i < V; i++)
{
Console.WriteLine($"{i}\t{distance[i]}");
}
}
static void Main(string[] args)
{
int[,] graph = {
{ 0, 4, 0, 0, 0, 0 },
{ 4, 0, 8, 0, 0, 0 },
{ 0, 8, 0, 7, 0, 4 },
{ 0, 0, 7, 0, 9, 14 },
{ 0, 0, 0, 9, 0, 10 },
{ 0, 0, 4, 14, 10, 0 }
};
int start = 0; // 시작 정점
Dijkstra(graph, start);
}
}