检查两个顶点是否连接

Question

可能重复：
How can I search a graph for a path?

我想知道什么是最好的办法是在一个与那些指他们的邻居对象的图形“，但其中我还有一个概述（一个包含坐标上的对象的散列图），以确定这些对象中的两个是否连接。

我读过Dijkstra可能效率不高，我读了BFS和DFS。

从我的理解BFS可能会接近我所需要的，我可以做得更好吗？有没有更常见的解决方法？也许更容易？时间复杂度确实起到了作用:)

Answer 1

检查这个代码在Java中，当你得到的邻接矩阵，你看是否节点连接：

import java.util.*; 

public class myListGraph 
{ 
    protected String[] names; // 1-d array to store the vertices 
    protected StringLinkList[] Edges; // 1-d array to store adjacencies between vertices, 
    protected int numVertices; 
    protected int numEdges; 

    // Default constructor. Sets aside enough capacity for one vertex 
    public myListGraph()  
    {   
     this(1); 
    } 

    // Constructor that sets aside as much capacity as specified by the user 
    public myListGraph(int capacity)  
    {   
     names = new String[capacity]; 
     Edges = new StringLinkList[capacity]; 
     for (int i = 0 ; i < capacity ; i ++) { 
      Edges[i] = new StringLinkList(); 
     } 

    } 

    public int numberOfVertices() 
    { 
       return numVertices; 
     } 

     public int numberOfEdges() 
     { 
       return numEdges; 
     } 

    // Finds the location at which a vertex is stored in Vertices. 
    // Returns -1 if vertex not found 
    public int getIndex(String vertex) 
    { 
     for(int i = 0; i < numVertices; i++) 
      if(vertex.equals(names[i])) 
       return i; 

     return -1; 
    } 

    // Resizes the array of vertices. Can make it larger or smaller, depending 
    // on what newSize is. 
    protected String[] resize(String[] array, int newSize) 
    { 
     String[] temp = new String[newSize]; 

     int smallerSize = newSize; 
     if(array.length < smallerSize) 
      smallerSize = array.length; 

     for(int i = 0; i < smallerSize; i++) 
      temp[i] = array[i]; 

     return temp; 
    } 

    // Resizes the array of Edges. Can make it larger or smaller, depending 
    // on what newSize is. 
    protected StringLinkList[] resize (StringLinkList[] array, int newSize) 
    { 
     StringLinkList[] temp = new StringLinkList[newSize]; 

     int smallerSize = newSize; 
     if(array.length < smallerSize) 
      smallerSize = array.length; 

     for(int i = 0; i < smallerSize; i++) 
      temp[i] = array[i]; 

     for (int i = smallerSize ; i < temp.length ; i ++) 
      temp [i] = new StringLinkList(); 

     return temp; 
    } 

    // Adds a new vertex 
    public void addVertex(String newVertex) 
    { 
     if(getIndex(newVertex) != -1) 
     { 
      System.out.print("addVertex: "); 
      System.out.print(newVertex); 
      System.out.println(" failed -- vertex already exists."); 
      return; 
     } 

     // if array of vertices is full, we need to expand it and 
     // also expand Edges 
     if (names.length == numVertices) 
     { 
      names = resize(names, 2*numVertices+1); 
      Edges = resize(Edges, 2*numVertices+1); 
     } 

     names[numVertices++] = newVertex; 
    } 


    // Adds a new edge 
    public void addEdge(String vertex1, String vertex2) 
    { 
     int i = getIndex(vertex1); 
     if(i == -1) 
     { 
      System.out.print("addEdge failed: "); 
      System.out.print(vertex1); 
      System.out.println(" does not exist."); 
        return; 
      } 

     int j = getIndex(vertex2); 
     if(j == -1) 
     { 
      System.out.print("addEdge failed: "); 
      System.out.print(vertex2); 
      System.out.println(" does not exist."); 
        return; 
      } 

     Edges[i].insertFirst(names[j]); 
     Edges[j].insertFirst(names[i]); 


     numEdges++; 
    } 

