graph - 平行边缘检测

Question

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

“平行边检测。设计一个线性时间算法来计算(多)图中的平行边。提示:维护一个顶点邻居的 bool 数组，并通过仅在需要时重新初始化条目来重用该数组。”

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

有什么想法吗？

Answer 1

我认为我们可以为此使用 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