检查两个顶点是否相连

Question

可能的重复：
如何在图表中搜索路径？

我想知道在“图表”中最好的方法是什么，其中的对象确实引用了它们的邻居，但我也有一个概述（带有坐标上的对象的哈希图），以确定其中两个对象是否连接。

我读到 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