我想使用深度优先和广度优先的方法来遍历图。我以前在一个简单的节点列表上做到了这一点,但我从未尝试过使用邻接矩阵,老实说,我甚至不知道从哪里开始。
这是我的矩阵:
999999999 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 999999999 0 3 1 0 0 0 0 0 0 0 0 0 0 0
1 0 999999999 3 0 1 0 0 0 0 0 0 0 0 0 0
0 3 3 999999999 0 0 0 8 0 0 0 0 0 0 0 0
0 1 0 0 999999999 0 1 3 0 0 0 0 0 0 0 0
0 0 1 0 0 999999999 0 3 1 0 0 0 0 0 0 0
0 0 0 0 1 0 999999999 0 0 3 0 1 0 0 0 0
0 0 0 8 3 3 0 999999999 0 8 8 0 3 0 0 0
0 0 0 0 0 1 0 0 999999999 0 3 0 0 1 0 0
0 0 0 0 0 0 3 8 0 999999999 0 0 0 0 3 0
0 0 0 0 0 0 0 8 3 0 999999999 0 0 0 0 3
0 0 0 0 0 0 1 0 0 0 0 999999999 0 0 1 0
0 0 0 0 0 0 0 3 0 0 0 0 999999999 0 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 999999999 0 1
0 0 0 0 0 0 0 0 0 3 0 1 1 0 999999999 0
0 0 0 0 0 0 0 0 0 0 3 0 1 1 0 999999999
下面是我创建这个矩阵(C#)的方法:
private static int[,] CreateMatrix()
{
int A = 0;
int B = 1;
int C = 2;
int D = 3;
int E = 4;
int F = 5;
int G = 6;
int H = 7;
int I = 8;
int J = 9;
int K = 10;
int L = 11;
int M = 12;
int N = 13;
int O = 14;
int P = 15;
int[,] matrix = new int[16, 16];
matrix[A, B] = 1;
matrix[A, C] = 1;
matrix[B, D] = 3;
matrix[B, E] = 1;
matrix[C, D] = 3;
matrix[C, F] = 1;
matrix[D, H] = 8;
matrix[E, G] = 1;
matrix[E, H] = 3;
matrix[F, H] = 3;
matrix[F, I] = 1;
matrix[G, J] = 3;
matrix[G, L] = 1;
matrix[H, J] = 8;
matrix[H, K] = 8;
matrix[H, M] = 3;
matrix[I, K] = 3;
matrix[I, N] = 1;
matrix[J, O] = 3;
matrix[K, P] = 3;
matrix[L, O] = 1;
matrix[M, O] = 1;
matrix[M, P] = 1;
matrix[N, P] = 1;
matrix[B, A] = 1;
matrix[C, A] = 1;
matrix[D, B] = 3;
matrix[E, B] = 1;
matrix[D, C] = 3;
matrix[F, C] = 1;
matrix[H, D] = 8;
matrix[G, E] = 1;
matrix[H, E] = 3;
matrix[H, F] = 3;
matrix[I, F] = 1;
matrix[J, G] = 3;
matrix[L, G] = 1;
matrix[J, H] = 8;
matrix[K, H] = 8;
matrix[M, H] = 3;
matrix[K, I] = 3;
matrix[N, I] = 1;
matrix[O, J] = 3;
matrix[P, K] = 3;
matrix[O, L] = 1;
matrix[O, M] = 1;
matrix[P, M] = 1;
matrix[P, N] = 1;
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 16; j++)
{
if (matrix[i, j] == 0)
matrix[i, j] = 0;
if (i == j)
matrix[i, j] = 999999999;
}
}
return matrix;
}
任何帮助都将不胜感激!!
此矩阵表示的图形:
发布于 2013-03-10 00:13:23
除了一个问题之外,计算机科学中的每一个问题都可以通过添加更多抽象来解决。
首先,以尽可能抽象的方式编写广度优先遍历:
void BreadthFirstTraversal(Graph graph, Vertex start)
{
/* A miracle happens */
}
我们有一个方法可以做我们想做的事情。除了它还没有被写出来。所以用稍微少一点的抽象来写它
void BreadthFirstTraversal(Graph graph, Vertex start)
{
/* make a queue of vertices */
/* make a mark set of vertices */
/* enqueue and mark start */
/* while the queue is not empty */
/* dequeue a vertext */
/* enqueue and mark all the unmarked neighbours of the vertex */
}
继续前进,移除越来越多的抽象。
void BreadthFirstTraversal(Graph graph, Vertex start)
{
var queue = new VertexQueue();
var markSet = new VertexMarkSet();
queue.Enqueue(start);
markSet.Add(start);
while(queue.NotEmpty())
{
var vertex = queue.Dequeue();
foreach(Vertex neighbour in graph.ListNeighbours(vertex))
{
if (!markSet.Contains(neighbour))
{
markSet.Add(neighbour);
queue.Enqueue(neighbour);
}
}
}
}
好了,现在你已经有了一个适用于任何图的算法,无论它的内部表示是什么。因此,您所要做的就是编写ListNeighbours(Vertex)
,然后就完成了。(假设您已经知道如何编写队列和集合,或者愿意使用基类库附带的类型。)你要怎么做?
你看到我是如何在那里使用抽象的吗?我真的不关心它是一个邻接矩阵还是一个邻接列表,我所关心的是这个图为我提供了给我一个顶点的邻居的服务。
那么,在给定邻接矩阵的情况下,如何编写ListNeighbours(Vertex)
呢?
要调查的两种可能的解决方案:
Graph.ListNeighbours(Vertex)
方法返回一个List<Vertex>
。构造列表并分发。IEnumerable<Vertex>
,并使用yield return
生成相邻顶点的序列。更新:好的,那么我们如何从邻接矩阵中生成一个相邻矩阵序列呢?
让我们假设每个顶点都有编号,因此Vertex
实际上是int
;这是使用邻接矩阵的传统方式。我们想要接受一个顶点--一个int --并返回一个与其相邻的顶点序列。
我们有一个数组,如果顶点j
是顶点i
的邻居,那么它的属性是array[i, j]
非零。
同样,从抽象开始,并按照您的方式进行实现:
public List<int> ListNeighbours(int vertex)
{
/* a miracle happens */
}
我们需要做些什么才能让这个奇迹发生?
public List<int> ListNeighbours(int vertex)
{
/* create a new list */
/* for each vertex j in the graph */
/* if j is a neighbour of i then add it to the list */
/* return the list */
}
或者,您可以使用yield return
创建序列:
public IEnumerable<int> ListNeighbours(int vertex)
{
/* for each vertex j in the graph */
/* if j is a neighbour of i then yield return j */
}
yield return
迭代器往往更简单,但初学者程序员通常很难弄清楚控制流。尝试以两种方式编写它,看看效果如何。
https://stackoverflow.com/questions/15312273
复制相似问题