java - 查找给定节点之间的最大边

Question

有一个（双向或双向）图。我的任务是根据下图找到两个给定节点6和9之间的最大边。6 和 9 之间有两条路径。我必须选择最长的路径6-1-3-5-9。但是我的代码是为了找到给定节点之间的最短路径而编写的，它给了我结果6-1-3-9。那么，我如何更改代码以找到最长的路径。

图形图像

我正在使用此链接中的代码minimum-number-of-edges-between-two-vertices-of-a-graph

import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

class Test {
  // Method for finding minimum no. of edge
  // using BFS
  static int minEdgeBFS(Vector<Integer> edges[], int u, int v, int n) {
    // visited[n] for keeping track of visited
    // node in BFS
    Vector<Boolean> visited = new Vector<Boolean>(n);

    for (int i = 0; i < n; i++) {
      visited.addElement(false);
    }

    // Initialize distances as 0
    Vector<Integer> distance = new Vector<Integer>(n);

    for (int i = 0; i < n; i++) {
      distance.addElement(0);
    }

    // queue to do BFS.
    Queue<Integer> Q = new LinkedList<>();
    distance.setElementAt(0, u);

    Q.add(u);
    visited.setElementAt(true, u);
    while (!Q.isEmpty()) {
      int x = Q.peek();
      Q.poll();

      for (int i = 0; i < edges[x].size(); i++) {
        if (visited.elementAt(edges[x].get(i))) continue;

        // update distance for i
        distance.setElementAt(distance.get(x) + 1, edges[x].get(i));
        Q.add(edges[x].get(i));
        visited.setElementAt(true, edges[x].get(i));
      }
    }
    return distance.get(v);
  }

  // method for addition of edge
  static void addEdge(Vector<Integer> edges[], int u, int v) {
    edges[u].add(v);
    edges[v].add(u);
  }

  // Driver method
  public static void main(String args[]) {
    // To store adjacency list of graph
    int n = 11;
    Vector<Integer> edges[] = new Vector[11];

    for (int i = 0; i < edges.length; i++) {
      edges[i] = new Vector<>();
    }

    addEdge(edges, 0, 1);
    addEdge(edges, 1, 2);
    addEdge(edges, 1, 7);
    addEdge(edges, 1, 6);
    addEdge(edges, 2, 8);
    addEdge(edges, 3, 1);
    addEdge(edges, 3, 4);
    addEdge(edges, 3, 9);
    addEdge(edges, 5, 3);
    addEdge(edges, 5, 9);
    addEdge(edges, 8, 10);
    int u = 6;
    int v = 9;
    System.out.println(minEdgeBFS(edges, u, v, n));
  }
}

标签： javaalgorithmgraphbreadth-first-search

Answer 1

“我的任务是找到两个给定节点之间的最大边”

这个问题是NP 难的，基本上，检查所有可能的路径是你最知名的算法。

但是，您必须定义一个节点是可以多次使用还是只能使用一次。然后，使用回溯，使用 aSet<Node or Edge>来了解何时访问了一条边（如果可以多次访问节点）或节点（如果不能访问）。

同时Set，保持回溯中的最大值（只有当你到达目的节点时）才能知道答案。

下一个代码从双向边图中的两个点计算哈密顿量

package com.computermind.sandbox.algorithms;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Hamilton {

    public static void main(String... args) {
        Graph g = new Graph();
        g.addEdge(6, 1);
        g.addEdge(7, 1);
        g.addEdge(2, 1);
        g.addEdge(3, 1);
        g.addEdge(2, 8);
        g.addEdge(8, 10);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(3, 9);
        g.addEdge(9, 5);
        System.out.println(g.hamiltonian(6, 9));
    }

    static class Graph {
        private Map<Integer, Set<Integer>> edges = new HashMap<>();

        private void _addEdge(int a, int b) {
            if (!edges.containsKey(a))
                edges.put(a, new HashSet<>());
            edges.get(a).add(b);
        }

        public void addEdge(int a, int b) {
            _addEdge(a, b);
            _addEdge(b, a);
        }

        // assume nodes could be used many times, edges only once
        public List<Integer> hamiltonian(int a, int b) {
            List<Integer> solution = new ArrayList<>();
            for (int z : edges.get(a))
                hamiltonian(b, new Edge(a, z), new HashSet<>(), new ArrayList<>(), solution);
            solution.add(0, b);
            return solution;
        }

        // recursion with backtracking
        private void hamiltonian(int b, Edge edge, Set<Edge> visited, List<Integer> path, List<Integer> best) {
            // if this edge is not visited, visit
            if (!visited.contains(edge)) {
                // has been visited
                visited.add(edge);
                // add the source node
                path.add(0, edge.a);
                // if destination node is the final node check solution
                if (edge.b == b) {
                    // if you need all longest paths you could accumulate
                    if (path.size() > best.size()) {
                        best.clear();
                        best.addAll(path);
                    }
                }
                // even if it is the final node you must go forward since it could be a cross node
                for (int z : edges.get(edge.b))
                    hamiltonian(b, new Edge(edge.b, z), visited, path, best);
                // backtracking
                path.remove(0);
                visited.remove(edge);
            }
        }

        // WARN bidirectional edges
        static class Edge {
            int a; // from
            int b; // to

            public Edge(int a, int b) {
                this.a = a;
                this.b = b;
            }

            // max/min should be considered to be a->b equals than b->a
            @Override
            public int hashCode() {
                return 7 * Math.min(a, b) + Math.max(a, b);
            }

            @Override
            public boolean equals(Object obj) {
                if (!(obj instanceof Edge))
                    return false;
                Edge o = (Edge) obj;
                return Math.min(a, b) == Math.min(o.a, o.b) && Math.max(a, b) == Math.max(o.a, o.b);
            }
        }
    }
}

带输出

[9、5、3、1、6]