帮我写一份数据结构程序代码:1、建立头文件Graph.h,包含数据类型定义和基本操作。 2、建立程序文件GraphDFS.cpp,通过调用头文件中的操作实现图的深度优先搜索函数,完成图的遍历。
时间: 2025-06-21 20:27:50 浏览: 11
### 定义图的数据结构
为了定义一个通用的图数据结构并实现其基本操作,在`Graph.h`中可以采用模板类的方式,以便支持不同类型的顶点和边。这里将展示如何构建这样一个头文件。
#### Graph.h 文件内容
```cpp
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// Define the graph class using adjacency list representation.
template<typename T>
class Graph {
private:
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency List
public:
Graph(int v); // Constructor to initialize a graph with 'v' vertices
void addEdge(int u, int w);
void DFSUtil(int v, bool visited[]); // Utility function for DFS traversal
void DFS(int v); // Perform DFS starting from vertex 'v'
};
#endif /* GRAPH_H */
```
此部分代码定义了一个名为 `Graph` 的模板类[^1],它使用邻接表作为内部存储机制,并提供了添加边的方法以及执行深度优先搜索的功能。
### 实现图的操作及DFS算法
接下来是在另一个源文件 (`GraphDFS.cpp`) 中具体实现上述声明的方法:
#### GraphDFS.cpp 文件内容
```cpp
#include "Graph.h"
// Constructor initializes an empty graph with given number of vertices
template<typename T>
Graph<T>::Graph(int v) : V(v), adj(vector<vector<int>>(V)) {}
// Adds an edge into the graph (undirected by default)
template<typename T>
void Graph<T>::addEdge(int u, int w){
adj[u].push_back(w); // Add w to u’s list.
}
// A recursive utility function used by DFS
template<typename T>
void Graph<T>::DFSUtil(int v, bool visited[]){
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent to this vertex
for(auto i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
DFSUtil(*i, visited);
}
// The function to do DFS traversal. It uses recursive DFSUtil()
template<typename T>
void Graph<T>::DFS(int v){
// Initially mark all vertices as not visited
bool *visited = new bool[V];
fill_n(visited,V,false);
// Call the private helper method that actually performs the DFS
DFSUtil(v, visited);
}
```
这段代码完成了对之前在`Graph.h`里声明的各种成员函数的实际编码工作,特别是实现了深度优先搜索的过程。
请注意由于C++标准并不允许分离编译模板类中的方法定义(除非是内联),因此通常建议把整个模板类放在单个`.hpp`或`.h`文件中一起提供给使用者[^5]。
阅读全文
相关推荐


















