c++ - BFS 与 Dijkstra 的运行时间，值没有意义

Question

我正在对邻接列表和邻接矩阵进行 Dijkstra 和 BFS 的比较。我正在测试所有四种变体作为最短路径算法，并计算它们在从稀疏到密集的未加权图上的运行时间。

我的理解是，邻接表应该在稀疏图上表现更好(即具有更快的时钟时间)，并且随着图变得更密集，矩阵最终将成为更快的实现。但是，当我运行我的代码时，矩阵的性能总是优于列表，而我终究无法理解其中的原因。任何见解将不胜感激。

// main.cpp

#include <iostream>
#include <fstream>
#include "Graph.h"
#include <sys/time.h>
#include <ctime>
#include <chrono>


using namespace std;

int main(int argc, char *argv[]) {
    //struct timeval begin, finish;

    int numVertices = 10;

    //Calculate the maximum number of edges that can exist in an undirected graph
    int maxNumEdges = (numVertices*(numVertices-1))/2;
    cout << "maxNumEdges" << maxNumEdges << endl;

    //Run all the algorithms with increasing number of edges
    for(int i = 0; i < maxNumEdges; i++) {
        int numEdges = i;
        Graph g(numVertices);
        cout <<  "Number of edges: " << numEdges << endl;

        g.generate(numEdges);
        int destination = g.getDestination();

        std::chrono::steady_clock::time_point begin1 = std::chrono::steady_clock::now();
        g.adjListBFS(0, destination);
        std::chrono::steady_clock::time_point end1= std::chrono::steady_clock::now();

        std::chrono::steady_clock::time_point begin2 = std::chrono::steady_clock::now();
        g.matrixBFS(0, destination);
        std::chrono::steady_clock::time_point end2= std::chrono::steady_clock::now();


        std::chrono::steady_clock::time_point begin3 = std::chrono::steady_clock::now();
        g.dijkstraList(0, destination);
        std::chrono::steady_clock::time_point end3= std::chrono::steady_clock::now();


        std::chrono::steady_clock::time_point begin4 = std::chrono::steady_clock::now();
        g.dijkstraMatrix(0, destination);
        std::chrono::steady_clock::time_point end4= std::chrono::steady_clock::now();
        //cout << endl;

        cout << "BfSList Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end1 - begin1).count() << " ";
        cout << "BFS Matrix Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end2 - begin2).count() << " ";
        cout << "DijList Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end3 - begin3).count() << " ";
        cout << "DijMatrix Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end4 - begin4).count() << " ";
        cout << endl;

        //break;

    }

}

//图表.cpp

#include "Graph.h"
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <stdlib.h>
#include <vector>
#include <list> 
#include <limits>
#include <algorithm>

using namespace std;

//Constructor
Graph::Graph(int numV) {
    numVertices = numV;

    //intialize vertex array
    vertexArray = new int[numVertices];
    //Initialize adjacency list
    adjList = new list<int>[numVertices];
    //Initialize matrix
    matrix = new int*[numVertices];
    for(int i = 0; i < numVertices; i++) {
        matrix[i] = new int[numVertices];
    }
    for(int i = 0; i < numVertices; i++) {
        for(int j = 0; j < numVertices; j++) {
        matrix[i][j] = 0;   
        }
    }
}


//Generate a random graph
void Graph::generate(int numEdges) {
    srand(time(NULL));
    int currentEdges = 0;
    int v1 = rand() % numVertices-1;

    //Pick destination vertex. If 0 randomly generated, just add 1 to it
    int dest = rand() % numVertices;
    if (dest != 0) {
        destination = dest;
    } else {
        destination = 1;
    }

    while(currentEdges < numEdges) {
        //cout << "stuck in generate while" << endl;
        for(int i = 0; i < numVertices; i++) {
            //cout << "Stuck in first for loop" << endl;
            v1 = rand() % numVertices;
            if (edgeExists(i, v1) == true || i == v1) {
                //cout << "hit if" << endl;
                //i--;
            } else {
                adjList[i].push_back(v1);
                adjList[v1].push_back(i);
                matrix[i][v1] == 1;
                matrix[v1][i] == 1;
                currentEdges++;
                //cout << "Hit else" << endl;
            //cout << "Added " << i << " to " << v1 << " list" << endl;
            //cout << "Added " << v1 << " to " << i << " list" << endl;
            }
        }
    }
}


