GraphTraversal.cs
2.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TheMachine
{
public class GraphTraversal
{
// 用于存储单向联通的边
public List<(Point, Point)> oneWayEdges = new List<(Point, Point)>();
// 用于存储双向联通的边
public List<(Point, Point)> twoWayEdges = new List<(Point, Point)>();
public void Traverse(Point start)
{
Stack<Point> stack = new Stack<Point>();
stack.Push(start);
while (stack.Count > 0)
{
Point current = stack.Pop();
if (current.Visited)
continue;
current.Visited = true;
// 检查并添加边
AddEdges(current, current.Up); // 上
AddEdges(current, current.Down); // 下
AddEdges(current, current.Left); // 左
AddEdges(current, current.Right); // 右
// 将未访问的邻近点压入栈中
if (current.Up != null && !current.Up.Visited)
stack.Push(current.Up);
if (current.Down != null && !current.Down.Visited)
stack.Push(current.Down);
if (current.Left != null && !current.Left.Visited)
stack.Push(current.Left);
if (current.Right != null && !current.Right.Visited)
stack.Push(current.Right);
}
}
// 添加边到对应的列表中
private void AddEdges(Point from, Point to)
{
if (to == null)
return;
// 单向联通
if ((from.Up == to || from.Down == to || from.Left == to || from.Right == to)&&
!(to.Up == from || to.Down == from || to.Left == from || to.Right == from))
oneWayEdges.Add((from, to));
// 双向联通（如果两个点都互相指向对方）
if ((to.Up == from || to.Down == from || to.Left == from || to.Right == from)&&
(from.Up == to || from.Down == to || from.Left == to || from.Right == to) &&
!twoWayEdges.Contains((to, from))) // 避免重复添加
{
twoWayEdges.Add((from, to));
}
}
}
}