VB新手请教一个算法问题
12345表示一个五边形的5个顶点,下面的数据表示边的连接情况,比如1号点与2345点之间有边连接,2号与1、3号点连接,而与其他点之间没有边,现在我想找出这里面的三个三角形123,134,145,即三个顶点都有边连接的情况,而2跟5之间没有连接,因而125这种的三角形不要,请问该如何写这段程序
1{2,3,4,5} 2{1,3} 3{2,1,4} 4{3,1,5} 5{4,1}
[解决办法]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>()
{
{ 1, new List<int>() { 2, 3, 4, 5 } },
{ 2, new List<int>() { 1, 3 } },
{ 3, new List<int>() { 2, 1, 4 } },
{ 4, new List<int>() { 3, 1, 5 } },
{ 5, new List<int>() { 4, 1 } }
};
int[] edges = new int[] { 1, 2, 3, 4, 5 };
var query = from x in edges
from y in edges
where y > x
from z in edges
where z > y
where dict[x].Contains(y) && dict[x].Contains(z) && dict[y].Contains(z)
select new { x, y, z };
foreach (var item in query)
Console.WriteLine("{0}, {1}, {2}.", item.x, item.y, item.z);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Dictionary<int, List<int>> edges = new Dictionary<int, List<int>>()
{
{ 1, new List<int>() { 2, 3, 4, 5 } },
{ 2, new List<int>() { 1, 3 } },
{ 3, new List<int>() { 2, 1, 4 } },
{ 4, new List<int>() { 3, 1, 5 } },
{ 5, new List<int>() { 4, 1 } }
};
int[] points = new int[] { 1, 2, 3, 4, 5 };
var query = from x in points
from y in points
where y > x
from z in points
where z > y
where edges[x].Contains(y) && edges[x].Contains(z) && edges[y].Contains(z)
select new { x, y, z };
foreach (var item in query)
Console.WriteLine("{0}, {1}, {2}.", item.x, item.y, item.z);
}
}
}
Option Explicit
Sub Main()
Dim aConnect() As Boolean
Dim i1 As Long
Dim i2 As Long
Dim i3 As Long
aConnect = BuildArray(0, 1, 1, 1, 1, _
1, 0, 1, 0, 0, _
1, 1, 0, 1, 0, _
1, 0, 1, 0, 1, _
1, 0, 0, 1, 0)
For i1 = 1 To 5
For i2 = i1 + 1 To 5
If aConnect(i1, i2) Then 'i1->i2
For i3 = i2 + 1 To 5
If aConnect(i2, i3) And aConnect(i3, i1) Then 'i2->i3->i1
Debug.Print i1 & "," & i2 & "," & i3
End If
Next
End If
Next
Next
End Sub
Function BuildArray(ParamArray args()) As Boolean()
Dim aConnect() As Boolean
Dim i As Long
ReDim aConnect(1 To 5, 1 To 5)
For i = 0 To 24
aConnect((i \ 5) + 1, (i Mod 5) + 1) = CBool(args(i))
Next
BuildArray = aConnect
End Function