Question

怎么用C++实现图的遍历深度优先和广度优先搜索

必须是c++
要有调试结果
和流程图什么的！

Answer 1

#include <stdio.h>
class Node{
public:
int value;
Node * left;
Node * right;
Node(int v): value(v){
left = NULL;
right = NULL;
}
~Node() {
if(left != NULL) delete left;
if (right != NULL) delete right;
}
};
class BTree {
private:
Node * root;
public:
BTree(){
root = NULL;
}
void add(int val) {
Node *p = new Node(val);
add(p);
}
void add(Node *node) {
if(node == NULL) return;
if (root == NULL) {
root = node;
return;
}
Node *p = root;
while(p != NULL) {
if(node->value <= p->value) {
if(p->left == NULL) {
p->left = node;
break;
}
else p = p->left;
} else {
if (p->right == NULL) {
p->right = node;
break;
} else p = p->right;
}
}
}
bool find(int val) {
Node *p = root;
while(p) {
if(p->value == val) {
printf("Find %d\n", val);
return true;
}
else if(p->value > val) p = p->left;
else p = p->right;
}
printf("Not Find %d\n", val);
return false;
}
~BTree() {
delete root;
}
void print(){
midTraval(root);
printf("\n");
}
void midTraval(Node *p) {
if(p==NULL) return;
midTraval(p->left);
printf("%d ", p->value);
midTraval(p->right);
}
};
int main()
{
int n;
int a[7] = {5, 3, 1, 2, 4, 8, 6};
BTree tree;
for(int i=0; i<7; i++)
tree.add(a[i]);
tree.print();

tree.find(3);
tree.find(7);

scanf("%d", &n);
return 0;
}

追问

能不能具体点！
给点注释什么的！
我不大看懂！

追答

class Node{ //二叉树节点类
public:
int value; //节点的值
Node * left;// 左子节点
Node * right;//右子节点
Node(int v): value(v){
left = NULL;
right = NULL;
}
~Node() {//析构函数
if(left != NULL) delete left;
if (right != NULL) delete right;
}
};
class BTree {//二叉树类
private:
Node * root; //二叉树的根节点
public:
BTree(){
root = NULL;
}
void add(int val) { //将val加入到二叉树之中。
Node *p = new Node(val);//构造一个新的节点
add(p);
}
void add(Node *node) {//将节点node 加入到二叉树之中。
if(node == NULL) return;
if (root == NULL) { //如果root是空，则将root指向node
root = node;
return;
}
Node *p = root;
while(p != NULL) { //深度周游找到节点node插入的位置。
if(node->value value) {//如果node的值小于当前节点的值，将其插入到左子树之中
if(p->left == NULL) {//当前的节点的左子树为空，则node作为左儿子。
p->left = node;
break;
}
else p = p->left;//继续在左子树中查找插入的位置
} else {//如果node的值大于当前节点的值，将其插入到右子树之中
if (p->right == NULL) {//当前的节点的右子树为空，则node作为右儿子。
p->right = node;
break;
} else p = p->right; //继续在右子树中查找插入的位置
}
}
}
bool find(int val) { //查找值val是否在树中
Node *p = root;//从root开始
while(p) { //循环直到找到了要查找的节点，或者p为空
if(p->value == val) {// val和当前p的值相同，找到了。
printf("Find %d\n", val);
return true;
}
else if(p->value > val) p = p->left; //val的值小于p的值，则继续在p的左子树中查找
else p = p->right; //val的值大于p的值，则继续在p的左子树中查找
}
printf("Not Find %d\n", val);//没有找到值为val的节点
return false;
}
};

追问

不好意思！
我要的是做图的遍历深度优先搜索和广度优先搜索的c++程序！
你做的貌似是二叉树的!

Answer 2

#include<iostream>
using namespace std;
#include<cstdlib>
#include<queue> //c++的队列库函数
#include<algorithm>
# define MAX_VERTEX_NUM 8 //顶点最大个数
typedef struct ArcNode{
int adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
int data; //int 类型
ArcNode *firstarc;
}Vnode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertex;
int vexnum,arcnum; //顶点的实际数，边的实际数
}Graph;

void CreateGraph(Graph &G){
ArcNode* s;
int i,j;
int k,d;
int n = G.vexnum;
int e = G.arcnum;
for(i=1; i<=n; i++){ //n为顶点数、e为边数
G.vertex[i].data = i;
G.vertex[i].firstarc = NULL;
}
for(i=1; i<=e; i++){
// 输入边
scanf("%d%d",&k,&d);
s = (ArcNode*)malloc(sizeof(ArcNode));
s->adjvex = d;
s->nextarc = G.vertex[k].firstarc;
G.vertex[k].firstarc = s;
s = (ArcNode*)malloc(sizeof(ArcNode));
s->adjvex = k;
s->nextarc = G.vertex[d].firstarc;
G.vertex[d].firstarc = s;
}
for(i=1;i<=n;i++){
int count=0;
int paixu[100] = {0};
ArcNode* r;
r = (ArcNode*)malloc(sizeof(ArcNode));
r = G.vertex[i].firstarc;
while(r!=NULL){
paixu[count] = r->adjvex;
count++;
r = r->nextarc;
}
sort(paixu,paixu+100);

r = G.vertex[i].firstarc;
count =100-count;
while(r!=NULL){
r->adjvex = paixu[count];
count++;
r = r->nextarc;
}
}
}
int flag[100] = {0};
int con=1;
void DFS(Graph G,int v){
if(con < G.vexnum){
cout<<G.vertex[v].data<<" ";
con++;
}
else{
cout<<G.vertex[v].data;
}
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p = G.vertex[v].firstarc;
flag[v] = 1;
while(p){
if(!flag[p->adjvex]){
DFS(G,p->adjvex);
}
p = p->nextarc;
}
}
int flag1[100] = {0};
int con1 = 1;
void BFS(Graph G,int v){
queue <int> Q;
cout<<G.vertex[v].data<<" ";
con1++;
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
flag1[v] = 1;
Q.push(v);
while(!Q.empty()){
v = Q.front();
Q.pop();
p = G.vertex[v].firstarc;
while(p){
if(!flag1[p->adjvex]){
if(con1 < G.vexnum){
cout<<G.vertex[p->adjvex].data<<" ";
con1++;
}
else{
cout<<G.vertex[p->adjvex].data;
}
flag1[p->adjvex] = 1;
Q.push(p->adjvex);
}
p = p->nextarc;
}
}
}
int main(){
int T;
Graph G;
cout<<"1...图的建立"<<endl;
cout<<"2...深度优先遍历图"<<endl;
cout<<"3...广度优先遍历图"<<endl;
cout<<"0...结束"<<endl;
cout<<endl;
scanf("%d",&T);
while(T != 0){
if(T == 1){
cout<<"请输入图的顶点数和边数"<<endl;
scanf("%d%d",&G.vexnum,&G.arcnum); // 顶点数 边数
CreateGraph(G); //建立图
cout<<"建图成功"<<endl;
}
else if(T == 2){
cout<<"深度优先遍历结果为："<<endl;
DFS(G,1); //深度优先遍历图
cout<<endl;
}
else if(T == 3){
cout<<"广度优先遍历结果为："<<endl;
BFS(G,1); //广度优先遍历图
cout<<endl;
}
scanf("%d",&T);
}
return 0;
}

Answer 3

才给10分呀，给50分我给你做呢。