写一段c语言代码并实现以下功能:创建有向带权图的邻接矩阵和邻接表存储结构并输出;分别在邻接矩阵和邻接表存储结构下求图中每个顶点的入度;分别在邻接矩阵和邻接表存储结构下对图进行深度和广度优先遍历。
时间: 2024-03-09 08:49:08 浏览: 100
邻接表存储的有向图的基本操作(C语言实现)
好的,以下是一段实现您要求功能的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 边结构体
typedef struct EdgeNode {
int adjvex; // 相邻节点编号
int weight; // 边的权重
struct EdgeNode *next; // 下一个边节点
} EdgeNode;
// 顶点结构体
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode *first_edge; // 第一条边节点
} VertexNode;
// 邻接表
typedef struct {
VertexNode adj_list[MAX_VERTEX_NUM]; // 顶点数组
int vertex_num; // 顶点数
int edge_num; // 边数
} GraphAdjList;
// 邻接矩阵
typedef struct {
int adj_matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int edge_num; // 边数
} GraphAdjMatrix;
// 初始化邻接表
void initGraphAdjList(GraphAdjList *graph) {
int i;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
graph->adj_list[i].data = 0;
graph->adj_list[i].first_edge = NULL;
}
graph->vertex_num = 0;
graph->edge_num = 0;
}
// 添加边到邻接表
void addEdgeToList(GraphAdjList *graph, int start, int end, int weight) {
EdgeNode *new_edge = (EdgeNode *)malloc(sizeof(EdgeNode));
new_edge->adjvex = end;
new_edge->weight = weight;
new_edge->next = graph->adj_list[start].first_edge;
graph->adj_list[start].first_edge = new_edge;
graph->edge_num++;
}
// 初始化邻接矩阵
void initGraphAdjMatrix(GraphAdjMatrix *graph) {
int i, j;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
for (j = 0; j < MAX_VERTEX_NUM; j++) {
graph->adj_matrix[i][j] = 0;
}
}
graph->vertex_num = 0;
graph->edge_num = 0;
}
// 添加边到邻接矩阵
void addEdgeToMatrix(GraphAdjMatrix *graph, int start, int end, int weight) {
graph->adj_matrix[start][end] = weight;
graph->edge_num++;
}
// 创建有向带权图
void createGraph(GraphAdjList *graph_list, GraphAdjMatrix *graph_matrix) {
int i, start, end, weight;
printf("请输入图的顶点数和边数(用空格隔开):");
scanf("%d %d", &graph_list->vertex_num, &graph_list->edge_num);
graph_matrix->vertex_num = graph_list->vertex_num;
for (i = 0; i < graph_list->edge_num; i++) {
printf("请输入第%d条边的起点、终点和权重(用空格隔开):", i+1);
scanf("%d %d %d", &start, &end, &weight);
addEdgeToList(graph_list, start, end, weight);
addEdgeToMatrix(graph_matrix, start, end, weight);
}
}
// 输出邻接表
void printGraphAdjList(GraphAdjList graph) {
int i;
EdgeNode *p;
for (i = 0; i < graph.vertex_num; i++) {
printf("%d -> ", graph.adj_list[i].data);
p = graph.adj_list[i].first_edge;
while (p != NULL) {
printf("%d(%d) -> ", p->adjvex, p->weight);
p = p->next;
}
printf("NULL\n");
}
}
// 输出邻接矩阵
void printGraphAdjMatrix(GraphAdjMatrix graph) {
int i, j;
for (i = 0; i < graph.vertex_num; i++) {
for (j = 0; j < graph.vertex_num; j++) {
printf("%d ", graph.adj_matrix[i][j]);
}
printf("\n");
}
}
// 求每个顶点的入度(邻接矩阵)
void getInDegreeMatrix(GraphAdjMatrix graph, int *in_degree) {
int i, j;
for (i = 0; i < graph.vertex_num; i++) {
in_degree[i] = 0;
for (j = 0; j < graph.vertex_num; j++) {
if (graph.adj_matrix[j][i] != 0) {
in_degree[i]++;
}
}
}
}
// 求每个顶点的入度(邻接表)
void getInDegreeList(GraphAdjList graph, int *in_degree) {
int i;
EdgeNode *p;
for (i = 0; i < graph.vertex_num; i++) {
in_degree[i] = 0;
}
for (i = 0; i < graph.vertex_num; i++) {
p = graph.adj_list[i].first_edge;
while (p != NULL) {
in_degree[p->adjvex]++;
p = p->next;
}
}
}
// 深度优先遍历(邻接矩阵)
void dfsMatrix(GraphAdjMatrix graph, int start, int *visited) {
int i;
visited[start] = 1;
printf("%d -> ", start);
for (i = 0; i < graph.vertex_num; i++) {
if (graph.adj_matrix[start][i] != 0 && !visited[i]) {
dfsMatrix(graph, i, visited);
}
}
}
// 深度优先遍历(邻接表)
void dfsList(GraphAdjList graph, int start, int *visited) {
EdgeNode *p;
visited[start] = 1;
printf("%d -> ", start);
p = graph.adj_list[start].first_edge;
while (p != NULL) {
if (!visited[p->adjvex]) {
dfsList(graph, p->adjvex, visited);
}
p = p->next;
}
}
// 广度优先遍历(邻接矩阵)
void bfsMatrix(GraphAdjMatrix graph, int start, int *visited) {
int i, queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[start] = 1;
printf("%d -> ", start);
queue[rear++] = start;
while (front != rear) {
start = queue[front++];
for (i = 0; i < graph.vertex_num; i++) {
if (graph.adj_matrix[start][i] != 0 && !visited[i]) {
visited[i] = 1;
printf("%d -> ", i);
queue[rear++] = i;
}
}
}
}
// 广度优先遍历(邻接表)
void bfsList(GraphAdjList graph, int start, int *visited) {
int i, queue[MAX_VERTEX_NUM], front = 0, rear = 0;
EdgeNode *p;
visited[start] = 1;
printf("%d -> ", start);
queue[rear++] = start;
while (front != rear) {
start = queue[front++];
p = graph.adj_list[start].first_edge;
while (p != NULL) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%d -> ", p->adjvex);
queue[rear++] = p->adjvex;
}
p = p->next;
}
}
}
int main() {
GraphAdjList graph_list;
GraphAdjMatrix graph_matrix;
int in_degree[MAX_VERTEX_NUM], visited[MAX_VERTEX_NUM];
int i;
initGraphAdjList(&graph_list);
initGraphAdjMatrix(&graph_matrix);
createGraph(&graph_list, &graph_matrix);
printf("邻接表:\n");
printGraphAdjList(graph_list);
printf("邻接矩阵:\n");
printGraphAdjMatrix(graph_matrix);
printf("邻接矩阵中每个顶点的入度:\n");
getInDegreeMatrix(graph_matrix, in_degree);
for (i = 0; i < graph_matrix.vertex_num; i++) {
printf("%d ", in_degree[i]);
}
printf("\n");
printf("邻接表中每个顶点的入度:\n");
getInDegreeList(graph_list, in_degree);
for (i = 0; i < graph_list.vertex_num; i++) {
printf("%d ", in_degree[i]);
}
printf("\n");
printf("邻接矩阵深度优先遍历:\n");
for (i = 0; i < graph_matrix.vertex_num; i++) {
visited[i] = 0;
}
for (i = 0; i < graph_matrix.vertex_num; i++) {
if (!visited[i]) {
dfsMatrix(graph_matrix, i, visited);
}
}
printf("NULL\n");
printf("邻接表深度优先遍历:\n");
for (i = 0; i < graph_list.vertex_num; i++) {
visited[i] = 0;
}
for (i = 0; i < graph_list.vertex_num; i++) {
if (!visited[i]) {
dfsList(graph_list, i, visited);
}
}
printf("NULL\n");
printf("邻接矩阵广度优先遍历:\n");
for (i = 0; i < graph_matrix.vertex_num; i++) {
visited[i] = 0;
}
for (i = 0; i < graph_matrix.vertex_num; i++) {
if (!visited[i]) {
bfsMatrix(graph_matrix, i, visited);
}
}
printf("NULL\n");
printf("邻接表广度优先遍历:\n");
for (i = 0; i < graph_list.vertex_num; i++) {
visited[i] = 0;
}
for (i = 0; i < graph_list.vertex_num; i++) {
if (!visited[i]) {
bfsList(graph_list, i, visited);
}
}
printf("NULL\n");
return 0;
}
```
您可以直接复制上述代码并编译运行,即可得到您想要的结果。
阅读全文