c语言代码题 图的遍历 【问题描述】图的遍历操作是从图的某一顶点出发,依次访问图中其余顶点,且每个顶点仅被访问一次。请完成无向连通图的深度优先搜索和广度优先搜索【输入形式】输入数据为多组,每组数据包含多行,第一行为2个整数n,e,n为图的顶点数,e为边数,接下来是e行,每行2个整数,是一个顶点对,代表一条边所依附的两个顶点。例如,下图的输入数据为: 5 61 21 32 43 42 54 5 【输出形式】每个图的深度优先搜索和广度优先搜索序列,每个序列占一行,输出的每个顶点后有一个空格。
时间: 2023-05-29 07:06:28 浏览: 131
#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, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices; //图的邻接表
int vexnum, arcnum; //顶点数和边数
}ALGraph;
//访问顶点
void visit(int v){
printf("%d ", v);
}
//深度优先搜索
void DFS(ALGraph G, int v, int visited[]){
visited[v] = 1; //标记已访问
visit(v); //访问当前顶点
ArcNode *p = G.vertices[v].firstarc;
while(p){ //遍历该顶点的所有邻接点
int w = p->adjvex;
if(!visited[w]) //如果邻接点未被访问,则递归访问
DFS(G, w, visited);
p = p->nextarc;
}
}
//广度优先搜索
void BFS(ALGraph G, int v, int visited[]){
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[v] = 1; //标记已访问
visit(v); //访问当前顶点
queue[rear++] = v; //将当前顶点入队
while(front < rear){ //队列不为空时循环
int u = queue[front++]; //取出队头元素
ArcNode *p = G.vertices[u].firstarc;
while(p){ //遍历该顶点的所有邻接点
int w = p->adjvex;
if(!visited[w]){ //如果邻接点未被访问,则访问并入队
visited[w] = 1;
visit(w);
queue[rear++] = w;
}
p = p->nextarc;
}
}
}
int main(){
int n, e;
while(scanf("%d%d", &n, &e) == 2){
ALGraph G;
G.vexnum = n;
G.arcnum = e;
for(int i = 1; i <= n; i++){ //初始化邻接表
G.vertices[i].data = i;
G.vertices[i].firstarc = NULL;
}
for(int i = 1; i <= e; i++){ //建立邻接表
int u, v;
scanf("%d%d", &u, &v);
ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v;
p->nextarc = G.vertices[u].firstarc;
G.vertices[u].firstarc = p;
//无向图要建立双向边
ArcNode *q = (ArcNode*)malloc(sizeof(ArcNode));
q->adjvex = u;
q->nextarc = G.vertices[v].firstarc;
G.vertices[v].firstarc = q;
}
int visited[MAX_VERTEX_NUM] = {0}; //初始化访问标记数组
for(int i = 1; i <= n; i++){ //从未访问的顶点开始深度优先搜索
if(!visited[i]){
DFS(G, i, visited);
}
}
printf("\n");
for(int i = 1; i <= n; i++){ //初始化访问标记数组
visited[i] = 0;
}
for(int i = 1; i <= n; i++){ //从未访问的顶点开始广度优先搜索
if(!visited[i]){
BFS(G, i, visited);
}
}
printf("\n");
}
return 0;
}
阅读全文