图的遍历的实现。

#include \"stdio.h\" #include #define INFINITY 32767

#define MAX_V 20 #define QUEUE_SIZE (MAX_V+1) using namespace std;

bool *visited; typedef struct

{ char *vexs; int arcs[MAX_V][MAX_V]; int vexnum,arcnum; }Graph;

class Queue { public: void InitQueue()

{ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; } void EnQueue(int e)

{ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e)

{ e=base[front]; front=(front+1)%QUEUE_SIZE; } public:

int *base; int front; int rear; };

int Locate(Graph G,char c) { for(int i=0;iif(G.vexs[i]==c) return i; return -1; }

void CreateUDN(Graph &G) { int i,j,w,s1,s2; char a,b,temp; printf(\"输入顶点的总数和边的总数:\"); scanf(\"%d%d\",&G.vexnum,&G.arcnum);

temp=getchar(); G.vexs=(char *)malloc(G.vexnum*sizeof(char)); printf(\"输入%d个顶点分别为：\\n\",G.vexnum);

for(i=0;i{ printf(\"顶点%d:\",i); scanf(\"%c\",&G.vexs[i]); temp=getchar();} for(i=0;iprintf(\"输入%d条边分别为：\\n\",G.arcnum);

for(i=0;iscanf(\"%c-%c %d\",&a,&b,&w);

temp=getchar(); s1=Locate(G,a); s2=Locate(G,b);

G.arcs[s1][s2]=G.arcs[s2][s1]=w; } }

int FirstVex(Graph G,int k) { if(k>=0 && k{ for(int i=0;iif(G.arcs[k][i]!=INFINITY) return i; } return -1; }

int NextVex(Graph G,int i,int j)

{ if(i>=0 && i=0 && jif(G.arcs[i][k]!=INFINITY) return k; } return -1; }

void DFS(Graph G,int k) { int i; if(k==-1) { for(i=0;i{ visited[k]=true; printf(\"%c \",G.vexs[k]); for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i)) if(!visited[i]) DFS(G,i); } }

void BFS(Graph G) { int k;

Queue Q; Q.InitQueue();

for(int i=0;iif(!visited[i]) { visited[i]=true; printf(\"%c \",G.vexs[i]);

Q.EnQueue(i); while(Q.front!=Q.rear)

{ Q.DeQueue(k); for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w)) if(!visited[w]) { visited[w]=true; printf(\"%c \",G.vexs[w]); Q.EnQueue(w); } } } }

void main() { int i; Graph G; CreateUDN(G);

visited=(bool *)malloc(G.vexnum*sizeof(bool)); printf(\"\\n深度优先搜索结果为: \");

for(i=0;ifor(i=0;i