图的“基本操作查找函数”(LocateVex查找坐标)“无向图”(Undirected Graph )输出相邻矩阵(print )循环队列“基本操作队列”(EnQueue )队列(DeQueue )是队列(空) 宽度优先遍历)宽度优先查找)设置宽优先遍历基本步长全局变量visited数组并将其初始化为全零意味着所有节点都不被访问，而是设置起始点。 包括使用起点输出、标记成已访问、入队后续节点。 从起点操作后续节点。 (输出、标记成已访问、入队)。
(步骤2-3重复广度优先搜索)循环2-3的操作，以避免忽略“孤岛”节点。
(步骤4递归执行宽度优先搜索，不忽略“孤岛”节点。 宽度优先算法分析(是宽度优先扫描)在设置起点后将起点入队。 (以下代码的第7-10行)然后对队列执行操作。 每个元素退出队列后，按顺序对其所有相邻节点进行排队，一次退出后对退出队列的元素执行操作)操作是找到其端点和有边的端点，然后“输出、设置为已访问、入队”直到队列为空voidBFS(mgraph*g，int i ) {int j； CyQueue q； 创建(q； //1 .起点printf(%c )、G-Vertex[i] )； //1 .输出开始节点visited[i]=1； //2 .将访问的节点标记为1enqueue(q，I )； //3 .将第一个节点入队//2 .从起点操作后续节点while (！ 队列empty (q )//队列不为空) dequeue，I )； for(j=0； jG-vexnum； j () if ) g-adj矩阵[ I ] [ j ]==1visited [ j ]==0) ) printf('%c '，G-Vertex[j] )； //输出满足条件的顶点visited [ j ]=1； //设为已访问状态1enqueue(q，j )； //入队} }完整的源代码1 .相邻矩阵# include stdio.h # include stdlib.h # definevertexmax 100//最大顶点数为100#define Maxsize 100 ////队列元素类型//*图结构//typedef struct { vertextypevertex [ vertex max ]； //存储顶点元素的一维数组intadjmatrix [ vertex max ] [ vertex max ]； //相邻矩阵的二维数组int vexnum、arcnum； //图的顶点数和边数}MGraph； /*队列结构* /类型def struct { datatype * base； int front； int rear； }CyQueue； /*查找有向图UDG的基本操作*/intlocatevex(mgraph*g，VertexType v ) /一维数组Vertex[] )中元素v的下标，然后单击下标({int i； for(I=0； iG-vexnum； I ) if(v==g-vertex[I] ) {return i； }printf(nosuchvertex！ n '； 返回- 1； }voidcreateudg(mgraph*g ) {int i，j； printf (输入顶点数和边数(n )； printf (顶点数n=)； scanf('%d '，G-vexnum )； printf (边缘数e=)； scanf('%d '，G-arcnum )； printf((n )； printf((n )； printf ('输入顶点元素(不必用空格分隔() )； scanf('%s '，G-Vertex )； printf((n )； for(I=0； iG-vexnum； I ) for ) j=0； jG-vexnum； j ) { g-adj矩阵[ I ] [ j ]=0； (} int n，m； VertexType v1，v2； printf ('请输入边缘的信息。 n )； for(I=0； iG-arcnum； I ) { printf ('输入第%d条的边缘信息)、i 1)； 扫描(' % c % c )、v1、v2 )； n=locatevex(g，v1 )； m=locatevex(g，v2 )； if(n==-1||m==-1 ) ) printf (通告程序！ n '； 返回； } g-adj矩阵[ n ] [ m ]=1； g-adj矩阵[ m ] [ n ]=1； }voidprint(mgraphg ) {int i，j； printf(((((n---------)
----------------");printf("n 邻接矩阵：nn"); printf("t "); for(i=0;i<G.vexnum;i++)printf(" %c",G.Vertex[i]);printf("n"); for(i=0;i<G.vexnum;i++) { printf("t%c",G.Vertex[i]); for(j=0;j<G.vexnum;j++) { printf(" %d",G.AdjMatrix[i][j]); } printf("n"); }}/*循环队列基本操作*/void create(CyQueue *q){q->base=(dataType *)malloc(Maxsize*sizeof(dataType));if(!q->base){printf("Space allocation failed!n");return;}q->front=q->rear=0;return;}void EnQueue(CyQueue *q,dataType value){if((q->rear+1)%Maxsize==q->front){printf("Cyclic Queue is Full!n");return;}q->base[q->rear]=value;q->rear=(q->rear+1)%Maxsize;return;}void DeQueue(CyQueue *q,dataType *value){if(q->front==q->rear){printf("Cyclic Queue is Empty!n");return;}*value=q->base[q->front];q->front=(q->front+1)%Maxsize;return;} int QueueEmpty(CyQueue *q){ if (q->front==q->rear)//队列为空返回1，不为空返回0 { return 1; } return 0;}/*广度优先遍历BFS*/ int visited[VertexMax];//定义"标志"数组为全局变量 void BFS(MGraph *G,int i){int j;CyQueue q;create(&q); //1.设置起始点 printf("%c",G->Vertex[i]);//1.输出当前结点 visited[i]=1;//2.将已访问的结点标志成1EnQueue(&q,i);//3.将第一个结点入队 //2.由起始点开始，对后续结点进行操作while(!QueueEmpty(&q)){DeQueue(&q,&i);for(j=0;j<G->vexnum;j++){if(G->AdjMatrix[i][j]==1&&visited[j]==0){printf("%c",G->Vertex[j]);//输出符合条件的顶点 visited[j]=1;//设置成已访问状态1 EnQueue(&q,j);//入队 }}} } void BFSTraverse(MGraph *G){int i;//数组初始化为全0 for(i=0;i<G->vexnum;i++){visited[i]=0;} for(i=0;i<G->vexnum;i++){if(visited[i]==0){BFS(G,i);}}} int main() {MGraph G; CreateUDG(&G);print(G); printf("nn广度优先遍历："); BFSTraverse(&G); return 0;} 2.邻接表： #include <stdio.h>#include <stdlib.h>#define VertexMax 20 //最大顶点个数 #define Maxsize 100 //队列最大元素个数100 typedef char VertexType;//顶点的数据类型（char）typedef int dataType; //队列元素类型 /*邻接表结构体*/typedef struct ArcNode//边表 {int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置 struct ArcNode *next;}ArcNode;typedef struct VNode //顶单个点 {VertexType vertex;struct ArcNode *firstarc;}VNode;typedef struct //顶点表 {VNode AdjList[VertexMax];//由顶点构成的结构体数组 int vexnum,arcnum; //顶点数和边数 }ALGraph;/*循环队列结构体*/typedef struct{dataType *base;int front;int rear;}CyQueue;/*无向图UDG基本操作*/int LocateVex(ALGraph *G,VertexType v){ int i;for(i=0;i<G->vexnum;i++){if(v==G->AdjList[i].vertex){return i;}}printf("No Such Vertex!n");return -1;}//2.无向图 void CreateUDG(ALGraph *G){int i,j;//1.输入顶点数和边数printf("输入顶点个数和边数：n");printf("顶点数 n="); scanf("%d",&G->vexnum);printf("边 数 e="); scanf("%d",&G->arcnum);printf("n"); printf("n");//2.顶点表数据域填值初始化顶点表指针域printf("输入顶点元素(无需空格隔开)：");for(i=0;i<G->vexnum;i++){scanf(" %c",&G->AdjList[i].vertex);G->AdjList[i].firstarc=NULL;} printf("n");//3.输入边信息构造邻接表int n,m;VertexType v1,v2;ArcNode *p1,*p2; printf("请输入边的信息：nn"); for(i=0;i<G->arcnum;i++){ //输入边信息，并确定v1和v2在G中的位置，即顶点在AdjList[]数组中的位置（下标） printf("输入第%d条边信息：",i+1); scanf(" %c%c",&v1,&v2);n=LocateVex(G,v1);m=LocateVex(G,v2);if(n==-1||m==-1) { printf("NO This Vertex!n"); return; } p1=(ArcNode *)malloc(sizeof(ArcNode));p1->adjvex=m;//填上坐标 p1->next=G->AdjList[n].firstarc;//改链（头插法） G->AdjList[n].firstarc=p1;p2=(ArcNode *)malloc(sizeof(ArcNode));//无向图的对称 p2->adjvex=n;p2->next=G->AdjList[m].firstarc;G->AdjList[m].firstarc=p2;}//for } void print(ALGraph G){int i;ArcNode *p;printf("n-------------------------------");printf("n图的邻接表表示：n");for(i=0;i<G.vexnum;i++){printf("n AdjList[%d]%4c",i,G.AdjList[i].vertex);p=G.AdjList[i].firstarc;while(p!=NULL){printf("-->%d",p->adjvex);p=p->next;} } printf("n");} /*循环队列基本操作*/void create(CyQueue *q){q->base=(dataType *)malloc(Maxsize*sizeof(dataType));if(!q->base){printf("Space allocation failed!n");return;}q->front=q->rear=0;return;}void EnQueue(CyQueue *q,dataType value){if((q->rear+1)%Maxsize==q->front){printf("Cyclic Queue is Full!n");return;}q->base[q->rear]=value;q->rear=(q->rear+1)%Maxsize;return;}void DeQueue(CyQueue *q,dataType *value){if(q->front==q->rear){printf("Cyclic Queue is Empty!n");return;}*value=q->base[q->front];q->front=(q->front+1)%Maxsize;return;} int QueueEmpty(CyQueue *q){ if (q->front==q->rear)//队列为空返回1，不为空返回0 { return 1; } return 0;}/*广度优先遍历*/int visited[VertexMax]; //定义数组为全局变量 void BFS(ALGraph *G,int i){int j;struct ArcNode *p;CyQueue q;create(&q); //1.设置起始点printf("%c",G->AdjList[i].vertex);//1.输出起始结点visited[i]=1;//2.将已访问的结点标志成1EnQueue(&q,i);//3.将第一个结点入队 //2.由起始点开始，对后续结点进行操作while(!QueueEmpty(&q)){p=G->AdjList[i].firstarc;DeQueue(&q,&i);while(p!=NULL){if(visited[p->adjvex]==0){printf("%c",G->AdjList[p->adjvex].vertex); visited[p->adjvex]=1; EnQueue(&q,p->adjvex);}p=p->next;//查找完之后，将p向后推一位 }} } void BFSTraverse(ALGraph *G){int i;//数组初始化为全0 for(i=0;i<G->vexnum;i++){visited[i]=0;} for(i=0;i<G->vexnum;i++){if(visited[i]==0){BFS(G,i);}}} int main() {ALGraph G; CreateUDG(&G);print(G); printf("nn广度优先遍历："); BFSTraverse(&G); return 0;} 执行结果 邻接矩阵邻接表