    // Prints the neighbors of the given vertex 
    public void printAdjacencyList (String vertex) 
    { 
     int i = getIndex(vertex); 
     if(i == -1) 
     { 
      System.out.print("addEdge failed: "); 
      System.out.print(vertex); 
      System.out.println(" does not exist."); 
        return; 
      } 

     System.out.print (vertex + " is connected to "); 
     Edges [i].displayList();   
    } 


     // returns the names of all the neighbors of a given vertex in a 
    // String array 
     public String[] getNeighbors(String vertex) 
     { 
       int source = getIndex(vertex); 
       if(source == -1) 
       { 
         System.out.print("getNeighbors failed: Vertex "); 
         System.out.print(vertex); 
         System.out.println(" does not exist."); 
         return null; 
       } 

     return Edges[source].copyIntoArray(); 
     } 

     // returns the indices of all the neighbors of a given vertex. The 
     // vertex is specified as an index and the neighbors are returned 
    // in an int array 
     public int[] getNeighbors(int index) 
     { 
       if((index < 0) || (index >= numVertices)) 
       { 
         System.out.print("getNeighbors failed: Index"); 
         System.out.print(index); 
         System.out.println(" is out of bounds."); 
         return null; 
       } 

     // Call the earlier getNeighbors function to get the names of 
     // neighbors 
       String[] nbrNames = getNeighbors(names[index]); 

     // Turn the array of neighbor names into an array 
     // of neighbor indices 
     int[] nbrIndices = new int[nbrNames.length]; 
     for(int i = 0; i < nbrIndices.length; i++) 
      nbrIndices[i] = getIndex(nbrNames[i]); 

     return nbrIndices; 
     } 



     // returns the degree of a vertex with given name 
     public int degree(String vertex) 
     { 
       // Get the index of the vertex 
       int i = getIndex(vertex); 
       if(i == -1) 
       { 
         System.out.print("In degree: "); 
         System.out.print(vertex); 
         System.out.println(" does not exist."); 
         return -1; 
       } 

       // Call the other degree function that returns the degree 
       // of a vertex, given its index 
       return degree(i); 
     } 

     // returns the degree of a vertex with given index 
     public int degree(int index) 
     { 
     return Edges[index].size(); 

     } 

    // Boolean method that tells us if {v1, v2} is an edge in the graph 
    public boolean isEdge(String vertex1, String vertex2) 
    { 
       int i = getIndex(vertex1); 
       if(i == -1) 
       { 
         System.out.print("isEdge failed: "); 
         System.out.print(vertex1); 
         System.out.println(" does not exist."); 
         return false; 
       } 

       int j = getIndex(vertex2); 
       if(j == -1) 
       { 
         System.out.print("isEdge failed: "); 
         System.out.print(vertex2); 
         System.out.println(" does not exist."); 
         return false; 
       } 

     // if vertex2 exists in the adjacency list of 
     // vertex1, then return true 
     return (Edges[i].find(vertex2) != null); 
    } 


    // Computes the clustering coefficient of a vertex. This is the 
    // version that takes a vertex index as argument. 
    public double clusteringCoefficient(int i) 
    { 

     // Copy the adjacency list into an array, for easy access 
     // copyIntoArray is a new method in the GenericLinkList class 
     String[] temp = Edges[i].copyIntoArray(); 

     // initialize edges-in-neighborhood to 0 
     int edgesInNbd = 0; 

     // Scan pairs of neighbors and increment counter whenever 
     // there is an edge 
     for(int j = 0; j < temp.length; j++) 
      for(int k = 0; k < j; k++) 
       if(isEdge(temp[j], temp[k])) 
        edgesInNbd++; 

     // if there are no neighbors or one neighbor then, clustering 
     // coefficient is trivially defined to be 1. Otherwise, 
     // compute the ratio of number of edges in neighborhood to 
     // the total number of pairs of neighbors 
     if(temp.length <= 1) 
      return 1; 
     else 
      return edgesInNbd*2.0/(temp.length*(temp.length-1)); 

    } 

