#include
using namespace std;
const int MaxSize=10;
int visited[MaxSize]= {0};
struct ArcNode {
int adjvex;
ArcNode *next;
};
template
struct VertexNode {
DataType vertex;
ArcNode *firstedge;
};
template
class ALGraph {
public:
ALGraph(DataType a[],int n,int e);
~ALGraph();
void DFSTraverse(int v);
void BFSTraverse(int v);
private:
VertexNode adjlist[MaxSize];
int vertexNum,arcNum;
} ;
template
ALGraph::ALGraph(DataType a[],int n,int e) {
vertexNum=n;
arcNum=e;
for(int i=0; i
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
for(int k=0; k
int i,j;
cin>>i>>j;
ArcNode *s=new ArcNode;
s->adjvex=j;
s->next=adjlist[i].firstedge;
adjlist[i].firstedge=s;
}
}
template
ALGraph::~ALGraph() {
for(int i=0; i
if(adjlist[i].firstedge!=NULL) {
ArcNode *p,*q;
p=adjlist[i].firstedge;
while(p!=NULL) {
q=p;
p=p->next;
delete q;
}
}
}
}
template
void ALGraph::DFSTraverse(int v) {
int visited[100]= {0};
int Q[100];
int top=-1;
ArcNode p;
cout<
Q[++top]=v;
visited[v]=1;
while(top!=-1) {
v=Q[top--];
p=adjlist[v].firstedge;
while(p!=NULL) {
if(visited[p->adjvex]==0) {
visited[p->adjvex]=1;
cout<adjvex].vertex<<" ";
Q[++top]=adjlist[p->adjvex].vertex;
p=adjlist[p->adjvex].firstedge;
} else {
p=p->next;
}
}
if(p==NULL) {
v=Q[--top];
//p=adjlist[v].firstedge;
}
}
}
template
void ALGraph::BFSTraverse(int v) {
int visited[MaxSize]= {0};
int Q[MaxSize];
int front=-1,rear=-1;
cout<
visited[v]=1;
Q[++rear]=v;
while(front!=rear) {
ArcNode *p;
int j;
v=Q[++front];
p=adjlist[v].firstedge;
while(p!=NULL) {
j=p->adjvex;
if(visited[j]==0) {
cout<
visited[j]=1;
Q[++rear]=j;
}
p=p->next;
}
}
}
int main() {
int n=4,e=4;
char a[4]= {'a','b','c','d'};
ALGraph example(a,n,e);
cout<<"Depth-first-Traverse:";
example.DFSTraverse(0);
/*cout<<"Breath-first-Traverse:";
example.BFSTraverse(0);/
return 0;
}