关于使用c ++的图形中的边的矩阵 [英] About matrix of edge in graph using c++

问题描述

我困惑如何定义程序，将在图中找到边的矩阵。
问题是如果一个输入邻接矩阵的值给出关于顶点连接的信息，例如：有3个顶点，然后V1连接到V2但不是与V3，然后V2连接到V3，它给出：

I confuse how to define the program that will find the matrix of edge in a graph. The problem is if one inputs the value of adjacency matrix that give information about connection of vertices in a graph, example : there are 3 vertices, then V1 connected to V2 but not with V3, then V2 connected to V3, it gives :

0 1 0

1 0 1

0 1 0

0 1 0
1 0 1
0 1 0

现在，有了这个信息，我想让程序找到边到边的连接，例如有3个边：1-2边，2-3边，其输出是：

now, with that information, I want to make the program which find the connection of edge to edge, example there are 3 edges : 1-2 edge, 2-3 edge, and its output is :

0 1

1 0

0 1
1 0

我知道要先输出Adjacency matrix但第二。
提前感谢。

I know to make the first output "Adjacency matrix", but the second. Thanks in advance.

推荐答案

邻接矩阵用于表示图形，意味着您有顶点和边在里面。所以如果输入是：

An adjacency matrix is used to represent a graph which means you have both vertices and edges in it. So if the input is :

0 1 1

1 0 1

1 1 0

0 1 1
1 0 1
1 1 0

这意味着你的图形是完整的。如果你把数字放在你的矩阵上读：

It means your graph is complete. If you read it with putting numbers on your matrix:

X 1 2 3

1 0 1 1

2 1 0 1

3 1 1 0

X 1 2 3
1 0 1 1
2 1 0 1
3 1 1 0

您可以看到：

到V2和V3

V2连接到V1和V3

V3连接到V1和V2

V1 connects to V2 and V3
V2 connects to V1 and V3
V3 connects to V1 and V2

通过阅读第n行

在你的例子中，你的图是不定向的，因为你的矩阵是对角线。

In your example, your graph is non-oriented because your matrix is diagonal.

如果你的目的是找到你的图的边缘，你已经在邻接矩阵中的信息。如果你想看到什么顶点是双连接，你需要找到如果对于顶点Vi和Vj矩阵的M [i] [j]和M [j] [i]成员都有值1总是在非定向图中的情况）。一个可能的算法是矩阵表示上的双循环（通常是两个向量/列表/数组）。

If your aim is to find what are the edges of your graph, you already have the information in the adjacency matrix. If you want to see what vertices are "double connected" you need to find if for vertices Vi and Vj the M[i][j] and the M[j][i] members of your matrix both have the value 1 (It is always the case in non-oriented graph). A possible algorithm for that is just a double loop on your matrix representation (generally two vectors/lists/arrays).

这篇关于关于使用c ++的图形中的边的矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！