{"id":33836,"date":"2024-11-01T09:21:01","date_gmt":"2024-11-01T09:21:01","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33836"},"modified":"2024-11-01T10:55:52","modified_gmt":"2024-11-01T10:55:52","slug":"c-coding-test-course-representation-of-graphs","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33836\/","title":{"rendered":"C# Coding Test Course, Representation of Graphs"},"content":{"rendered":"<article>\n<header>\n<p>Author: [Author Name] | Date: [Date]<\/p>\n<\/header>\n<section>\n<h2>Introduction<\/h2>\n<p>Algorithms play a very important role in coding tests. In particular, graph algorithms are one of the frequently encountered topics in evaluating problem-solving abilities. In this article, we will take a closer look at how to represent a graph using C# and the process of solving algorithm problems using graphs.<\/p>\n<\/section>\n<section>\n<h2>What is a Graph?<\/h2>\n<p>A graph is a data structure consisting of nodes (or vertices) and edges that represent the relationships between them. A graph can be divided into two main elements:<\/p>\n<ul>\n<li><strong>Vertices:<\/strong> The nodes of the graph.<\/li>\n<li><strong>Edges:<\/strong> The connections between the vertices.<\/li>\n<\/ul>\n<p>A graph can be directed (directed graph) or undirected (undirected graph). It can also be classified as connected graph and disconnected graph.<\/p>\n<\/section>\n<section>\n<h2>Methods of Graph Representation<\/h2>\n<p>There are several ways to represent a graph, but the two commonly used methods are the Adjacency Matrix and the Adjacency List.<\/p>\n<h3>1. Adjacency Matrix<\/h3>\n<p>The adjacency matrix uses an n x n sized 2D array to represent the graph according to the number of vertices. If vertex i and vertex j are connected, it is set as <code>matrix[i][j] = 1<\/code> (for a directed graph) or <code>matrix[i][j] = matrix[j][i] = 1<\/code> (for an undirected graph). The advantage of the adjacency matrix is that it can check the existence of edges in O(1) time complexity. However, it may lead to memory waste in sparse graphs, where there are many vertices with few connections.<\/p>\n<h3>2. Adjacency List<\/h3>\n<p>The adjacency list uses a list of connected vertices for each vertex to represent the graph. Each vertex has a list containing the information of connected vertices, which uses less memory but takes O(V) (where V is the number of vertices) time to find vertices connected to a specific vertex. For graphs with a small number of vertices, the adjacency list is more advantageous than the adjacency matrix.<\/p>\n<\/section>\n<section>\n<h2>Algorithm Problem: Finding the Shortest Path<\/h2>\n<h3>Problem Description<\/h3>\n<p>Given the node and edge information of a graph, implement an algorithm to find the shortest path distance from a specific starting node to all other nodes. This problem can be solved using Dijkstra&#8217;s algorithm.<\/p>\n<h3>Input Format<\/h3>\n<pre>\n            - First line: Number of vertices <code>V<\/code> and number of edges <code>E<\/code>\n            - From the second line: <code>E<\/code> lines of edge information <code>u v w<\/code> (weight <code>w<\/code> from vertex <code>u<\/code> to vertex <code>v<\/code>)\n            - Last line: Starting vertex <code>S<\/code>\n        <\/pre>\n<h3>Sample Input<\/h3>\n<pre>\n            5 6\n            1 2 2\n            1 3 3\n            2 3 1\n            2 4 4\n            3 5 1\n            4 5 2\n            1\n        <\/pre>\n<h3>Sample Output<\/h3>\n<pre>\n            0\n            2\n            3\n            6\n            4\n        <\/pre>\n<h3>Solution Process<\/h3>\n<p>Dijkstra&#8217;s algorithm proceeds by using a priority queue to select the node with the shortest distance found so far and updating the distances of the nodes adjacent to that node.<\/p>\n<ol>\n<li>Initialize the graph in the form of an adjacency list.<\/li>\n<li>Use a priority queue to initialize the distances from the starting vertex.<\/li>\n<li>Select the vertex with the shortest distance from the priority queue and update the distances of all vertices connected to that vertex.<\/li>\n<li>Repeat steps 2-3 until all vertices are processed.<\/li>\n<\/ol>\n<h3>C# Code Implementation<\/h3>\n<pre><code>\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\n\nclass Program\n{\n    static void Main(string[] args)\n    {\n        var input = Console.ReadLine().Split();\n        int V = int.Parse(input[0]); \/\/ Number of vertices\n        int E = int.Parse(input[1]); \/\/ Number of edges\n\n        List<Tuple<int, int, int>> edges = new List<Tuple<int, int, int>>();\n        for (int i = 0; i < E; i++)\n        {\n            var edgeInput = Console.ReadLine().Split();\n            int u = int.Parse(edgeInput[0]) - 1; \/\/ 0-indexed\n            int v = int.Parse(edgeInput[1]) - 1; \/\/ 0-indexed\n            int w = int.Parse(edgeInput[2]);\n            edges.Add(Tuple.Create(u, v, w));\n        }\n        \n        int startVertex = int.Parse(Console.ReadLine()) - 1; \/\/ 0-indexed\n        Dijkstra(V, edges, startVertex);\n    }\n\n    static void Dijkstra(int V, List<Tuple<int, int, int>> edges, int startVertex)\n    {\n        \/\/ Initialize the graph\n        List<List<Tuple<int, int>>> graph = Enumerable.Range(0, V)\n                                                        .Select(x => new List<Tuple<int, int>>())\n                                                        .ToList();\n\n        foreach (var edge in edges)\n        {\n            graph[edge.Item1].Add(Tuple.Create(edge.Item2, edge.Item3));\n            graph[edge.Item2].Add(Tuple.Create(edge.Item1, edge.Item3)); \/\/ Undirected graph\n        }\n\n        \/\/ Initialize distance array\n        int[] distances = new int[V];\n        for (int i = 0; i < V; i++)\n            distances[i] = int.MaxValue;\n        distances[startVertex] = 0;\n\n        \/\/ Initialize priority queue\n        var priorityQueue = new SortedSet<Tuple<int, int>>();\n        priorityQueue.Add(Tuple.Create(0, startVertex)); \/\/ (distance, vertex)\n\n        while (priorityQueue.Any())\n        {\n            var current = priorityQueue.Min;\n            priorityQueue.Remove(current);\n            int currentDistance = current.Item1;\n            int currentVertex = current.Item2;\n\n            \/\/ Skip if a shorter path has already been found\n            if (currentDistance > distances[currentVertex])\n                continue;\n\n            foreach (var neighbor in graph[currentVertex])\n            {\n                int neighborVertex = neighbor.Item1;\n                int edgeWeight = neighbor.Item2;\n\n                \/\/ Update distance\n                if (distances[currentVertex] + edgeWeight < distances[neighborVertex])\n                {\n                    distances[neighborVertex] = distances[currentVertex] + edgeWeight;\n                    priorityQueue.Add(Tuple.Create(distances[neighborVertex], neighborVertex));\n                }\n            }\n        }\n\n        \/\/ Output results\n        for (int i = 0; i < V; i++)\n        {\n            if (distances[i] == int.MaxValue)\n                Console.WriteLine(\"INF\");\n            else\n                Console.WriteLine(distances[i]);\n        }\n    }\n}\n        <\/code><\/pre>\n<h3>Conclusion<\/h3>\n<p>This course taught the basic concepts and methods of graph representation, and how to implement Dijkstra's algorithm in C# to solve the shortest path problem. Algorithm problems require continuous practice. I hope you find your own solutions by solving various problems.<\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Author: [Author Name] | Date: [Date] Introduction Algorithms play a very important role in coding tests. In particular, graph algorithms are one of the frequently encountered topics in evaluating problem-solving abilities. In this article, we will take a closer look at how to represent a graph using C# and the process of solving algorithm problems &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33836\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C# Coding Test Course, Representation of Graphs&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[90],"tags":[],"class_list":["post-33836","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C# Coding Test Course, Representation of Graphs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33836\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C# Coding Test Course, Representation of Graphs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Author: [Author Name] | Date: [Date] Introduction Algorithms play a very important role in coding tests. In particular, graph algorithms are one of the frequently encountered topics in evaluating problem-solving abilities. In this article, we will take a closer look at how to represent a graph using C# and the process of solving algorithm problems &hellip; \ub354 \ubcf4\uae30 &quot;C# Coding Test Course, Representation of Graphs&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33836\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:21:01+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:55:52+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"4\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33836\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33836\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, Representation of Graphs\",\"datePublished\":\"2024-11-01T09:21:01+00:00\",\"dateModified\":\"2024-11-01T10:55:52+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33836\/\"},\"wordCount\":488,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33836\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33836\/\",\"name\":\"C# Coding Test Course, Representation of Graphs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:21:01+00:00\",\"dateModified\":\"2024-11-01T10:55:52+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33836\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33836\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33836\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# Coding Test Course, Representation of Graphs\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C# Coding Test Course, Representation of Graphs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33836\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, Representation of Graphs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Author: [Author Name] | Date: [Date] Introduction Algorithms play a very important role in coding tests. In particular, graph algorithms are one of the frequently encountered topics in evaluating problem-solving abilities. In this article, we will take a closer look at how to represent a graph using C# and the process of solving algorithm problems &hellip; \ub354 \ubcf4\uae30 \"C# Coding Test Course, Representation of Graphs\"","og_url":"https:\/\/atmokpo.com\/w\/33836\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:21:01+00:00","article_modified_time":"2024-11-01T10:55:52+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"4\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33836\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33836\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, Representation of Graphs","datePublished":"2024-11-01T09:21:01+00:00","dateModified":"2024-11-01T10:55:52+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33836\/"},"wordCount":488,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33836\/","url":"https:\/\/atmokpo.com\/w\/33836\/","name":"C# Coding Test Course, Representation of Graphs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:21:01+00:00","dateModified":"2024-11-01T10:55:52+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33836\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33836\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33836\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# Coding Test Course, Representation of Graphs"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33836","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33836"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33836\/revisions"}],"predecessor-version":[{"id":33837,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33836\/revisions\/33837"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33836"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33836"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33836"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}