一、要求
1.设计并验证如下算法：图采用邻接矩阵表示，实现无向图的深度优先搜索与有向图的广度优先搜索。
2.设计并验证如下算法：带权图采用邻接表表示，实现无向图的广度优先搜索与有向图的深度优先搜索。
二、代码
1.
#include<stdio.h> #include<stdlib.h> #include<time.h> #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef struct queue { int Data[MAX_VERTEX_NUM]; int front; int rear; }SqQueue; int visited[MAX_VERTEX_NUM];//1--已访问 0--未访问 typedef struct mgraph { char vexs[MAX_VERTEX_NUM];//顶点向量 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 int vexnum;//图的顶点数 }Mgraph; void init_queue(SqQueue *); void EnQueue(SqQueue *,int); void DeQueue(SqQueue *); int empty_queue(SqQueue *); void DFS(Mgraph G,int v); void DFSTraverse(Mgraph G); void BFSTraverse(Mgraph G); int main() { Mgraph G; printf("请输入图的顶点数\n"); scanf("%d",&G.vexnum); printf("输入图的各个顶点向量\n"); scanf("%s",&G.vexs); srand((unsigned)time(NULL)); for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵 { for(int j=0;j<G.vexnum;j++) G.arcs[i][j]=rand()%2; } printf("该图的邻接矩阵如下：\n"); for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵 { for(int j=0;j<G.vexnum;j++) printf("%d ",G.arcs[i][j]); printf("\n"); } printf("深度优先遍历结果如下：\n"); DFSTraverse(G); printf("\n"); printf("广度优先遍历结果如下：\n"); BFSTraverse(G); return 0; } void DFSTraverse(Mgraph G) { for(int v=0;v<G.vexnum;v++)//标记赋值为未访问 visited[v]=0; for(int v=0;v<G.vexnum;v++)//调用DFS if(!visited[v]) DFS(G,v); } void DFS(Mgraph G,int v) { visited[v]=1; printf("%c ",G.vexs[v]); for(int n=0;n<G.vexnum;n++) { if((visited[n]==0)&&(G.arcs[v][n]==1)) DFS(G,n); } } void BFSTraverse(Mgraph G)//广度优先遍历 { SqQueue Q; for(int i=0;i<G.vexnum;i++) visited[i]=0; init_queue(&Q); for(int i=0;i<G.vexnum;i++) { if(!visited[i]) { visited[i]=1; printf("%c ",G.vexs[i]); EnQueue(&Q,i); } while(!empty_queue(&Q)) { DeQueue(&Q); for(int j=0;j<G.vexnum;j++) { if(!visited[j]&&G.arcs[i][j]) { visited[j]=1; printf("%c ",G.vexs[j]); EnQueue(&Q,j); } } } } } void init_queue(SqQueue *Q) { Q->front=Q->rear=0; } void EnQueue(SqQueue *Q,int e) { Q->Data[Q->rear]=e; Q->rear++; } void DeQueue(SqQueue *Q) { Q->front++; } int empty_queue(SqQueue *Q) { if(Q->front==Q->rear) return 1; else return 0; }
运行结果
文章来源：https://www.toymoban.com/news/detail-760083.html
2.
#include<stdio.h> #include<stdlib.h> #define MAX_SIZE 20 int visited[MAX_SIZE]; typedef struct queue { int Data[MAX_SIZE]; int front; int rear; }SqQueue; typedef struct ArcNode { int adjvex;//该弧指向顶点的位置 struct ArcNode *next; }ArcNode; typedef struct vnode { int data;//顶点信息 ArcNode *first;//指向第一条依附该顶点的弧的指针 }VNode; typedef struct { VNode vertices[MAX_SIZE]; int vexnum; int edgenum; }ALGraph; void init_queue(SqQueue *); void EnQueue(SqQueue *,int); void DeQueue(SqQueue *); int empty_queue(SqQueue *); void DFSTraverse(ALGraph *G); void DFS(ALGraph *G,int v); void BFSTraverse(ALGraph G); void createALGraph(ALGraph *); int main() { ALGraph G; createALGraph(&G); DFSTraverse(&G); printf("\n"); BFSTraverse(G); return 0; } void DFSTraverse(ALGraph *G) { for(int v=0;v<G->vexnum;v++)//标记赋值为未访问 visited[v]=0; for(int v=0;v<G->vexnum;v++)//调用DFS if(!visited[v]) DFS(G,v); } void DFS(ALGraph *G,int v) { ArcNode *p; p = G->vertices[v].first; visited[v]=1; printf("%d ",G->vertices[v].data); while(p) { if(!visited[p->adjvex]) DFS(G,p->adjvex); p=p->next; } } void BFSTraverse(ALGraph G) { SqQueue Q; ArcNode *p; for(int i=0;i<G.vexnum;i++) visited[i]=0; init_queue(&Q); for(int i=0;i<G.vexnum;i++) { p = G.vertices[0].first; if(!visited[i]) { visited[i]=1; printf("%d ",G.vertices[i].data); EnQueue(&Q,i); } while(!empty_queue(&Q)) { DeQueue(&Q); while(p) { if(!visited[p->adjvex]) { visited[p->adjvex]=1; printf("%d ",G.vertices[p->adjvex].data); EnQueue(&Q,i); } p=p->next; } } } } void init_queue(SqQueue *Q) { Q->front=Q->rear=0; } void EnQueue(SqQueue *Q,int e) { Q->Data[Q->rear]=e; Q->rear++; } void DeQueue(SqQueue *Q) { Q->front++; } int empty_queue(SqQueue *Q) { if(Q->front==Q->rear) return 1; else return 0; } void createALGraph(ALGraph *G) { int i, j; ArcNode *e; printf("输入顶点数和边数：\n"); scanf("%d %d",&G->vexnum,&G->edgenum); printf("输入顶点"); for(i = 0; i < G->vexnum; i++) { scanf("%d", &G->vertices[i].data); G->vertices[i].first = NULL; } //输入边 printf("输入边（i, j）上的顶点：\n"); for(int k = 0; k < G->edgenum; k++) { scanf("%d %d", &i, &j); e = (ArcNode *) malloc (sizeof (ArcNode)); e->adjvex = j; e->next = G->vertices[i].first; G->vertices[i].first = e; e = (ArcNode *) malloc (sizeof (ArcNode)); e->adjvex = i; e->next = G->vertices[j].first; G->vertices[j].first= e; } }
运行结果：
文章来源地址https://www.toymoban.com/news/detail-760083.html
到了这里，关于数据结构 图及其应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
