标签: graph-algorithm

我知道Dijkstra的最短路径算法.但是,如果我要对其进行修改,以便不使用贪婪算法找到最短路径,而是找到最长路径.我需要对以下代码做些什么:

这是我使用的:

作为比较函数,在最短路径版本中选择正确的节点:

 if (Cost(potential_node) > Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

然而,为了达到另一方面,这是行不通的:

 if (Cost(potential_node) < Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

有点困惑,真的很感激一些反馈

我希望以最低成本遍历二叉树,其中每个边的成本为1. 当访问树的每个节点时,遍历完成.

例如,跟随树的遍历的最低成本是13.

       *
      / \
     *   *
    / \   \
   *   *   *
  /   /     \
 *   *       *

跟随树的遍历的最低成本是12.

        *
       / \
      *   *
     / \   \
    *   *   *
   /     \
  *       *
 /
*

我正在尝试用C++编写Dijkstra的算法,互联网上有无数的例子,但我似乎无法理解这些例子的工作原理.我宁愿以对我有意义的方式去做,这样我就能更好地理解算法.我知道算法本身应该如何工作,我已经编写了一些代码.我想知道是否有人可以在我的思考过程中指出这个缺陷.我选择将我的图表表示为边缘列表.我会写伪代码,因为我的实际代码是一个巨大的混乱:

class Node{
   vector<node> linkVector;           //links to other nodes, generated at random
   int cost;                     //randomly generated by constructor
   bool visited = false;
}

vector<node> edgelist;           //contains all nodes


int main(){
   create n Nodes
   add all nodes to edgeList
   for each node {
      randomly add WEIGHT nodes to linkVector
   }
findPath(initialNode)
}

int findPath(Node start, node want, int cost=0){   //returns cost from src to dest
if(start==want) return cost;
if(every node has been visited) return 0;        //this is in case of failure …

如果图中只有一个周期,如何找到无向图中的顶点周期？

我有用于在图中查找循环的代码,但是现在我需要能够找到顶点循环的代码.

这是用于查找周期的代码(在C++中):

bool dfs(int x)
{
    state[x] = 1;
    for(int j = 0; j < ls[x].size(); j++)
    {
        if(state[ls[x][j]] == 1 and parent[x] != ls[x][j])
        {
            t = 0; // Graph contains cycle.
            return t;
        }
        if(state[ls[x][j]] == 0)
        {
            parent[ls[x][j]] = x;
            dfs(ls[x][j]);
        }
    }
}

void detect_cycle()
{
    memset(state, 0, sizeof state);
    memset(parent, 0, sizeof parent);
    for(int i = 1; i <= n; i++)
        if(state[i] == false)
            dfs(i);
}

谢谢.

这是最终的代码.多谢你们.

bool dfs(int x)
{
    state[x] = …

我有一个长度为N的数字序列.我将不得不对这个数字序列进行Q操作.

在每次操作中我将给出三个整数P,Q,V与P≤Q≤Ñ并且将减去V从每iᵗʰ整数,其中P≤I≤Q .

每次操作后,我将得到另外两个整数X,Y,X≤Y≤N.我将不得不回答Xᵗʰ和Yᵗʰ(包括)整数之间有多少个整数是正数.

Q将在10 ⁵左右.我将不得不在大约1/2秒内完成所有操作并回答相应的查询.

我应该使用什么算法/数据结构？那个程序会是什么？

注意:我对Segment Trees或Binary Indexed Trees有很好的了解.如果您的解决方案涉及这些数据结构,那将非常棒.

我在接受采访时被问到这个问题.

问题:一个二叉树和相应的子树的高度,也给我们的.然后我们必须按顺序在特定位置找到一个元素.

例如:树结构是:D(根节点)[子树大小= 6] - > B,F(D的子节点)[子树大小= 2] - > A,C,E,G(叶子)节点)[subtree-size = 0].

所以共有3个级别:0级:D; 1级:B,F; 等级2:A,C,E,G

我们必须按顺序计算特定顺序/位置的节点,比如p.如果p = 2,那么节点将是B(按顺序遍历).

我的解决方案:我建议我们需要进行一次遍历遍历(通过BFS/DFS),然后我们可以给出第i个顺序节点,时间复杂度为O(n).

现在我被问到可以根据子树大小信息改进解决方案.但我无法想出子树大小可以减少时间复杂度的任何方式.

子树大小信息可以减少时间复杂度吗？如果是,请分享算法/伪代码.

我正在实施Kruskal的算法.

在以下代码中调用graph()后,节点的值会发生变化.我不太清楚为什么 - 如果有人能清楚这一点,我会非常感激.我没有从图中访问节点的值,并且正在访问的数组的节点和边都被分配到堆栈外部!

struct node {
  int parent, rank;
};
typedef struct node node;

struct edge {
  int fromvertex, tovertex;
  float weight;
};
typedef struct edge edge;

node* nodes;
edge* edges;

typedef enum {Unvisited, Visited} vertexstate;

int main (int argc, char const *argv[])
{
  void getcount(int*, int*);
  void graph(int, int);
  void makeset(int);
  int hasspantree(int, int, int);
  void kruskal(int, int);
  int printmcst(int);
  int nodecount, edgecount, i, totalcost=0;
  getcount(&nodecount, &edgecount);
  for (i = 1; i <= nodecount; i++)
    makeset(i);
  printf("%d \t …

我有一个大的稀疏方阵n和n,它的等级略低于n,比方说m.我希望通过某个规则删除行和列来使其成为非单数形式.规则是如果你删除第i行,你也必须删除第i列,这样矩阵总是方形的.这有效地删除了邻接图中的节点.

我的第一个问题是:是否总是存在这样的nm行和列的组合,我可以将其移除,使得m个子矩阵的剩余m在结构上是非奇异的.

我的第二个问题是:是否存在一种有效的算法来通过p非奇异子矩阵获得ap而不会删除过多的行和列

为了提供更多的上下文,我正在处理的矩阵大约是1000乘1000,稀疏度接近0.05

有向图被称为“ 在-至少-单向连接的 ”如果，对于每两个节点u和v在图中，有两种从路径u到v或从一个路径v到u（或两者）。
是否有O(m + n)解决此问题的时间复杂度算法？

我需要从某个点找到最长的路径（就像多米诺骨牌一样），它可以在文件中显示：

因此，我可以从单元格（0,0）创建的最长的多米诺骨牌是（1,4）点，而不是（3,0）点。

我已经尝试使用dfs解决此问题，并成功找到了整个区域的大小-我不知道如何更改此代码来计算多米诺骨牌的最长路径。

public class Main {

    static int totalRows = 4;
    static int totalCols = 6;
    static int[] rowNbr = {1, -1, 0, 0};
    static int[] colNbr = {0, 0, 1, -1};
    static int count = 0;
    static boolean[][] visited = new boolean[4][6];

    public static void main(String[] args) {
        int mat[][] = {
                {1, 0, 0, 0, 0, 0},
                {1, 1, 1, 1, 1, 0},
                {1, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0}};

        dfs(mat, 0, …