How do I use BFS in an unweighted, undirected graph in C#, implemented using adj list to dye a map, using four colors so that 2 countries that are neighbours to have different colors.

This is how I implemented the graphs, I will add, an array that represents the four colors as strings, and another one for countries, such as every vertex to represent a country.

    internal class Graph
    {
        private int vertices;
        private LinkedList<int>[] adj;
        public Graph(int v)
        {
            vertices = v;
            adj = new LinkedList<int>[v];
            for(int i = 0; i < v; i  )
            {
                adj[i] = new LinkedList<int>();
            }
        }

        public void addEdge(int c, int v)
        {
            adj[c].AddLast(v);
        }

        public void BFS(int s)
        {
            bool[] visited = new bool[vertices];
            for(int i=0; i<vertices; i  )
            {
                visited[i] = false;
            }

            LinkedList<int> queue = new LinkedList<int>();

            visited[s] = true;
            queue.AddLast(s);

            while (queue.Any())
            {
                s = queue.First();

                Console.WriteLine(s   " ");

                LinkedList<int> list = adj[s];

                foreach(var val in list)
                {
                    if (!visited[val])
                    {
                        visited[val] = true;
                        queue.AddLast(val);
                    }
                }
            }
        }
        
    }
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TrifIonut_MapDrawing
{
    internal class Graph
    {
        private int vertices;
        private LinkedList<int>[] adj;
        private string[] color;
        public Graph(int v)
        {
            vertices = v;
            adj = new LinkedList<int>[v];
            color = new string[v];
            for (int i = 0; i < v; i  )
            {
                adj[i] = new LinkedList<int>();
                color[i] = "";
            }
            color[0] = "blue";
        }

        public void addEdge(int c, int v)
        {
            adj[c].AddLast(v);
        }

        public void BFS(int s)
        {
            bool[] visited = new bool[vertices];
            for (int i = 0; i < vertices; i  )
            {
                visited[i] = false;
            }

            LinkedList<int> queue = new LinkedList<int>();

            visited[s] = true;
            queue.AddLast(s);

            while (queue.Any())
            {
                s = queue.First();



                queue.RemoveFirst();

                LinkedList<int> list = adj[s];

                void visitor()
                {
                    List<string> possibleColors = new List<string>{"blue", "green", "yellow", "red" };
                    foreach (var val in list)
                    {
                        if (visited[val])
                        {
                            for(int i=0; i<possibleColors.Count; i  )
                            {
                                if (color[val] == possibleColors[i])
                                {
                                    possibleColors.RemoveAt(i);
                                }
                            }
                        }
                    }

                    color[s] = possibleColors[0];
                }

                visitor();

                foreach (var val in list)
                {
                    if (!visited[val])
                    {
                        visited[val] = true;
                        queue.AddLast(val);
                    }
                }
            }
        }
    }
}

I don't really know how to modify the BFS function to help me in my matters.

CodePudding user response：

You can add a "visitor", which is a small function that is called each time a new node is reached in the search. Pass into the visitor the index of the newly visited node. In the visitor look at all the adjacent nodes of the new one. If adjacent node has been visited, remove adjacent node's color from possible colors. Color the new node with a color not being used by the visited adjacent nodes.