标签: graph-theory

否则说用模式匹配和图遍历替换特征向量并模拟降维？

我的意思是，给定一个英语单词的语义图，计算类似于：

king - man = queen

这意味着我可以从图中减去一个子图，并在给定指标的情况下对结果子图进行评分。

我不希望这将是单个 neo4j 或 gremlin 查询。我对通过图形数据库同时进行全局和局部推理所涉及的底层机制感兴趣。

下面是我对队列拓扑排序算法的阅读，写在我的教科书中：

void topologicalsort(struct Graph* G){
    struct queue* Q;
    int counter;
    int v,w;
    Q=createqueue();
    counter=0;
    for(v=0;v<G->V;v++){
       if(indegree[v]==0)
          enqueue(Q,v);
       while(!isemptyqueue(Q)){
          v=dequeue(Q);
          topologicalorder[v]=++counter;
          for each w to adjacent to v
             if(--indegree[w]==0){
             enqueue(Q,w);
             }


       }
    } 
} 

对于下图，该算法失败：

如果在给定的图中最初 7 5 3 的入度为零，那么它们将被插入到队列中，但是对于与7 5 3我们相邻的任何顶点，我们都没有任何度为 1 的顶点。这意味着这if(--indegree[w]==0)将不成立，7 5 3因此有将不会在队列内进一步排队，因此该算法将不会处理更多的顶点。如果图形是 DAG，我想知道为什么算法会失败？哪种方式不正确？

我知道我们也可以使用 DFS 实现拓扑排序，但我想按原样实现以下内容：

我在乳胶中新编码，我想制作高质量的图（节点和边），特别是我需要制作这种图。

这甚至可能吗？

网格中三角形面的连通分量

我已经使用上面的链接实现了深度优先搜索，并且对于我的大多数数据样本都运行良好。当我的数据样本非常大时，代码会达到断点，由于递归函数变得太深，可能会导致堆栈溢出。有什么办法可以避免这种情况吗？或者我是否必须使用其他方式（例如广度优先搜索/并集查找算法）来查找图中的连接组件。

#include <bits/stdc++.h>\nusing namespace std;\n \nclass Graph {\n \n    // A function used by DFS\n    void DFSUtil(int v);\n \npublic:\n    int count;\n    map<int, bool> visited;\n    map<int, list<int> > adj;\n    // function to add an edge to graph\n    void addEdge(int v, int w);\n \n    // prints DFS traversal of the complete graph\n    void DFS();\n};\n \nvoid Graph::addEdge(int v, int w)\n{\n    adj[v].push_back(w); // Add w to v\xe2\x80\x99s list.\n}\n \nvoid Graph::DFSUtil(int v)\n{\n    // Mark the current node as visited and print it\n …

我正在开发一个 Java 程序，以各种方式分析图形，特别是具有加权边的无向图。我现在试图，给定一个平面图，确定它的面，也就是由图的边缘分隔的“空间”的封闭区域，但我真的找不到一种算法，或者至少是一个可以理解的算法，可以做到这一点我正在努力实施我的其中之一。

有人有什么想法吗？

PS：我应该注意，我没有扎实的图论基础知识

我最近在考虑一个可能的解决方案，以在多项式时间内找到无向图是否具有哈密顿路径。

作为此实现的一部分使用的主要概念基于我在尝试为几个无向图找到（即在纸上）哈密顿路径时注意到的观察结果。

这些步骤可以定义如下：

1. 读取图的邻接矩阵。

2. 在读取邻接矩阵时，将为所有节点创建一个映射（即基于字典的结构）。此外，在读取邻接矩阵时将选择路径的起始节点。这些操作可以描述如下：
   
   

   2.1. 映射将存储图中的所有节点，作为键-值结构。

   映射中的每个条目将表示为：（键：节点索引，值：节点类）

   节点类将包含有关节点的以下详细信息：节点索引、其关联边的数量以及指示当前节点是否已被访问过的标志。

   考虑到映射中的每个条目将仅包含对应于该节点的值，可以说对于给定节点索引从映射中进行的任何读取访问都将是恒定的（即 O(1)）。
   
   

   2.2. 作为在步骤 2.1. 中读取邻接矩阵和构建地图的一部分，起始节点也将被保留。路径的起始节点将由具有最少边数的节点表示。

   如果图中存在多个具有此属性的节点，则将选择索引号最低的节点。在这种情况下，我们可以假设每个节点都有一个与之关联的索引，从零开始：0、1、2 等。
   
   

3. 在步骤 2.2 中标识的起始节点。将被标记为已访问。

4. 其余节点将进行下一步操作。当访问节点的数量等于图中节点的数量时，或者当没有找到当前节点的未访问相邻节点时，循环将结束。

   因此，接下来的步骤将作为此循环的一部分进行：
   
   

   4.1. 第一个操作是寻找下一个要访问的节点。

   要访问的下一个节点必须遵守以下约束：

   • 拥有到当前节点的边
   • 到目前为止还没有被访问过
   • 与当前节点的其他相邻节点相比，具有最少数量的边缘。
     
     

   4.2. 如果没有找到下一个节点，那么算法将结束并指示没有找到哈密顿路径。
   
   

   4.3. 如果找到了下一个节点，则这将代表当前节点。它将被标记为已访问，并且已访问节点的数量将增加。
   
   

5. 如果访问节点的数量等于图中节点的数量，则已找到哈密顿路径。无论哪种方式，都会根据算法的结果显示一条消息。

GitHub 上提供了实现/测试：https : //github.com/george-cionca/hamiltonian-path

我的主要问题是：

1. 是否有无向图会导致该算法无法生成正确的解决方案？
2. 在存储库的页面上，我包含了更多详细信息，并说明此实现提供了二次时间（即 O(n ² )）的解决方案。有没有我没有考虑到时间复杂度的方面？