//Checking to be sure edge is not added twice
bool Graph::edgeExists(int v1, int v2) {
    bool alreadyAdded = false;
    for(list<int>::iterator i = adjList[v1].begin(); i != adjList[v1].end(); ++i) {
        //cout << "(*i): " << (*i) << " v2: " << v2 << endl;
        if(*i == v2) {
            alreadyAdded = true;
        } 
    }
    return alreadyAdded;
}

//In list already - make sure correct number of vertices are created
bool Graph::inList(int v1) {
    bool check = false;
    for(vector<int>::iterator i = vectorVertex.begin(); i != vectorVertex.end(); ++i) {
        if((*i) == v1) {
            check = true;
        }   
    }
    return check;
}

//================================================BFS with adjacency list====================================================
void Graph::adjListBFS(int s, int e){ 
    int nodesVisited = 0;
    bool foundDest = false;
    bool *visited = new bool[numVertices];
    int *previous = new int[numVertices];
    int start = s;
    int dest = e;

    //Initialize vertices to 'not visited'
    for(int i = 0; i < numVertices; i++) {
        visited[i] = false;
    }

    //Create a queue, push starting vertex on
    queue<int> Q;
    visited[s] = true;
    Q.push(s);
    //cout << "BFS complete traversal: ";

    while(!Q.empty() && foundDest == false) {
            s = Q.front();
            Q.pop();
        //  cout << s << " -> ";
            nodesVisited++;
            for(list<int>::iterator i = adjList[s].begin(); i != adjList[s].end(); ++i) {
                if(!visited[*i]) {
                    visited[(*i)] = true;
                    Q.push(*i);
                    previous[(*i)] = s;

                    if((*i) == e) {
                        foundDest = true;
                        //cout << e << endl;
                        break;
                    }
                } 
            }
     }
    vector<int> pathVector;
    //bool check = false;
    //printPath(previous, e);
    //cout << "Backwards path: " << e << " <- ";
   /*   for(int i = 0; i < numVertices; i++) {
        cout << previous[e] << " <- ";
        if(previous[e] == start) {
            break;
        } else {
            e = previous[e];
        }
    }*/

    /*pathVector.push_back(start);
    for(vector<int>::iterator i = pathVector.end(); i != pathVector.begin(); --i) {
        cout << pathVector.at(*i) << " -> ->  " ;
    }*/

    //cout << endl;
            //  cout << "stuck in BFS adjlist" << endl;

}

//====================================================BFS with Matrix===========================================================


void Graph::matrixBFS(int s, int e){ 
    bool foundDest = false;
    bool *visited = new bool[numVertices];

    //Initialize vertices to 'not visited'
    for(int i = 0; i < numVertices; i++) {
        visited[i] = false;
    }

    //Create a queue, push starting vertex on
    queue<int> Q;
    visited[s] = true;
    Q.push(s);

    //While there are still vertices to process
     while(!Q.empty() && foundDest == false) {
            s = Q.front();
            Q.pop();
            //cout << s << " -> ";

            for(int i = 0; i < numVertices; i++) {
                if(matrix[i][s] == 1 && visited[i] == false) {
                    visited[i] = true;
                    Q.push(i);
                } 
                if(s == e) {
                foundDest = true;
                break;
            }
            }
     }
    //cout << endl;


}

//For reconstructing the path 
void Graph::printPath(int parent[], int j) {
    if (parent[j] == -1) {
        return;
    }

    printPath(parent, parent[j]);
    //cout << j << "->" << endl;
    //cout << " ";
}



