图的基本操作1、 所输入的数据要为整形数据 2、 输出的形式为:每按一次回车,遍历一个结点 3、 能创建最大结点树为30的任意图,实现对无向图的两种遍历 程序流程:
时间: 2024-05-04 22:21:35 浏览: 16
1. 定义图的数据结构,包括结点数量、边的数量、邻接矩阵等;
2. 实现图的创建函数,包括输入结点数量、边的数量、邻接矩阵等信息,根据信息创建图;
3. 实现图的遍历函数,包括深度优先遍历和广度优先遍历,根据不同的遍历算法实现不同的遍历顺序;
4. 编写主函数,根据用户的输入选择创建图或者进行遍历操作。
下面是伪代码实现:
```
//定义图的数据结构
struct Graph {
int nodeNum; //结点数量
int edgeNum; //边的数量
int adjMatrix[MAX_NODE][MAX_NODE]; //邻接矩阵
};
//创建图的函数
void createGraph(Graph &g) {
//输入结点数量、边的数量、邻接矩阵等信息,根据信息创建图
}
//深度优先遍历的函数
void DFS(Graph g, int node, bool visited[]) {
visited[node] = true; //标记当前结点为已访问
cout << node << " "; //输出当前结点
for(int i = 0; i < g.nodeNum; i++) {
if(g.adjMatrix[node][i] && !visited[i]) { //如果当前结点与i之间有边且i未访问过
DFS(g, i, visited); //递归访问i
}
}
}
//广度优先遍历的函数
void BFS(Graph g, int node, bool visited[]) {
queue<int> q;
q.push(node); //将起始结点加入队列
visited[node] = true; //标记当前结点为已访问
while(!q.empty()) {
int curNode = q.front(); //取出队首元素
q.pop(); //弹出队首元素
cout << curNode << " "; //输出当前结点
for(int i = 0; i < g.nodeNum; i++) {
if(g.adjMatrix[curNode][i] && !visited[i]) { //如果当前结点与i之间有边且i未访问过
q.push(i); //将i加入队列
visited[i] = true; //标记i为已访问
}
}
}
}
//主函数
int main() {
Graph g;
bool visited[MAX_NODE] = {false}; //初始化visited数组
cout << "请输入结点数量、边的数量和邻接矩阵:\n";
createGraph(g); //创建图
cout << "深度优先遍历结果:\n";
DFS(g, 0, visited); //深度优先遍历
cout << "\n广度优先遍历结果:\n";
memset(visited, false, sizeof(visited)); //清空visited数组
BFS(g, 0, visited); //广度优先遍历
return 0;
}
```