C# 中的 BFS 地图绘制

Question

我如何在 C# 中的未加权、无向图中使用 BFS，使用 adj 列表来染色地图，使用四种颜色，以便 2 个相邻的国家具有不同的颜色。

这就是我实现图表的方式，我将添加一个将四种颜色表示为字符串的数组，另一个表示国家/地区的数组，例如每个顶点代表一个国家/地区。

    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);
                    }
                }
            }
        }
    }
}

我真的不知道如何修改 BFS 函数来帮助我解决问题。

Answer 1

您可以添加一个“访问者”，这是一个小函数，每次在搜索中到达一个新节点时都会调用该函数。将新访问节点的索引传递给访问者。在访问者中查看新节点的所有相邻节点。如果访问过相邻节点，则从可能的颜色中删除相邻节点的颜色。使用未被访问的相邻节点使用的颜色为新节点着色。

C# 中的 BFS 地图绘制

BFS Map-Drawing in C#

c#

graph-theory

breadth-first-search