c语言邻接矩阵初始化

邻接矩阵是用二维数组表示图的一种方式，其中数组中的元素表示图中的边。在C语言中，可以通过以下方式初始化邻接矩阵：

#define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES];

void initAdjMatrix(int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            adjMatrix[i][j] = 0; // 初始化为0，表示没有边相连
        }
    }
}

在上面的代码中，我们定义了一个常量`MAX_VERTICES`表示图中最多有多少个顶点，以及一个二维数组`adjMatrix`表示邻接矩阵。函数`initAdjMatrix`用于初始化邻接矩阵，参数`n`表示图中顶点的个数。在函数中，我们使用两个循环遍历邻接矩阵中的每一个元素，并将其初始化为0，表示没有边相连。如果有边相连，则可以将相应元素设置为1或其他权值。

相关问题

c语言邻接矩阵和邻接表

邻接矩阵实现图的深度优先遍历和广度优先遍历：

深度优先遍历：

1. 定义一个栈，将起始节点入栈。

2. 当栈不为空时，取出栈顶节点，访问该节点，并将其未被访问的邻居节点入栈。

3. 标记已访问的节点。

4. 重复步骤2和3，直到栈为空。

邻接矩阵实现深度优先遍历的代码：

#define MAX_VERTEX_NUM 100 //最大顶点数
#define INFINITY 65535 //表示无穷大

