用c语言邻接表作为图的存储结构建立一个图,并对此图分别进行深度优先搜索和广度优先搜索遍历
时间: 2024-02-09 07:08:13 浏览: 31
好的,我来回答你的问题。
首先,我们需要了解什么是邻接表。邻接表是一种图的存储结构,它将每个顶点的所有邻居顶点存储在一个链表中。邻接表通常用于存储稀疏图,因为它不会浪费太多空间。
现在,让我们来建立一个图并用邻接表来存储它。假设我们有以下这个图:
```
0 -- 1
|\ |
| \ |
3 -- 2
```
我们可以将它表示为一个邻接表,如下所示:
```
0: 1 -> 3
1: 0 -> 2
2: 1 -> 3
3: 0 -> 2
```
现在,让我们来分别对这个图进行深度优先搜索和广度优先搜索。
深度优先搜索(DFS)是一种遍历图的算法,它从一个顶点开始,沿着一条路径一直走到底,然后返回并探索其他路径。DFS通常使用递归或栈来实现。
下面是使用 DFS 遍历上面那个图的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *firstarc;
}VNode;
typedef struct{
VNode vertices[MAX_VERTEX_NUM];
int vexnum, arcnum;
}ALGraph;
void CreateGraph(ALGraph *G){
printf("输入顶点数和边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for(int i=0;i<G->vexnum;++i){
printf("输入第%d个顶点:",i+1);
scanf("%d",&G->vertices[i].data);
G->vertices[i].firstarc=NULL;
}
for(int k=0;k<G->arcnum;++k){
int i,j;
printf("输入边(vi,vj)的顶点序号i和j:");
scanf("%d%d",&i,&j);
ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j-1;
p->nextarc=G->vertices[i-1].firstarc;
G->vertices[i-1].firstarc=p;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=i-1;
p->nextarc=G->vertices[j-1].firstarc;
G->vertices[j-1].firstarc=p;
}
}
void DFS(ALGraph *G,int v,int *visited){
printf("%d ",G->vertices[v].data);
visited[v]=1;
for(ArcNode *p=G->vertices[v].firstarc;p;p=p->nextarc){
int j=p->adjvex;
if(!visited[j])
DFS(G,j,visited);
}
}
void DFSTraverse(ALGraph *G){
int visited[MAX_VERTEX_NUM]={0};
for(int i=0;i<G->vexnum;++i){
if(!visited[i])
DFS(G,i,visited);
}
}
void BFS(ALGraph *G,int v,int *visited){
int queue[MAX_VERTEX_NUM]={0};
int head=0,tail=0;
printf("%d ",G->vertices[v].data);
visited[v]=1;
queue[tail++]=v;
while(head<tail){
int k=queue[head++];
for(ArcNode *p=G->vertices[k].firstarc;p;p=p->nextarc){
int j=p->adjvex;
if(!visited[j]){
printf("%d ",G->vertices[j].data);
visited[j]=1;
queue[tail++]=j;
}
}
}
}
void BFSTraverse(ALGraph *G){
int visited[MAX_VERTEX_NUM]={0};
for(int i=0;i<G->vexnum;++i){
if(!visited[i])
BFS(G,i,visited);
}
}
int main(){
ALGraph G;
CreateGraph(&G);
printf("DFS遍历顶点:");
DFSTraverse(&G);
printf("\nBFS遍历顶点:");
BFSTraverse(&G);
printf("\n");
return 0;
}
```
使用上面的算法,对于上面的图,DFS会按照以下顺序遍历节点:0 -> 1 -> 2 -> 3,BFS会按照以下顺序遍历节点:0 -> 1 -> 3 -> 2。