#include
#include
#include
#include
#define maxsize 64#define TRUE 1#define FALSE 0#define n 6#define e 9typedef char datatype ;typedef char vextype;typedef int adjtype; typedef struct { vextype vexs[maxsize]; adjtype arcs[maxsize][maxsize];}graph; typedef struct { datatype data[maxsize]; int front,rear;}sequeue; typedef struct node { int adjvex; struct node *next;}edgenode;typedef struct{ vextype vertex; edgenode *link;}vexnode; vexnode gl[maxsize];graph *ga;sequeue *Q; graph *CREATGRAPH(){ int i,j,k; char ch; system("cls"); scanf("%c",&ch); printf("n请输入顶点信息(邻接矩阵): "); for(i=1;i<=n;i++) scanf("%c",&ga->vexs[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) ga->arcs[i][j]=0; printf("n输入节点信息与权值：n"); for(k=0;k
arcs[i][j]=1; ga->arcs[j][i]=1; } return ga;} void PRINT(){ int i,j; system("cls"); printf("n对应的邻接矩阵是：nn"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%5d",ga->arcs[i][j]); printf("n"); }} void CREATADJLIST(){ int i,j,k; edgenode *s; char ch; system("cls"); printf("请输入顶点信息: "); scanf("%c",&ch); for(i=1;i<=n;i++) { gl[i].vertex=getchar(); gl[i].link=NULL; } printf("输入边表节点信息：n"); for(k=1;k<=e;k++) { scanf("%d %d",&i,&j); s=(edgenode *)malloc(sizeof(edgenode)); s->adjvex=j; s->next=gl[i].link; gl[i].link=s; s=(edgenode *)malloc(sizeof(edgenode)); s->adjvex=i; s->next=gl[j].link; gl[j].link=s; }} void PRINTL(){ int i; edgenode *s; system("cls"); printf("n对应的邻接表是：n"); for(i=1;i<=n;i++) { s=gl[i].link; printf("%3c",gl[i].vertex); while(s!=NULL) { printf("%5d",s->adjvex); s=s->next; } printf("n"); }} sequeue *SETNULL(sequeue *P){ P->front=maxsize-1; P->rear=maxsize-1; return P;} int EMPTY(sequeue *Q){ if(Q->rear==Q->front) return TRUE; else return FALSE;} sequeue *ENQUEUE(sequeue *Q,int k){ if(Q->front==(Q->rear+1)%maxsize) { printf("队列已满!n"); return NULL; } else { Q->rear=(Q->rear+1)%maxsize; Q->data[Q->rear]=k; } return Q;}int DEQUEUE(sequeue *Q){ if(EMPTY(Q)) { printf("队列为空,无法出队!n"); return FALSE; } else { Q->front=(Q->front+1)%maxsize; return Q->data[Q->front]; } return 1;}void BFS(int k){ int i,j; int visited[maxsize]={0}; printf("n广度优先遍历后得到的序列是: "); Q=SETNULL(Q); printf("%3c",ga->vexs[k]); visited[k]=TRUE; Q=ENQUEUE(Q,k); while(!EMPTY(Q)) { i=DEQUEUE(Q); for(j=1;j<=n;j++) if((ga->arcs[i][j]==1)&&(!visited[j])) { printf("%3c",ga->vexs[j]); visited[j]=TRUE; Q=ENQUEUE(Q,j); } } printf("nn深度优先遍历后得到的序列是: "); } void BFSL(int k){ int i; int visited[maxsize]={0}; edgenode *p; Q=SETNULL(Q); printf("n广度优先遍历后得到的序列是: "); printf("%3c",gl[k].vertex); visited[k]=TRUE; Q=ENQUEUE(Q,k); while(!EMPTY(Q)) { i=DEQUEUE(Q); p=gl[i].link; while(p!=NULL) { if(!visited[p->adjvex]) { printf("%3c",gl[p->adjvex].vertex); visited[p->adjvex]=TRUE; Q=ENQUEUE(Q,p->adjvex); } p=p->next; } } printf("nn深度优先遍历后得到的序列是: ");} void DFS(int i){ int j; static int visited[maxsize]={0}; printf("%3c",ga->vexs[i]); visited[i]=TRUE; for(j=1;j<=n;j++) if((ga->arcs[i][j]==1)&&(!visited[j])) DFS (j);}void DFSL(int k){ int j; edgenode *p; static int visited[maxsize]={0};printf("%3c",gl[k].vertex); visited[k]=TRUE; p=gl[k].link;while(p) { j=p->adjvex; if(!visited[j]) DFSL(j); p=p->next; }}void main(){ int i,k; int ch; Q=malloc(sizeof(graph)); ga=malloc(sizeof(graph)); while(1) { printf("nnn"); printf("输入你的选择: "); scanf("%d",&ch); switch(ch) { case 1: CREATADJLIST(); PRINTL(); printf("想从第几号结点开始: "); scanf("%d",&k); BFSL(k); DFSL(k);break; case 2: ga=CREATGRAPH(); PRINT(); printf("想从第几号结点开始: "); scanf("%d",&i); BFS(i); DFS(i);break; case 3:exit (0); } }}
PS:下标从1开始的,输入矩阵的对应元素时要按你的顺序输入 输入表的顺序是要逆序输入 否则两者答案不匹配 因为表的选择要有大小要求的 你可以试一下.