using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 试验版
{
    public class Graph
    {
                
        // 邻接列表的字典
        public Dictionary<dian, List<dian>> adjList;

        public Graph()
        {
            adjList = new Dictionary<dian, List<dian>>();
        }

        // 添加节点
        public void AddVertex(dian vertex)
        {
            if (!adjList.ContainsKey(vertex))
            {
                adjList[vertex] = new List<dian>();
            }
        }


        public void RemoveVertex(dian vertex)
        {
            // 检查是否包含该顶点
            if (adjList.ContainsKey(vertex))
            {
                // 删除以该顶点为起点的所有边
                adjList.Remove(vertex);
            }

            // 删除所有以该顶点为终点的边
            foreach (var key in adjList.Keys)
            {
                adjList[key].Remove(vertex);
            }
        }



        // 添加无向边
        public void AddEdge(dian vertex1, dian vertex2)
        {
            if (!adjList.ContainsKey(vertex1))
                AddVertex(vertex1);
        
            if (!adjList.ContainsKey(vertex2))
                AddVertex(vertex2);
        
            adjList[vertex1].Add(vertex2);
            adjList[vertex2].Add(vertex1);
        }

        //删除连接
        public void RemoveEdge(dian vertex1, dian vertex2)
        {
            
            if (adjList.ContainsKey(vertex1) && adjList.ContainsKey(vertex2))
            {
                
                adjList[vertex1].Remove(vertex2);

                
                adjList[vertex2].Remove(vertex1);
            }
        }




        //广度优先搜索（BFS）
        public List<dian> BFS(dian start)
        {
            if (start.fatherelement.sbname != "el")
            {
                return new List<dian>();
            }

            HashSet<dian> visited = new HashSet<dian>();
            Queue<dian> queue = new Queue<dian>();
            List<dian> result = new List<dian>();

            visited.Add(start);
            queue.Enqueue(start);
            result.Add(start);

            while (queue.Count > 0)
            {
                dian vertex = queue.Dequeue();
                //Console.Write(vertex + " ");

                foreach (var neighbor in adjList[vertex])
                {
                    if (!visited.Contains(neighbor))
                    {
                        visited.Add(neighbor);
                        queue.Enqueue(neighbor);
                        result.Add(neighbor);
                    }
                }
            }

            return result;
        }



        // 输出图
        public void PrintGraph()
        {
            foreach (var vertex in adjList)
            {
                Console.Write(vertex.Key + " -> ");
                foreach (var edge in vertex.Value)
                {
                    Console.Write(edge + " ");
                }
                Console.WriteLine();
            }
        }
    }






}