//======================================================Dijkstra Matrix============================================================
void Graph::dijkstraMatrix(int s, int e) {
    bool foundDest = false;
    int infinity = numeric_limits<int>::max();
    int distance[numVertices];
    bool visited[numVertices];
    int parent[numVertices];

    for(int i = 0; i < numVertices; i++) {
        parent[i] = -1;
        distance[i] = infinity;
        visited[i] = false;
    }

    //Distance from starting vertex to itself is 0
    distance[s] = 0;

    //Create a queue, push first element on
    queue<int> dijQueue;
    dijQueue.push(s);

    while(!dijQueue.empty() && foundDest == false) {
        int current = dijQueue.front();
        dijQueue.pop();
        visited[current] = true;

            for (int i = 0; i < numVertices; i++) {
                if(!visited[i] && matrix[current][i] && distance[current]+matrix[s][i] < distance[i]) {
                    parent[i] = current;
                    distance[i] = distance[current] + 1;
                    if(s == e) {
                        foundDest = true;
                        break;
                    }
                    dijQueue.push(i);
                }
            }   
    }

/*  int startVertex = 0;
    //cout << "Path" << " " << "Vertex" << " " << "Distance" << endl;
    for (int i= 1; i < numVertices; i++) {
        printPath(parent, i);
        //cout << "    " << startVertex << "-->" << i << "   " << "        " << endl;   
    }*/
                    //  cout << "stuck in Dijkstra Matrix" << endl;

}

//==================================================Dijkstra Adjacency List============================================================
void Graph::dijkstraList(int s, int e) {
    bool foundDest = false;
    int infinity = numeric_limits<int>::max();
    int distance[numVertices];
    bool visited[numVertices];
    int parent[numVertices];

    //Initialize
    for(int i = 0; i < numVertices; i++) {
        parent[i] = -1;
        distance[i] = infinity;
        visited[i] = false;
    }

    //Distance from starting vertex to itself is 0
    distance[s] = 0;

    //Create a queue, push first element on
    queue<int> dijQueue;
    dijQueue.push(s);

    //While there are still vertexes to process
    while(!dijQueue.empty() && foundDest == false) {
        int current = dijQueue.front();
        dijQueue.pop();
        visited[current] = true;

            //cout << "current: " << current << endl;

        for(list<int>::iterator i = adjList[current].begin(); i != adjList[current].end(); ++i) {

            if(!visited[*i] && (distance[current]+1) < distance[*i]) {
                parent[*i] = current;
                distance[*i] = distance[current] + 1;
                if(s == e) {
                    foundDest = true;
                    break;
                }
                dijQueue.push(*i);
            }
        }
    }

    //Print results
    int startVertex = 0;
    //cout << startVertex << " ";
    //printPath(parent, e);
                            //cout << "stuck in Dijkstra List" << endl;


}

//Returns the "ending" vertex that was randomly generated
int Graph::getDestination() {
    return destination;
}

//图.h

#ifndef GRAPH_H_
#define GRAPH_H_
#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <fstream>

using namespace std;

class Graph {

    private:
        int numVertices;
        list<int> *adjList;
        int *vertexArray;
        int **matrix;
        vector<int> vectorVertex;


    public: 
        int destination;
        int currentNumVertices;
        Graph(int numV);
        void generate(int numEdges);
        int getDestination();

        bool inList(int v1);
        bool edgeExists(int v1, int v2);
        void adjListBFS(int s, int e);
        void matrixBFS(int s, int e);
        void dijkstraMatrix(int s, int e);
        void dijkstraList(int s, int e);

        void printPath(int parent[], int j);

};

#endif

Answer 1

可能是因为你在这里做的是比较而不是赋值:

matrix[i][v1] == 1;
matrix[v1][i] == 1;

应该是 = 而不是 ==。