遍历以邻接矩阵表示的图
遍历以邻接矩阵表示的图
提问于 2013-03-09 23:15:16
我想使用深度优先和广度优先的方法来遍历图。我以前在一个简单的节点列表上做到了这一点，但我从未尝试过使用邻接矩阵，老实说，我甚至不知道从哪里开始。
这是我的矩阵：
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;
}任何帮助都将不胜感激！！
此矩阵表示的图形：
回答 1
Stack Overflow用户
回答已采纳
发布于 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迭代器往往更简单，但初学者程序员通常很难弄清楚控制流。尝试以两种方式编写它，看看效果如何。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15312273
复制相关文章
相似问题
腾讯云开发者
