一般而言，图的实现有邻接矩阵和邻接表两种。

---

1. 邻接矩阵

#include <iostream>
#include <vector>class Graph {
private:int V; // 顶点数量std::vector<std::vector<int>> adjMatrix; // 邻接矩阵std::vector<bool> visited; // 记录顶点是否被访问过public:Graph(int vertices) : V(vertices) {adjMatrix.resize(V, std::vector<int>(V, 0));visited.resize(V, false);}void addEdge(int u, int v) {// 在顶点u到v之间添加一条有向边adjMatrix[u][v] = 1;}void printGraph() {std::cout << "Graph adjacency matrix:" << std::endl;for (int i = 0; i < V; ++i) {for (int j = 0; j < V; ++j) {std::cout << adjMatrix[i][j] << " ";}std::cout << std::endl;}}//图的深度优先遍历void DFS(int startVertex) {visited[startVertex] = true;std::cout << startVertex << " ";for (int i = 0; i < V; ++i) {if (adjMatrix[startVertex][i] == 1 && !visited[i]) {DFS(i);}}}void DFSTraversal() {std::cout << "Depth First Traversal starting from vertex 0:" << std::endl;DFS(0);std::cout << std::endl;}//图的广度优先遍历void BFS(int startVertex) {std::queue<int> q;q.push(startVertex);visited[startVertex] = true;while (!q.empty()) {int currentVertex = q.front();q.pop();std::cout << currentVertex << " ";for (int i = 0; i < V; ++i) {if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {q.push(i);visited[i] = true;}}}}void BFSTraversal() {std::cout << "Breadth First Traversal starting from vertex 0:" << std::endl;BFS(0);std::cout << std::endl;}
};
};

2. 邻接表

#include <iostream>
#include <vector>class Graph {
private:int V; // 顶点数量std::vector<std::vector<int>> adjList; // 邻接表std::vector<bool> visited; // 记录顶点是否被访问过public:Graph(int vertices) : V(vertices) {adjList.resize(V);visited.resize(V, false);}void addEdge(int u, int v) {// 在顶点u的邻接表中添加顶点vadjList[u].push_back(v);}void printGraph() {std::cout << "Graph adjacency list:" << std::endl;for (int i = 0; i < V; ++i) {std::cout << i << " -> ";for (int j : adjList[i]) {std::cout << j << " ";}std::cout << std::endl;}}//深度优先遍历void DFSRecursive(int startVertex) {visited[startVertex] = true;std::cout << startVertex << " ";for (int neighbor : adjList[startVertex]) {if (!visited[neighbor]) {DFSRecursive(neighbor);}}}// 深度优先遍历入口void DFSTraversal() {std::cout << "Depth First Traversal starting from vertex 0:" << std::endl;DFSRecursive(0);std::cout << std::endl;}// 广度优先搜索void BFS(int startVertex) {std::queue<int> q;q.push(startVertex);visited[startVertex] = true;while (!q.empty()) {int currentVertex = q.front();q.pop();std::cout << currentVertex << " ";for (int neighbor : adjList[currentVertex]) {if (!visited[neighbor]) {q.push(neighbor);visited[neighbor] = true;}}}}// 广度优先搜索入口void BFSTraversal() {std::cout << "Breadth First Traversal starting from vertex 0:" << std::endl;BFS(0);std::cout << std::endl;}
};

---

P1. 洛谷p3916图的遍历

#include<iostream>
#include<vector>
#include<queue>
using namespace std;class Graph {
private:int V; // 顶点数量std::vector<std::vector<int>> adjList; // 邻接表std::vector<bool> visited; // 记录顶点是否被访问过vector<int> maxspot;//记录每个点能到达的最大点的编号public:Graph(int vertices) : V(vertices) {adjList.resize(V+1);visited.resize(V+1, false);//只用于初始化,不可像fill一样用maxspot.resize(V+1);for(int i=0;i<=V;i++)maxspot[i]=i;//初始化为自己}void addEdge(int u, int v) {// 在顶点u的邻接表中添加顶点vadjList[u].push_back(v);}void clearvis(){for(int i=1;i<=V;i++) visited[i]=false;}void printans(){for(int i=1;i<=V;i++)cout<<maxspot[i]<<" ";}void printGraph() {std::cout << "Graph adjacency list:" << std::endl;for (int i = 1; i < V+1; ++i) {std::cout << i << " -> ";for (int j : adjList[i]) {std::cout << j << " ";}std::cout << std::endl;}}//深度优先遍历void DFSRecursive(int startVertex) {visited[startVertex] = true;std::cout << startVertex << " ";for (int neighbor : adjList[startVertex]) {if (!visited[neighbor]) {DFSRecursive(neighbor);}}}// 深度优先遍历入口void DFSTraversal() {std::cout << "Depth First Traversal starting from vertex 0:" << std::endl;DFSRecursive(0);std::cout << std::endl;}// 广度优先搜索void BFS(int startVertex) {int record=startVertex;std::queue<int> q;q.push(startVertex);visited[startVertex] = true;while (!q.empty()) {int currentVertex = q.front();q.pop();if(currentVertex>maxspot[record]) maxspot[record]=currentVertex;//std::cout << currentVertex << " ";for (int neighbor : adjList[currentVertex]) {if (!visited[neighbor]) {q.push(neighbor);visited[neighbor] = true;}}}//cout<<endl;}// 广度优先搜索入口void BFSTraversal() {std::cout << "Breadth First Traversal starting from vertex 0:" << std::endl;BFS(0);std::cout << std::endl;}
};int main()
{int n,m;cin>>n>>m;Graph mygraph(n);for(int i=1;i<=m;i++){int a,b;cin>>a>>b;mygraph.addEdge(a,b);}//mygraph.printGraph();for(int i=1;i<=n;i++){mygraph.BFS(i);mygraph.clearvis();}mygraph.printans();return 0;
}