图的深度优先遍历和广度优先遍历

上代码！

广度↓

#include<stdio.h> #include<stdlib.h> #define maxn 50 typedef struct node{ int elem; struct node *next; }DataNode; typedef struct{ int count; DataNode *front; DataNode *rear; }*LinkHead,LinkQueue; int Init(LinkHead *Q) { LinkHead q=(LinkHead)malloc(sizeof(LinkQueue)); DataNode *p=(DataNode *)malloc(sizeof(DataNode)); p->next = NULL; q->count = 0; q->front = p; q->rear = p; (*Q) = q; return 0; } int EnQueue(LinkHead *Q,int elem) { DataNode *p=(DataNode *)malloc(sizeof(DataNode)); p->elem = elem; (*Q)->rear->next = p; (*Q)->rear = p; (*Q)->count +=1; return 0; } int DeQueue(LinkHead *Q,int *elem) { DataNode *p=(*Q)->front->next; *elem = p->elem; (*Q)->front->next = p->next; if(p==(*Q)->rear) { (*Q)->rear = (*Q)->front; } free(p); (*Q)->count -= 1; return 0; } int Clear(LinkHead *Q) { while((*Q)->count != 0) { DataNode *p=(*Q)->front->next; (*Q)->front->next = p->next; if(p == (*Q)->rear) { (*Q)->rear =(*Q)->front; } free(p); (*Q)->count -= 1; } return 0; } int Destory(LinkHead *Q) { Clear(Q); (*Q)->rear = (*Q)->front->next; free((*Q)->front); (*Q)->front = (*Q)->rear; free(*Q); return 0; } typedef struct { int vers[maxn]; int arcs[maxn][maxn]; int vernum,arcnum; }Mgraph; Mgraph G; int Create(Mgraph *G) { scanf("%d",&(*G).vernum); for(int i=0;i<(*G).vernum ;i++) { for(int j=0;j<(*G).vernum ;j++) { scanf("%d",&(*G).arcs[i][j]); } } for(int i=0;i<=(*G).vernum;i++) { (*G).vers[i]=0; } } int BFS(Mgraph G) { LinkHead Q; Init(&Q); for(int i=0;i<G.vernum ;i++) { if(!G.vers[i]) { printf("%d ",i); G.vers[i]=1; EnQueue(&Q,i); while(Q->count != 0) { int elem; DeQueue(&Q,&elem); for(int j=0;j<G.vernum;j++) { if(G.arcs[elem][j]) { if(!G.vers[j]) { printf("%d ",j); G.vers[j]=1; EnQueue(&Q,j); } } } } } } return 0; } int main() { Create(&G); BFS(G); return 0; }

深度↓

#include<stdio.h> #include<stdlib.h> #define max 55 int visited[max]; typedef struct node{ int vexs[max ]; int arcs[max+1][max+1]; int vexnum,acrnum; }Mgraph; int Init(Mgraph *G) { for(int i=0;i<max;i++) { visited[i]=0; } for(int i=0;i<max;i++) { (*G).vexs[i]=0; } for(int j=0;j<=max;j++) { for(int k=0;k<=max;k++) { (*G).arcs[j][k]=0; } } } int Create(Mgraph *G) { int vexnum; scanf("%d",&(*G).vexnum); for(int i=0;i<(*G).vexnum;i++) { for(int j=0;j<(*G).vexnum;j++) { scanf("%d",&(*G).arcs[i][j]); } } return 0; } void DFTraverse(Mgraph *G, int i) { printf("%d ",i); visited[i] = 1; for (int j = 0; j < (*G).vexnum; j++) { if ((*G).arcs[i][j] == 1 && visited[j] == 0) DFTraverse(G, j); } } /*void BFTraverse(Mgraph *G.int i) { printf("%d",i); visited[i]=1; for() }*/ int main() { Mgraph G; Init(&G); Create(&G); DFTraverse(&G,0); return 0; }