|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include<iostream>
#include<string>
using namespace std;
const int max=100;
struct ArcNode{
int adjvex;
ArcNode *nexttarc;
};
struct VexNode{
int vexdata;
ArcNode *firstarc;
};
VexNode adjlist[max];
class Graph
{
private:
static string str;
bool *visited;
VexNode *adjlist;
int n;
void dfs0(int v0, void visit(int &v));
void bfs0(int v0, void visit(int &v));
public:
Graph(int l);
// Graph(VexNode adjl[], int l);
// Graph(int vex[], int arc[], int n);
// int ODVex(int data);
void instVex(int data);
void instArc(int v1,int v2);
string dfs(int v0, void visit(int &v));
string bfs(int v0, void visit(int &v));
static void func1(int &v);
// static void func2(int &v);
}
void Graph::func1(int &v){
str=str+IntToStr(v)+"";
}
Graph::Graph(int l){
n=0; max=l;
visited=new bool[l];
adjlist=new VexNode[l];
}
void Graph::instVex(int data){
if(n<max)
adjlist[n++].vexdata=data;
}
void Graph::instArc(int v1, int v2){
ArcNode *p1, *p2;
p1=new ArcNode;
p2=new ArcNode;
p1->nexttarc=adjlist[v1].firstarc;
p2->nexttarc=adjlist[v2].firstarc;
adjlist[v1].firstarc=p1;
adjlist[v2].firstarc=p2;
p1->adjvex=v2;
p2->adjvex=v1;
}
void Graph::dfs0(int v0, void visit(int &v)){
ArcNode *p;
visited[v0]=true;
visit(adjlist[v0].vexdata);
p=adjlist[v0].firstarc;
while(p!=null){
if(visited[p->adjvex]==false)
dfs0(p->adjvex,visit);
p=p->nexttarc;
}
}
String Graph::dfs(int v0, void visit(int &v)){
int i;
for(i=0; i<n; i++)
visited[i]=false;
str="深度优先";
dfs0(v0,visit);
return str;
}
void Graph::dfs0(int v0, visit(int &v)){
ArcNode *p;
int v, adjv, front,rear;
int q[100];
visited[v0]=true;
visit(adjlist[v0].vexdata);
front=1;rear=1;
q[rear]=v0;rear=rear+1;
while(front!=rear){
v=q[front]; front=front+1;
p=adjlist[v].firstarc;
while(p!=null){
adjv=p->adjvex;
if(visited[adjv]==false){
visited[adjv]==true;
visit(adjlist[adjv].vexdata);
q[rear]=adjv;rear=rear+1;
};
p=p->nexttarc;
}
}
}
String Graph::bfs(int v0, void visit(int &v)){
int i;
for(i=0; i<n; i++)
visited[i]==false;
str="广度优先";
bfs0(v0, visit);
return str;
}
void main(){
Graph g1(10);
for(int i=0; i<4; i++)
g1.instVex(i);
g1.instArc(0,1); g1.instArc(0,2); g1.instArc(3,1); g1.instArc(3,2);
cout<<g1.dfs(0,Graph::func1)<<endl;
cout<<g1.bfs(0,Graph::func1)<<endl;
}
|
|