graph - 平行边缘检测

我正在研究一个问题(来自Sedgewick的Algorithms，第4.1节，问题32)以帮助我理解，但我不知道如何进行。

“平行边缘检测。设计一种线性时间算法以对(多)图中的平行边缘进行计数。
提示:维护顶点邻居的布尔数组，并通过仅根据需要重新初始化条目来重用此数组。”

如果两条边连接同一对顶点，则认为两条边平行

有什么想法怎么办？

最佳答案

我认为我们可以为此使用BFS。

主要思想是能够判断两个节点之间是否存在两个或更多路径，因此，我们可以使用一个集合，并查看该集合中是否已存在与某个节点的相邻列表相对应的相邻节点。

这使用了O(n)的额外空间，但具有O(n)的时间复杂度。

boolean bfs(int start){

 Queue<Integer> q = new Queue<Integer>();       // get a Queue
 boolean[] mark = new boolean[num_of_vertices];
 mark[start] = true;                            // put 1st node into Queue
 q.add(start);
 while(!q.isEmpty()){
    int current = q.remove();
    HashSet<Integer> set = new HashSet<Integer>(); /* use a hashset for
                                    storing nodes of current adj. list*/
    ArrayList<Integer> adjacentlist= graph.get(current);   // get adj. list
    for(int x : adjacentlist){
        if(set.contains(x){  // if it already had a edge current-->x
          return true;       // then we have our parallel edge
        }
        else set.add(x);     // if not then we have a new edge

        if(!marked[x]){      // normal bfs routine
            mark[x]=true;
            q.add(x);
        }
    }
 }
}// assumed graph has ArrayList<ArrayList<Integer>> representation
 // undirected

关于graph - 平行边缘检测，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22737978/