图的遍历(graph traversal)

数据结构与算法第五章图(gragh) 图的遍历(graph traversal)

一、图的遍历
从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问顶点，需要记录已访问过的顶点。
图的遍历分为深度优先遍历和广度优先遍历

二、深度优先遍历(DFS)
从图中某结点出发，访问其相邻结点(按编号最小或最大)，再访问该结点的相邻结点，直至访问完所有的结点。一条路走到头，回头再走没走过的路。可以看出DFS算法是一个递归的过程，其中需要借助一个栈完成操作。
基于邻接表的遍历的序列不唯一，基于邻接矩阵的遍历序列是唯一的。

深度优先遍历(从大到小)：0，4，6，9，8，7，5，3，2，1。
深度优先遍历(从小到大)：0，1，2，3，4，6，5，7，8，9。

图的深度遍历-邻接表1

#include <iostream>

using namespace std;

const int MAX_VERTICES = 1000;

void DFSHelper(int** adjList, int numVertices, int vertex, bool* visited) {
    // mark the current vertex as visited
    visited[vertex] = true;
    // process the current vertex
    cout << vertex << " ";
    // recursively visit all adjacent vertices that have not been visited
    for (int i = 0; i < numVertices; ++i) {
        if (adjList[vertex][i] && !visited[i]) {
            DFSHelper(adjList, numVertices, i, visited);
        }
    }
}

void DFS(int** adjList, int numVertices, int startVertex) {
    // create an array to keep track of visited vertices
    bool visited[MAX_VERTICES] = {false};
    // call the recursive helper function on the starting vertex
    DFSHelper(adjList, numVertices, startVertex, visited);
}

int main() {
    // create an adjacency list for a graph with 4 vertices and 4 edges
    int numVertices = 4;
    int** adjList = new int*[numVertices];
    for (int i = 0; i < numVertices; ++i) {
        adjList[i] = new int[numVertices]();
    }
    adjList[0][1] = adjList[1][0] = 1;
    adjList[1][2] = adjList[2][1] = 1;
    adjList[2][3] = adjList[3][2] = 1;
    // perform a depth-first search starting at vertex 0
    DFS(adjList, numVertices, 0);
    // free memory
    for (int i = 0; i < numVertices; ++i) {
        delete[] adjList[i];
    }
    delete[] adjList;
    return 0;
}

图的深度遍历-邻接表2

#include <iostream>
#include <vector>
#include <set>

using namespace std;

void DFSHelper(vector<vector<int>>& adjList, int vertex, set<int>& visited) {
    // mark the current vertex as visited
    visited.insert(vertex);
    // process the current vertex
    cout << vertex << " ";
    // recursively visit all adjacent vertices that have not been visited
    for (int neighbor : adjList[vertex]) {   //C++ 11 feature
        if (visited.find(neighbor) == visited.end()) {
            DFSHelper(adjList, neighbor, visited);
        }
    }
}

void DFS(vector<vector<int>>& adjList, int startVertex) {
    // create a set to keep track of visited vertices
    set<int> visited;
    // call the recursive helper function on the starting vertex
    DFSHelper(adjList, startVertex, visited);
}

int main() {
    // create an adjacency list for a graph with 4 vertices and 4 edges
    vector<vector<int>> adjList(4);
    adjList[0].push_back(1);
    adjList[1].push_back(0);
    adjList[1].push_back(2);
    adjList[2].push_back(1);
    adjList[2].push_back(3);
    adjList[3].push_back(2);
    // perform a depth-first search starting at vertex 0
    DFS(adjList, 0);
    return 0;
}

图的深度遍历-邻接矩阵

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_VERTICES = 1000;

void DFSHelper(int** adjMatrix, int numVertices, int vertex, bool* visited) {
    // mark the current vertex as visited
    visited[vertex] = true;
    // process the current vertex
    cout << vertex << " ";
    // recursively visit all adjacent vertices that have not been visited
    for (int i = 0; i < numVertices; ++i) {
        if (adjMatrix[vertex][i] && !visited[i]) {
            DFSHelper(adjMatrix, numVertices, i, visited);
        }
    }
}

