c语言中图的邻接矩阵的深度优先和广度优先搜索
#include<stdio.h>#include<stdlib.h>typedef struct {int vexs[7];int arcs[7][7];int vexnum,arcnum;}AMGraph;bool visited[7];int con[7];int com=0;int initlink(AMGraph &p){int i;for(i=0;i<p.vexnum;i++)visited[i+1]=false;for (i=0;i<7;i++){con[i]=NULL;}}int push(int n){con[com]=n;com+=1;}int pop(){int i,j;i=con[0];if (con[1]==NULL){com-=1;con[0]=NULL;return i;}for (j=0;j<6;j++){if(con[j+1]!=NULL){con[j]=con[j+1];con[j+1]=NULL;}}com-=1;return i;}int Init(AMGraph &p){int i,j;p.vexnum=p.arcnum=7;p.arcs[0][1]=p.arcs[0][2]=p.arcs[0][3]=p.arcs[0][4]=p.arcs[0][6]=1;p.arcs[1][3]=p.arcs[1][6]=1;p.arcs[2][4]=1;p.arcs[3][4]=p.arcs[3][5]=1;p.arcs[4][5]=1;p.arcs[5][6]=1;p.arcs[0][5]=0;for (i=0;i<7;i++){p.vexs[i]=i;for (j=0;j<7;j++){if(p.arcs[i][j]==1){p.arcs[j][i]=1;continue;}p.arcs[i][j]=0;}}p.arcs[0][5]=p.arcs[5][0]=0;}int DFS(AMGraph &p,int n)//深度优先搜索 {int i,j;printf("%d ",n);visited[n]=true;for (i=0;i<7;i++){if (p.arcs[n][i]==1){if(!visited[i])DFS(p,i);}}}int DFSTraverse(AMGraph &p)//深度优先 {int i,j;for(i=0;i<p.vexnum;i++)visited[i+1]=false;for(i=0;i<p.vexnum;i++)if(!visited[i])DFS(p,i);}int BFS(AMGraph &p,int n){int i,j,v;initlink(p);printf("%d ",n);push(n);while(com!=0){v=pop();for (i=0;i<7;i++){if (p.arcs[v][i]==1){if(!visited[i]){printf("%d ",i);visited[i]=true;push(i);}}}}return 0;}int main(){//头指针尾指针 AMGraph p;Init(p);DFSTraverse(p);printf("\n");BFS(p,0);}
