标签: graph-algorithm

我最初是以两种方式做到的.一种方法是将访问的节点存储在列表中并遍历列表以确定之前是否已访问过节点.另一个是使用布尔数组,它跟踪访问和未访问的节点.它真的让我感兴趣,最好的方法是什么？

如何将旅行商问题的(决定版本)转换为哈密尔顿电路问题(即如何将TSP降低到HCP,如果我有HCP解决方案,那么我将使用该解决方案来解决TSP问题)？

如何使用A star算法查找前100条最短路径？

设G =(V,E)是一个网络,其中s和t是源和接收器.设f为G中的最大流量.找到一个算法,确定G中是否存在唯一的最小割数.

我在这个网站上找到了类似的问题:

确定最小切割的唯一性

在那里给出答案的摘要:

找到残差图中s可到达的所有顶点,我们在G中找到了最小割(S,T).

从t开始,查看相同的残差图.查看箭头反方向可从t到达的顶点组(意味着可以到达t的所有顶点).

这个小组也是一个小切.

如果切割与原始切割相同,那么只有一个.否则,您刚刚发现了2个切口,因此原始切割不可能是唯一的.

我不明白为什么如果切割与原始切割相同,那么切割是独特的.谁可以向我们保证没有其他的减产？

提前致谢

好吧,我知道无向图的广度优先搜索树不能有后沿.但我想知道它怎么能有一个跨界？我无法对由OFS构造的图形G的生成树进行成像,其中包含一个交叉边缘.

我对使用A*和曼哈顿距离度量的网格中的对角线移动感到有些困惑.有人可以解释为什么使用对角线运动使其不可接受吗？不会进行对角线移动找到一个更好的最佳解决方案,因为采取较少的步骤来达到目标​​状态而不是向上向左下方或我错过了什么？

如果满足以下条件,让我们调用n个顶点的无向图p-interesting:

1. 该图包含2n + p个边;
2. 图形不包含自循环和多个边;
3. 对于任何整数k(1≤k≤n),由k个顶点组成的任何子图最多包含2k + p个边.

图的子图是一组图顶点和一组图边.此时,边集必须满足条件:集合中每条边的两端必须属于所选的顶点集.

任务是找到由n个顶点组成的p-interesting图.

要查看问题陈述,请单击此处

我甚至不理解这里解释的教程.

如果有人能指出我背景所需的理论或与这个问题相关的一些模糊定理.我很高兴.

这是我遇到的面试问题:

您将获得一个国家城市之间的飞机地图,基本上有一个有向图,其中权重是城市之间飞机的成本.您还获得了一张优惠券,可以在任何一个航班上获得50%的优惠券.查找您可以在两个城市之间旅行的最低费用？

我在解决BFS问题.我使用的是PriorityQueue,但我得到了错误的答案,然后我使用了LinkedList,我得到了正确的答案.我无法找到它们之间的区别.这是两个代码.为什么两个答案都不同？

Code1:    
        LinkedList q=new LinkedList();
        q.add(src);
        dist[src]=0;
        visited[src]=1;
        while(!q.isEmpty()){
            u=(int)(Integer) q.remove(0);
            for (int k = 0; k < n; k++) {
                if(a[u][k]==1 && visited[k]==0)
                {
                    dist[k]=dist[u]+1;
                    q.add(k);
                    visited[k]=1;
                }   
            }
        }

Code 2: 
    PriorityQueue<Integer> q= new PriorityQueue<>();
        q.add(src);            
        dist[src]=0;
        visited[src]=1;
        while(!q.isEmpty()){
            u=q.remove();               
            for (int k = 0; k < n; k++) {
                if(a[u][k]==1 && visited[k]==0)
                {
                    dist[k]=dist[u]+1;
                    q.add(k);
                    visited[k]=1;
                }   
            }
        }

此外,当我使用Adjacency List而不是Adjacency矩阵时,Priority Queue实现给出了正确的ans.

我正在研究二叉搜索树算法,由于某种原因,我不断收到类型错误.当第二个值插入树中时,总会发生这种情况.特别是当当前节点的值与传入数据值进行比较时

这是代码:

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.leftNode = left;
        this.rightNode = right;
    }
}

class BST {
    constructor() {
        this.root = null;
    }
    insert(data) {
        const dataNode = new Node(data);
        if (this.root === null) {
            this.root = dataNode;
        } else {
            let currentNode = this.root;
            let parentNode;
            while (true) {
                parentNode = currentNode;
                if (data < currentNode.data) {
                    currentNode = parentNode.left;
                    if (parentNode.left === null) {
                        parentNode.left = dataNode
                        break; …