     // Computes the clustering coefficient of a vertex. This is the 
     // version that takes a vertex name as argument. 
     public double clusteringCoefficient(String v) 
     { 
       int i = getIndex(v); 
       if(i == -1) 
       { 
         System.out.print("clusteringCoefficient failed: "); 
         System.out.print(v); 
         System.out.println(" does not exist."); 
         return 0; 
       } 

     return clusteringCoefficient(i); 
    } 

    // Computes the clustering coefficient of the entire graph 
    // added on 2/23 
    public double clusteringCoefficient() 
    { 
     double sum = 0; 
     for(int i = 0; i < numVertices; i++) 
      sum = sum + clusteringCoefficient(i); 

     return sum/numVertices; 
    }  

    // Checks whether the graph is connected or not by calling breadthFirstSearch 
    public boolean isConnected() 
    { 
     // Perform breadth first search 
     int[] bfsTree = breadthFirstSearch(names[0]); 

     // Scan the bfsTree array, looking for -1. The graph 
     // is not connected if there is -1 in this array 
     for(int i = 0; i < bfsTree.length; i++) 
      if(bfsTree[i] == -1) 
       return false; 

     return true; 
    } 


    // Returns a 2-d array of vertex names representing the connected components 
    // of the graph. Each row in the 2-d array is a connected component. 
    public String[][] connectedComponents() 
    { 
     // The maximum number of connected components equals the number 
     // of vertices; so start by allocating this many rows. 
     String[][] cc = new String[numVertices][]; 

     // Keeps track of which vertices have been visited by repeated 
     // calls to bfs 
     boolean[] visited = new boolean[numVertices]; 
     for(int i = 0; i < numVertices; i++) 
      visited[i] = false; 

     // Keeps track of the number of vertices have been visited by repeated 
     // calls to bfs 
     int numVisited = 0; 

     // Keeps track of the number of connected components 
     int numComponents = 0; 

     // Repeat bfs until all vertices have been visited 
     while(numVisited < numVertices) 
     { 
      // Scan visited until an unvisited vertex is found 
      // and start bfs at that source 
      int source; 
      for(source = 0; source < numVisited; source++) 
       if(!visited[source]) 
        break; 

      // Compute the bfsTree starting at this source 
      int[] bfsTree = breadthFirstSearch(names[source]); 

      // Scan bfsTree to count number of newly visited vertices 
      int countNewVisited = 0; 
      for(int i = 0; i < numVertices; i++) 
       if(bfsTree[i] != -1) 
        countNewVisited++; 

      // Allocate a row of size countNewVisited in the current row of 
      // cc to store the new connected component 
      cc[numComponents] = new String[countNewVisited]; 

      // Scan bfsTree again, this time to copy the newly visited 
      // vertices into cc and set them as visited 
      countNewVisited = 0; 
      for(int i = 0; i < numVertices; i++) 
       if(bfsTree[i] != -1) 
       { 
        cc[numComponents][countNewVisited++] = names[i]; 
        visited[i] = true; 
       } 

      // Update numVisited  
      numVisited = numVisited + countNewVisited; 

      // Update numComponents 
      numComponents++; 

     } // end while 

     // Resize cc to have exactly as mamy rows as numComponents 
     String[][] newCC = new String[numComponents][]; 
     for(int i = 0; i < numComponents; i++) 
      newCC[i] = cc[i]; 

     return newCC; 


    } 