typedef struct {
    int vexs[MAX_VERTEX_NUM]; //顶点表
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
    int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;

int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过

void DFS(MGraph G, int v) {
    visited[v] = 1; //标记节点v已被访问
    printf("%d ", G.vexs[v]); //访问节点v
    for (int i = ; i < G.vexnum; i++) {
        if (G.arcs[v][i] != INFINITY && !visited[i]) { //如果节点i是节点v的邻居且未被访问
            DFS(G, i); //递归访问节点i
        }
    }
}

void DFSTraverse(MGraph G) {
    for (int i = ; i < G.vexnum; i++) {
        visited[i] = ; //初始化visited数组
    }
    for (int i = ; i < G.vexnum; i++) {
        if (!visited[i]) { //如果节点i未被访问
            DFS(G, i); //从节点i开始深度优先遍历
        }
    }
}

广度优先遍历：

1. 定义一个队列，将起始节点入队。

2. 当队列不为空时，取出队首节点，访问该节点，并将其未被访问的邻居节点入队。

3. 标记已访问的节点。

4. 重复步骤2和3，直到队列为空。

邻接矩阵实现广度优先遍历的代码：

#define MAX_VERTEX_NUM 100 //最大顶点数
#define INFINITY 65535 //表示无穷大

typedef struct {
    int vexs[MAX_VERTEX_NUM]; //顶点表
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
    int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;

int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过

void BFS(MGraph G, int v) {
    int queue[MAX_VERTEX_NUM]; //定义队列
    int front = , rear = ; //队首和队尾指针
    visited[v] = 1; //标记节点v已被访问
    printf("%d ", G.vexs[v]); //访问节点v
    queue[rear++] = v; //将节点v入队
    while (front != rear) { //队列不为空时
        int w = queue[front++]; //取出队首节点w
        for (int i = ; i < G.vexnum; i++) {
            if (G.arcs[w][i] != INFINITY && !visited[i]) { //如果节点i是节点w的邻居且未被访问
                visited[i] = 1; //标记节点i已被访问
                printf("%d ", G.vexs[i]); //访问节点i
                queue[rear++] = i; //将节点i入队
            }
        }
    }
}

void BFSTraverse(MGraph G) {
    for (int i = ; i < G.vexnum; i++) {
        visited[i] = ; //初始化visited数组
    }
    for (int i = ; i < G.vexnum; i++) {
        if (!visited[i]) { //如果节点i未被访问
            BFS(G, i); //从节点i开始广度优先遍历
        }
    }
}

邻接表实现图的深度优先遍历和广度优先遍历：

深度优先遍历：

1. 定义一个栈，将起始节点入栈。

2. 当栈不为空时，取出栈顶节点，访问该节点，并将其未被访问的邻居节点入栈。

3. 标记已访问的节点。

4. 重复步骤2和3，直到栈为空。

邻接表实现深度优先遍历的代码：

#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;

int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过

void DFS(ALGraph G, int v) {
    visited[v] = 1; //标记节点v已被访问
    printf("%d ", G.vertices[v].data); //访问节点v
    ArcNode *p = G.vertices[v].firstarc;
    while (p) {
        if (!visited[p->adjvex]) { //如果节点p->adjvex未被访问
            DFS(G, p->adjvex); //递归访问节点p->adjvex
        }
        p = p->nextarc;
    }
}

void DFSTraverse(ALGraph G) {
    for (int i = ; i < G.vexnum; i++) {
        visited[i] = ; //初始化visited数组
    }
    for (int i = ; i < G.vexnum; i++) {
        if (!visited[i]) { //如果节点i未被访问
            DFS(G, i); //从节点i开始深度优先遍历
        }
    }
}

广度优先遍历：

1. 定义一个队列，将起始节点入队。

2. 当队列不为空时，取出队首节点，访问该节点，并将其未被访问的邻居节点入队。

3. 标记已访问的节点。

4. 重复步骤2和3，直到队列为空。

邻接表实现广度优先遍历的代码：

#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;

int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过

void BFS(ALGraph G, int v) {
    int queue[MAX_VERTEX_NUM]; //定义队列
    int front = , rear = ; //队首和队尾指针
    visited[v] = 1; //标记节点v已被访问
    printf("%d ", G.vertices[v].data); //访问节点v
    queue[rear++] = v; //将节点v入队
    while (front != rear) { //队列不为空时
        int w = queue[front++]; //取出队首节点w
        ArcNode *p = G.vertices[w].firstarc;
        while (p) {
            if (!visited[p->adjvex]) { //如果节点p->adjvex未被访问
                visited[p->adjvex] = 1; //标记节点p->adjvex已被访问
                printf("%d ", G.vertices[p->adjvex].data); //访问节点p->adjvex
                queue[rear++] = p->adjvex; //将节点p->adjvex入队
            }
            p = p->nextarc;
        }
    }
}

void BFSTraverse(ALGraph G) {
    for (int i = ; i < G.vexnum; i++) {
        visited[i] = ; //初始化visited数组
    }
    for (int i = ; i < G.vexnum; i++) {
        if (!visited[i]) { //如果节点i未被访问
            BFS(G, i); //从节点i开始广度优先遍历
        }
    }
}

C语言 邻接矩阵转换为邻接表

邻接矩阵和邻接表是表示图的两种常见方式，其中邻接矩阵是通过二维数组来表示图的，而邻接表则是通过链表来表示图的。邻接表通常用于稀疏图的表示，而邻接矩阵则适用于稠密图的表示。

下面是将邻接矩阵转换为邻接表的C语言实现代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct EdgeNode{
    int adjvex; // 邻接点的位置
    struct EdgeNode *next; // 指向下一个邻接点的指针
}EdgeNode;

typedef struct VertexNode{
    int data; // 顶点的数据
    EdgeNode *firstedge; // 指向第一个邻接点的指针
}VertexNode, AdjList[MAX_VERTEX_NUM];

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

void CreateALGraph(GraphAdjList *G, int **matrix, int row, int col){
    G->numVertexes = row;
    G->numEdges = 0;

    for(int i = 0; i < G->numVertexes; i++){
        G->adjList[i].data = i; // 顶点数据
        G->adjList[i].firstedge = NULL; // 初始化邻接表的头指针
        for(int j = 0; j < G->numVertexes; j++){
            if(matrix[i][j] != 0){
                EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
                e->adjvex = j;
                e->next = G->adjList[i].firstedge;
                G->adjList[i].firstedge = e; // 将新建的边节点插入到邻接表中
                G->numEdges++; // 边数加一
            }
        }
    }
}

int main(){
    int matrix[5][5] = {
        {0, 1, 0, 1, 1},
        {1, 0, 1, 1, 0},
        {0, 1, 0, 1, 0},
        {1, 1, 1, 0, 1},
        {1, 0, 0, 1, 0}
    };
    GraphAdjList G;
    CreateALGraph(&G, (int**)matrix, 5, 5);

    // 打印邻接表
    for(int i = 0; i < G.numVertexes; i++){
        printf("%d: ", G.adjList[i].data);
        EdgeNode *e = G.adjList[i].firstedge;
        while(e != NULL){
            printf("%d ", e->adjvex);
            e = e->next;
        }
        printf("\n");
    }

    return 0;
}

上述代码中，CreateALGraph函数用于将邻接矩阵转换为邻接表，其中邻接表通过AdjList数组来表示，每个AdjList数组元素包括一个顶点的数据和一个指向第一个邻接点的指针。具体实现中，我们遍历邻接矩阵，如果矩阵元素不为0，则新建一个边节点，并将该节点插入到顶点的邻接表中。

最后，我们利用两层循环打印邻接表。