标签: adjacency-matrix

我试图在java中实现一个邻接矩阵,它将产生哈密顿循环的输出,然后可以用不同的算法解决,例如kruskurals,djikstras和2opt方法.我知道我需要一个2d阵列,但我不知道从哪里开始.我需要能够存储矩阵并将其应用于我拥有的图形,该图形目前是具有"n"个节点的圆(取决于矩阵).欢迎所有的帮助,谢谢

想象一下,我有一个由36个顶点组成的6x6正方形(即每行6个顶点和每列6个顶点),看起来像这样:

•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •  
•  •  •  •  •  •

每个顶点都与1,2,3或4个近邻点连接 - 所以我们基本上得到一个带有顶点和边的图.我的问题如下:我想要一个机器人通过那个"迷宫"的边缘,直到找到某个顶点放置某个物体.一旦找到该对象,就应该以最快的方式回到起点.

现在,我不太清楚如何实现这一点,所以我的问题是:在C中保存有关顶点和边的信息的最佳结构是什么？(邻接矩阵对我来说似乎效率低,因为36x36非常大).而且,使用这些信息,我怎样才能找到最快的方式？

我有大约100个节点的大型稀疏邻接矩阵,我正在使用MATLAB进行处理.我想尽可能高效地将这些矩阵转换为网络边缘列表.作为一个示例邻接矩阵来说明这一点:

adj =
     1     0     1     0
     0     0     1     1
     0     0     1     0
     0     1     0     0

我在这里称之为网络边缘列表的输出是:

>> adj2edgeList_Alex(adj)
ans =
     0     0
     0     2
     1     2
     1     3
     2     2
     3     1

我必须这样做的代码停留了一段时间.

function edge_list = adj2edgeList_Alex(graph)

edge_num = length(logical(graph > 0));
edge_list = zeros(edge_num,2);
row_ind = 1;
for ii=1:size(graph,2)
    ind_temp = find(graph(ii,:)==1);
    if(isempty(ind_temp) == 0)
        ind_temp = ind_temp - 1;
        edges_iter = length(ind_temp);   
        node_num = ii - 1; …

我有data.frame10个视频,每列都是一个标记,指示视频的类别.例如,数据将如下所示:

data <- data.frame(id=paste0("r", 1:10), A=sample(0:1,10,TRUE), B=sample(0:1,10,TRUE), C=sample(0:1,10,TRUE))
data
    id A B C
1   r1 1 0 1
2   r2 0 0 0
3   r3 0 1 0
4   r4 1 1 0
5   r5 0 0 0
6   r6 1 0 1
7   r7 1 0 1
8   r8 0 1 1
9   r9 0 0 1
10 r10 1 0 0

现在我想基于标签形成一个邻接矩阵,其值应该是具有相同标签的视频数量.例如,单元格A-C应该是3,因为r1,r6并且r7具有相同的标签.最后,我想要一个如下输出矩阵:

     A    B    C
A    5    1 …

public int bfs(int maxDepth){
        int src = 2;
        int dest = 2;
        int i;
        int depth = 0;
        int countPaths = 0;
        int element;

        queue.add(src);

        while(!queue.isEmpty() && depth <= maxDepth)
        {   
            element = queue.remove();
            i = 0;

            while(i < 5) 
            {   
                if(arr[element][i] > 0)
                {
                    queue.add(i);

                    if(i == dest)
                        countPaths++;
                }       
                i++;
            }
        }

        queue.clear();
        return countPaths;
    }

你好!!给定源和目的地,我需要找到一条路径.就遍历图表而言,我的BFS算法工作得很好.我的问题是当我想要它时停止它.我拿出了我增加深度的地方,所以我看起来不像是一个完全白痴.我希望有人能帮帮忙.基本上我想知道如何跟踪当前的深度.谢谢!

例:

找到从C到C的路径数,最多3个停靠点.答案是两条路:

C - > D - > C(2站)

C - > E - > B - > C(3站)

示例2:找到从A到C的路径数,最多3个停靠点.答案是三条路.

A …

我想找到图中所有节点之间的距离,而不是总和我想要乘以它们的边权重.

举个例子:

library(igraph)

# create a weighted adjacency matrix
mx <- structure(c(0, 0.5, 0, 0, 0, 0.5, 0, 0.5, 0.5, 0, 0, 0.5, 0, 0, 0.5, 0, 0.5, 
    0, 0, 0, 0, 0, 0.5, 0, 0), .Dim = c(5L, 5L))

## convert to igraph object
mx2 <- graph.adjacency(mx, weighted = TRUE)

我可以得到所有节点之间的距离如下:

shortest.paths(mx2)

 [,1] [,2] [,3] [,4] [,5]
[1,]  0.0  0.5  1.0  1.0  1.5
[2,]  0.5  0.0  0.5  0.5  1.0
[3,]  1.0  0.5  0.0  1.0  0.5
[4,]  1.0  0.5  1.0 …

我在matlab中有一个邻接矩阵.我如何绘制图表？由于我有> 500个节点,我不能使用随机(或网格状)坐标的gplot.

我一直在寻找一个 python 实现，给定一个数组，它返回 4 或 8 连接的邻接矩阵。我感到惊讶的是 cv2 或 networkx 不包含此功能。我遇到了这个很棒的 Matlab实现，并决定用 python 做一些类似的东西。

问题：我正在寻找一种可以改进运行时/空间中链接的 Matlab 解决方案或其他有趣方法的实现。

免责声明：

我在这里提交我自己的实现，因为我认为我不可能是唯一需要为图像处理或其他应用程序创建（4 / 8 连接）邻接矩阵的人。我希望能够提供改进或更好的实施。

我目前正在尝试编写代码来计算度矩阵，以便我可以计算拉普拉斯 L = D - A，其中 D=度矩阵，A=邻接矩阵。

这将在我的光谱聚类算法中使用。我正在使用 Python。所以对于这个玩具示例，我在做这件事时遇到了麻烦。任何人都可以提供一种有效的方法来做到这一点，或者是否有用于计算度矩阵的 API？我的问题很简单，计算连接矩阵度的有效方法是什么，或者是否有一个 python 模块？

例子：

import numpy as np
matrix = np.matrix('1, 1, 1, 1; 1, 0, 0, 0; 0, 0, 1, 1')

matrix =

 1     1     1     1
 1     0     0     0
 0     1     0     1
 0     0     1     1

我如何计算给我 5 3 4 4 的度（矩阵），它代表每个节点的连接度？谢谢你。

假设我们从一个由元组列表表示的“友谊”图开始，

friendships = [(0, 1), (0, 2), (1, 2), (1, 3), (2,
3), (3, 4),(4, 5), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9)]

其中元素0是1的朋友（因此1是0的朋友）。

我想以一种始终适用于这种元组表示形式的方式从头构造邻接矩阵。

我有以下（排斥）Python代码：

friendships = [(0, 1), (0, 2), (1, 2), (1, 3), (2,
3), (3, 4),(4, 5), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9)]

我知道它效率低下而且非常难看。有没有更聪明的方法来解决这个问题？我上面给出的示例列表的输出应为

[[0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 1, 1, 0, 0, 0, 0, 0, 0],
 [1, 1, 0, …