void DFS(int** adjMatrix, int numVertices, int startVertex) {
    // create an array to keep track of visited vertices
    bool visited[MAX_VERTICES];
    memset(visited, false, sizeof(visited));
    // call the recursive helper function on the starting vertex
    DFSHelper(adjMatrix, numVertices, startVertex, visited);
}

int main() {
    // create an adjacency matrix for a graph with 4 vertices and 4 edges
    int numVertices = 4;
    int** adjMatrix = new int*[numVertices];
    for (int i = 0; i < numVertices; ++i) {
        adjMatrix[i] = new int[numVertices];
        memset(adjMatrix[i], 0, numVertices * sizeof(int));
    }
    adjMatrix[0][1] = adjMatrix[1][0] = 1;
    adjMatrix[1][2] = adjMatrix[2][1] = 1;
    adjMatrix[2][3] = adjMatrix[3][2] = 1;
    // perform a depth-first search starting at vertex 0
    DFS(adjMatrix, numVertices, 0);
    // free memory
    for (int i = 0; i < numVertices; ++i) {
        delete[] adjMatrix[i];
    }
    delete[] adjMatrix;
    return 0;
}

三、广度优先遍历(BFS)

图的广度遍历-邻接表

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAX_VERTICES = 1000;

void BFS(vector<int>* adjList, int numVertices, int startVertex) {
    // create an array to keep track of visited vertices
    bool visited[MAX_VERTICES] = { false };
    // create a queue to store the vertices to be processed
    queue<int> q;
    // mark the starting vertex as visited and add it to the queue
    visited[startVertex] = true;
    q.push(startVertex);
    // process the vertices in the queue
    while (!q.empty()) {
        // get the next vertex from the queue
        int vertex = q.front();
        q.pop();
        // process the current vertex
        cout << vertex << " ";
        // add all unvisited neighbors of the current vertex to the queue
        for (int i = 0; i < adjList[vertex].size(); ++i) {
            int neighbor = adjList[vertex][i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // create an adjacency list for a graph with 4 vertices and 4 edges
    int numVertices = 4;
    vector<int> adjList[MAX_VERTICES];
    adjList[0].push_back(1);
    adjList[1].push_back(0);
    adjList[1].push_back(2);
    adjList[2].push_back(1);
    adjList[2].push_back(3);
    adjList[3].push_back(2);
    // perform a breadth-first search starting at vertex 0
    BFS(adjList, numVertices, 0);
    return 0;
}

图的广度遍历-邻接矩阵

#include <iostream>
#include <queue>

using namespace std;

const int MAX_VERTICES = 1000;

void BFS(int adjMatrix[][MAX_VERTICES], int numVertices, int startVertex) {
    // create an array to keep track of visited vertices
    bool visited[MAX_VERTICES] = { false };
    // create a queue to store the vertices to be processed
    queue<int> q;
    // mark the starting vertex as visited and add it to the queue
    visited[startVertex] = true;
    q.push(startVertex);
    // process the vertices in the queue
    while (!q.empty()) {
        // get the next vertex from the queue
        int vertex = q.front();
        q.pop();
        // process the current vertex
        cout << vertex << " ";
        // add all unvisited neighbors of the current vertex to the queue
        for (int i = 0; i < numVertices; ++i) {
            if (adjMatrix[vertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    // create an adjacency matrix for a graph with 4 vertices and 4 edges
    int numVertices = 4;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES] = { { 0, 1, 0, 0 },
                                                  { 1, 0, 1, 0 },
                                                  { 0, 1, 0, 1 },
                                                  { 0, 0, 1, 0 } };
    // perform a breadth-first search starting at vertex 0
    BFS(adjMatrix, numVertices, 0);
    return 0;
}

B3862

P1294高手去散步

Previous Topic

Back to Lesson

Next Topic