标签: graph-algorithm

我正在使用堆数据结构实现 Dijkstra 算法。我还使用一个数组来跟踪节点的“可能的最小距离”。问题是当我更新数组时，如何更新堆中相应的值？

好的，这是代码

typedef struct temp                       
{
    int nodeTag;    
    int weight; 
    struct temp *next;
}myStruct;  //this structure corresponds to the elements of the linked list 

typedef struct temp *link;

typedef struct
{ 
    int nodeTag;   //each node has an integer nodeTag associated with it
    link l;
}head;    //the head of the elements of the adjacency list

typedef struct {
    head *adjList;
    int numNodes;
    int numEdges;
} Graph;

typedef struct {
    int possibleMinWeight;
    int minFound;    //minFound==1 if true min is found …

我刚刚开始阅读图论，并且正在阅读有关图着色的内容。我的脑海中浮现出这个问题：

我们必须仅用一种颜色对无向图（不完全）进行着色，以便使彩色节点的数量最大化。我们需要找到这个最大数量。我能够制定一种非循环图的方法：

我的方法：首先，我们将图划分为独立的组件，并对每个组件执行此操作。我们创建一个 dfs 树，并在遍历它时创建 2 个 dp 数组，以便根位于最后：

dp[0][u]=sum(dp[1][visited children])

dp[1][u]=sum(dp[0][visited children])

ans=max(dp[1][root],dp[0][root])

dp[0][i] , dp[1][i] are initialized to 0,1 respectively.

这里0表示无色，1表示有色。

但这对于循环图不起作用，因为我假设没有访问过的孩子是连接的。

有人可以指导我如何解决循环图的这个问题（而不是通过暴力）的正确方向吗？是否可以修改我的方法或者我们是否需要提出不同的方法？像为具有最少边缘的节点着色这样的贪婪方法会起作用吗？

抽象问题

我想在完整的加权二分图中找到最佳的最大匹配，其中两组顶点的大小差异很大，即一组顶点非常大，另一组非常小。

匈牙利算法不是解决此问题的好方法，因为它将虚拟顶点添加到较小的集合中，使得两个集合具有相同的大小，因此我失去了其中一个顶点集合非常小的所有潜在效率增益。

更具体地说

我已将对象（边界框）分为两组，并且有一个相似性度量（杰卡德重叠）来衡量任意两个对象的相似程度。我想产生两个集合之间的匹配，使得所有单独匹配的相似度之和最大。

问题在于，其中一组仅包含很少的对象，例如 10 个，而第二组非常大，例如 10,000 个对象。第一组中的 10 个对象中的每一个都需要与第二组中的 10,000 个对象中的一个进行匹配。

两组大小的不对称让我想知道如何有效地做到这一点。我无法使用匈牙利算法生成 10,000 x 10,000 矩阵。

我对以下算法的时间复杂度感到困惑，它是 O(V) 还是 O(V+E)？

DFS(G,s,t):


vis[s] = true
        if s == t
            vis[s] = false, return 1
        cont = 0
        for v is adj(s)
            if vis[v] == false
                cont = cont + DFS(G,s,t)
        vis[s] = false
        return cont

我有一个通过 BFS 迭代整个图的算法，它将更新分数以找到所有节点的最小值。而且我相信它的运行时复杂度是 O(V+E)，我相信它比 Dijkstra 更好。现在显然我还不够天真，认为这个算法是正确的。但是，我很好奇在哪种情况下，这不会找到最佳最小路径。这是我的代码

from queue import Queue

ad_list = {
    'A': {'B': 1, 'D': 3},
    'B': {'A': 1, 'D': 1, 'C': 5},
    'D': {'A': 3, 'B': 1, 'C': 3},
    'C': {'B': 5, 'D': 3}
}

min_weights = {
    'A': 0,
    'B': float('inf'),
    'C': float('inf'),
    'D': float('inf'),

}


def fake_dijkstra(ad_list):
    queue = Queue()
    queue.put('A')

    visited = {}

    global min_weights

    while not queue.empty():
        key = queue.get()

        # update score
        children = ad_list[key]

        for child_key, value in children.items():
            if min_weights[child_key] …

我有一个由用户创建的有向无环图，其中图的每个节点（顶点）代表对某些数据执行的操作。节点的输出取决于其输入（显然），并且该输入由其父节点提供。然后输出将传递给其子级。保证不存在循环，因此可以忽略。

该图的工作原理与Blender 中的着色器编辑器相同。每个节点对其输入执行一些操作，并且该操作的成本可能任意高。因此，我只想在严格要求时评估这些操作。

当通过用户输入或其他方式更新节点时，我需要重新评估每个节点，这取决于更新节点的输出。但是，鉴于我无法证明多次评估同一节点的合理性，我需要一种方法来确定更新节点的正确顺序。基本的广度优先遍历并不能解决问题。要了解原因，请考虑此图：

传统的广度优先遍历将导致D在 之前进行评估B，尽管D依赖于B。

我尝试过反向进行广度优先遍历（即从O1和O2节点开始，向上遍历图形），但我似乎遇到了同样的问题。反向广度优先遍历将访问Dbefore B，因此I2before A，导致I2被排序在 after A，尽管A取决于I2。

我确信我在这里遗漏了一些相对简单的东西，而且我觉得反向遍历似乎是关键，但我似乎无法全神贯注并让所有部分都适合。我认为一个潜在的解决方案是按预期使用反向遍历，但不是避免多次访问每个节点，而是在每次出现时访问每个节点，确保它具有绝对正确的顺序。但是多次访问每个节点以及随之而来的指数扩展是一个非常没有吸引力的解决方案。

对于此类问题是否有众所周知的有效算法？

Qt中是否有图形数据结构的实现,内置节点和边的默认操作？

给定一个无向图和图中的两个任意节点(A和B),如何找到通过大量唯一节点的路径,以便在节点A和B之间导航？

我知道你可以深入搜索并比较所有长度,但有更好的方法吗？

我正在努力解决这个算法问题:

我如何编写一个theta(m+n)算法来打印m边,n-顶点有向图中每个顶点的入度和出度,其中有向图用相邻列表表示.

我有对(a1,b1),(a2,b2).....(an,bn)我想生成所有2 ^ n列表.使用递归这很容易,就像找到字符串的所有排列,但我想迭代地做.请建议我这样做的方法.

要清楚列表的第一个位置可以是a1或b1,第二个位置可以是a2或b2 ..第i个位置可以是ai或bi ....第n个位置将是a或bn.

示例:(a1 a2 .... an)(b1 b2 ..... bn)(b1 a2 ... an)(a1 b2 ..... an)(所有2 ^ n列表)

这是n = 3的示例递归代码.

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

void compute( int a[][2],int i,vector<int> v)
{
    if(i==3)
    {
        for(int j=0;j<v.size();j++)
            cout<<v[j]<<" ";
        cout<<endl;
        return;
    }

    for(int j=0;j<=1;j++)
    {
        if(j==1) v.pop_back();
        v.push_back(a[i][j]);
        compute(a,i+1,v);
    }
}

int main()
{
   float ans=0;
   int a[3][2];
   for(int i=0;i<=2;i++)
   {
       for(int j=0;j<=1;j++)
        cin>>a[i][j];
    }
    vector <int> v;
    compute(a,0,v); …