用C语言结构体定义邻接矩阵和邻接表表示图的结构体

好的，以下是用C语言结构体定义邻接矩阵和邻接表表示图的结构体：

1. 邻接矩阵：

#define MAXVEX 100 // 最大顶点数

// 定义邻接矩阵结构体
typedef struct {
    int vexs[MAXVEX]; // 存储顶点信息
    int arc[MAXVEX][MAXVEX]; // 存储边信息
    int numVertexes, numEdges; // 顶点数和边数
} MGraph;

2. 邻接表：

#define MAXVEX 100 // 最大顶点数

// 定义邻接表结构体
typedef struct EdgeNode { // 边表结点
    int adjvex; // 邻接点域，存储该顶点对应的下标
    int weight; // 权值
    struct EdgeNode *next; // 链域，指向下一个邻接点
} EdgeNode;

typedef struct VertexNode { // 顶点表结点
    int data; // 顶点信息
    EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList; // 邻接表
    int numVertexes, numEdges; // 顶点数和边数
} GraphAdjList;

希望能够解答您的问题。

相关问题

用C语言分别定义图的邻接矩阵表示法和邻接表表示法的数据类型。 （写代码）

在C语言中，我们可以用不同的数据结构来表示图的邻接矩阵和邻接表。以下是这两种表示法的简单示例：

**邻接矩阵**：
邻接矩阵是一个二维数组，其中行代表源节点，列代表目标节点。如果两个节点之间有边，则对应位置的值通常是1（无向图）或一个特定的标识（有向图）。我们可以通过整型数组或者更复杂的数据结构（如`struct`或`union`）来实现。

typedef struct {
    int vertices; // 节点数
    int matrix[vertices][vertices]; // 邻接矩阵
} AdjMatrixGraph;

**邻接表**：
邻接表则是一个链表数组，每个元素是一个链表，包含从某一个节点出发的所有邻居节点。这里通常需要定义一个结构体来存储节点和其对应的链表节点。

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    int vertices;
    Node** adjacencyList; // 每个节点的链表指针
} AdjacencyListGraph;

用C语言实现使用邻接矩阵或链接表来存储图，并编程实现DFS和BFS算法

好的，这里给出使用邻接矩阵来存储图，并实现DFS和BFS算法的C语言代码示例。

首先，我们需要定义一个结构体来表示图：

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    int vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的邻接矩阵
    int vexnum; // 顶点数
    int arcnum; // 边数
} Graph;

其中，`vexs`数组存储顶点的值，`arcs`数组存储边的邻接矩阵，`vexnum`表示顶点数，`arcnum`表示边数。

接下来，我们可以定义一个函数来创建图：

void createGraph(Graph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入顶点的值：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }
    // 初始化邻接矩阵
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = 0;
        }
    }
    printf("请输入每条边的起点和终点：");
    int v1, v2;
    for (int k = 0; k < G->arcnum; k++) {
        scanf("%d %d", &v1, &v2);
        int i = locateVex(G, v1);
        int j = locateVex(G, v2);
        G->arcs[i][j] = 1;
        G->arcs[j][i] = 1; // 无向图需加上这行
    }
}

该函数从标准输入中读取顶点数和边数，以及每个顶点的值，然后根据输入的起点和终点在邻接矩阵中设置对应的边。

我们还需要一个函数来查找某个值对应的顶点在图中的位置：

int locateVex(Graph *G, int v) {
    for (int i = 0; i < G->vexnum; i++) {
        if (G->vexs[i] == v) {
            return i;
        }
    }
    return -1;
}

接下来，我们可以实现DFS算法：

void DFS(Graph *G, int v, int visited[]) {
    printf("%d ", G->vexs[v]);
    visited[v] = 1;
    for (int i = 0; i < G->vexnum; i++) {
        if (G->arcs[v][i] == 1 && visited[i] == 0) {
            DFS(G, i, visited);
        }
    }
}

该函数从给定的起点v开始，输出其值并将其标记为已访问，然后递归遍历所有与v相连的未访问过的顶点。

最后，我们可以实现BFS算法：

void BFS(Graph *G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    printf("%d ", G->vexs[v]);
    visited[v] = 1;
    queue[rear++] = v;
    while (front < rear) {
        int w = queue[front++];
        for (int i = 0; i < G->vexnum; i++) {
            if (G->arcs[w][i] == 1 && visited[i] == 0) {
                printf("%d ", G->vexs[i]);
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

该函数从给定的起点v开始，输出其值并将其标记为已访问，然后将其加入队列中。然后不断从队列中取出一个顶点，遍历其所有未访问过的邻接点，并将其加入队列中。

完整代码如下：