编写c语言代码实现如下操作 :分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。
- User
编写c语言代码实现如下操作 :分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。
- Assistant
邻接矩阵存储图的代码实现:
#include<stdio.h> #include<stdlib.h>
#define MAX_NUM 100
int graph[MAX_NUM][MAX_NUM];//邻接矩阵 int visited[MAX_NUM];//标记是否访问过
void DFS(int v, int vertexNum){ printf("%d ", v); visited[v] = 1; for(int i=0;i<vertexNum;i++){ if(graph[v][i]&&!visited[i]){ //如果有边相连并且未访问过 DFS(i, vertexNum); } } }
void BFS(int v, int vertexNum){ int queue[MAX_NUM]; int front=0, rear=0; visited[v] = 1; queue[rear++] = v;//进队列 while(front<rear){ //队列不为空 int cur = queue[front++]; //出队列 printf("%d ", cur); for(int i=0;i<vertexNum;i++){ if(graph[cur][i]&&!visited[i]){ //如果有边相连并且未访问过 visited[i]=1; queue[rear++]=i; } } } }
int main(){ int vertexNum;//顶点数 int edgeNum;//边数 int v1, v2;//边的两个顶点
printf("请输入顶点数和边数:"); scanf("%d%d", &vertexNum, &edgeNum); //初始化邻接矩阵和visited数组 for(int i=0;i<vertexNum;i++){ for(int j=0;j<vertexNum;j++){ graph[i][j]=0; } visited[i]=0; } //输入边 for(int i=0;i<edgeNum;i++){ printf("请输入第%d条边的两个顶点:", i+1); scanf("%d%d", &v1, &v2); graph[v1][v2] = graph[v2][v1] = 1;//建立双向边 } //深度优先遍历 printf("深度优先遍历结果为:"); for(int i=0;i<vertexNum;i++){ if(!visited[i]){//未访问过 DFS(i, vertexNum); } } printf("\n"); //初始化visited数组 for(int i=0;i<vertexNum;i++){ visited[i]=0; } //广度优先遍历 printf("广度优先遍历结果为:"); for(int i=0;i<vertexNum;i++){ if(!visited[i]){//未访问过 BFS(i, vertexNum); } } printf("\n"); return 0;}
邻接表存储图的代码实现:
#include<stdio.h> #include<stdlib.h>
#define MAX_NUM 100
typedef struct node{//链表结点 int vertex; struct node* next; }Node;
Node* graph[MAX_NUM];//邻接表 int visited[MAX_NUM];//标记是否访问过
void insert(int v1, int v2){ Node* p = (Node*)malloc(sizeof(Node)); p->vertex = v2; p->next = graph[v1]; graph[v1] = p;
p = (Node*)malloc(sizeof(Node)); p->vertex = v1; p->next = graph[v2]; graph[v2] = p;}
void visit(int v){ printf("%d ", v); }
void DFS(int v){ visited[v] = 1; visit(v); Node* p = graph[v]; while(p){ if(!visited[p->vertex]){ DFS(p->vertex); } p = p->next; } }
void BFS(int v){ int queue[MAX_NUM]; int front=0, rear=0; visited[v] = 1; visit(v); queue[rear++] = v; while(front<rear){ int cur = queue[front++]; p = graph[cur]; while(p){ if(!visited[p->vertex]){ visited[p->vertex] = 1; visit(p->vertex); queue[rear++] = p->vertex; } p = p->next; } } }
int main(){ int vertexNum;//顶点数 int edgeNum;//边数 int v1, v2;//边的两个顶点
printf("请输入顶点数和边数:"); scanf("%d%d", &vertexNum, &edgeNum); //初始化邻接表和visited数组 for(int i=0;i<vertexNum;i++){ graph[i] = NULL; visited[i] = 0; } //输入边 for(int i=0;i<edgeNum;i++){ printf("请输入第%d条边的两个顶点:", i+1); scanf("%d%d", &v1, &v2); insert(v1, v2);//建立单向边 } //深度优先遍历 printf("深度优先遍历结果为:"); for(int i=0;i<vertexNum;i++){ if(!visited[i]){//未访问过 DFS(i); } } printf("\n"); //初始化visited数组 for(int i=0;i<vertexNum;i++){ visited[i]=0; } //广度优先遍历 printf("广度优先遍历结果为:"); for(int i=0;i<vertexNum;i++){ if(!visited[i]){//未访问过 BFS(i); } } printf("\n"); return 0;}