一、要求
1.设计并验证如下算法：图采用邻接矩阵表示，实现无向图的深度优先搜索与有向图的广度优先搜索。
2.设计并验证如下算法：带权图采用邻接表表示，实现无向图的广度优先搜索与有向图的深度优先搜索。
二、代码
1.
#include#include#include#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef 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;}
运行结果
2.
#include#include #define MAX_SIZE 20int 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;vvexnum;v++)//标记赋值为未访问 visited[v]=0; for(int v=0;vvexnum;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 vexnum; i++) { scanf("%d", &G->vertices[i].data); G->vertices[i].first = NULL; } //输入边 printf("输入边（i, j）上的顶点：\n"); for(int k = 0; k 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; }}
运行结果：