    // Computes a shortest path (in hops) from source to destination. Does 
    // this by simply calling breadthFirstSearch and following the parent 
    // pointers in the BFS tree. If the source and destination are not in 
    // the same component, returns null. Otherwise, returns a String array 
    // of vertices in a shortest path 
    public String[] shortestPath(String source, String dest) 
    { 
     // Get index of source 
     int sourceIndex = getIndex(source); 
       if(sourceIndex == -1) 
       { 
         System.out.print("breadthFirstSearch failed: "); 
         System.out.print(source); 
         System.out.println(" does not exist."); 
         return null; 
       } 

     // Get index of destination 
       int destIndex = getIndex(dest); 
       if(destIndex == -1) 
       { 
         System.out.print("breadthFirstSearch failed: "); 
         System.out.print(dest); 
         System.out.println(" does not exist."); 
         return null; 
       } 

     // Perform a BFS from destination 
     int[] bfsTree = breadthFirstSearch(destIndex); 

     // If source is unreachable from destination 
     if(bfsTree[sourceIndex] == -1) 
      return null; 

     // Define a String[] for shortest path and place the source vertex 
     // in it 
     String[] path = new String[numVertices]; 
     path[0] = names[sourceIndex];  

     // Start following parent pointers and store each new vertex 
     // encountered, in the path array. The while-loop executes 
     // until the root of the BFS tree is encountered 
     int currentIndex = sourceIndex; 
     int pathLength = 0; 
     while(currentIndex != bfsTree[currentIndex]) 
     { 
      currentIndex = bfsTree[currentIndex]; 
      pathLength++; 
      path[pathLength] = names[currentIndex]; 
     } 

     // Resize the path array to be exactly of the correct size 
     String[] newPath = new String[pathLength + 1]; 
     for(int i = 0; i < newPath.length; i++) 
      newPath[i] = path[i]; 

     return newPath; 
    } 

    // Breadth first search function that takes a vertex name as argument; 
    // returns a breadth first search tree 
    // stored in an array of integers with the entry in slot i containing 
    // the index of the parent of the vertex with index i 
    // parent of source is itself; unvisited nodes have parent -1 
    public int[] breadthFirstSearch(String source) 
    { 
      int sourceIndex = getIndex(source); 
       if(sourceIndex == -1) 
       { 
         System.out.print("breadthFirstSearch failed: "); 
         System.out.print(source); 
         System.out.println(" does not exist."); 
         return null; 
       } 

     return breadthFirstSearch(sourceIndex); 
    } 


    // Breadth first search function that takes a vertex index as argument; 
    // returns a breadth first search tree 
    // stored in an array of integers with the entry in slot i containing 
    // the index of the parent of the vertex with index i 
    // parent of source is itself; unvisited nodes have parent -1 
    public int[] breadthFirstSearch(int sourceIndex) 
    { 
     // Initialize the bfsTree array; the entry -1 means 
     // not yet visited. 
     int[] bfsTree = new int[numVertices]; 
     for(int i = 0; i < numVertices; i++) 
      bfsTree[i] = -1; 

     // The parent of the tree root is itself 
     bfsTree[sourceIndex] = sourceIndex; 

     // Then initialize the visited array 
     boolean[] visited = new boolean[numVertices]; 
     for(int i = 0; i < numVertices; i++) 
      visited[i] = false; 

     visited[sourceIndex] = true; 

     // Then initialize the queue 
     Queue Q = new Queue(numVertices); 
     Q.enqueue(sourceIndex); 

     while(!Q.isEmpty()) 
     { 
      // get the index of the vertex first in line 
      int current = Q.dequeue(); 

      // Get the indices of the neighbors of the current vertex 
      int[] neighbors = getNeighbors(current); 

      // Scan the neighbors 
      for(int i = 0; i < neighbors.length; i++) 
      { 
       // Get the index of the current neighbor 
       int currentNeighbor = neighbors[i]; 

       // Check if the neighbor is new, i.e., not visited 
       // If so, mark the neighbor as visited, enqueue the neighbor, and 
       // set the neighbor's parent in bfsTree 
       if(!visited[currentNeighbor]) 
       { 
        visited[currentNeighbor] = true; 
        Q.enqueue(currentNeighbor); 
        bfsTree[currentNeighbor] = current; 
       } 

      } // end-scanning neighbors 

     } // end-while Q is not empty 

     return bfsTree; 

    } 


} // end of class