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

邻接矩阵是一种用于表示图形的数据结构，其中图形中的每个节点都被表示为一个矩阵中的行和列。如果图形中存在一条从节点A到节点B的边，则在邻接矩阵中会将A行B列的元素设为1，否则设为0。

邻接表是另一种用于表示图形的数据结构，其中每个节点都有一个指针指向其相邻的节点的列表。

要将邻接矩阵转换为邻接表，可以使用以下步骤：

1. 首先，创建一个由邻接表表示的图形。
2. 然后，遍历邻接矩阵的每一行和每一列，并检查其中的元素。
3. 如果发现邻接矩阵中的元素为1，则表示图形中存在一条从当前行所表示的节点到当前列所表示的节点的边。
4. 在邻接表中，为当前行所表示的节点创建一个新的节点，并将其指针设为当前列所表示的节点。
5. 重复步骤2至4，直到遍历完整个邻接矩阵为止。

例如，假设我们有一个邻接矩阵，如下所示：

0 1 1 0
1 0 1 0
1 1 0

相关问题

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

邻接矩阵转换为邻接表需要以下步骤：

1. 定义邻接表结构体，包含顶点数量和指向每个顶点邻居的指针数组。

struct Graph {
    int V; // 顶点数量
    struct Node** adjList; // 指向邻居的指针数组
};

struct Node {
    int dest;
    struct Node* next;
};

2. 根据邻接矩阵创建邻接表。遍历邻接矩阵的每一个元素，如果该元素的值为1，就在邻接表中加入该边。

struct Graph* createGraph(int V, int** edges, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjList = (struct Node**) malloc(V * sizeof(struct Node*));

    // 初始化邻接表为空
    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }

    // 添加边到邻接表
    for (int i = 0; i < E; i++) {
        int src = edges[i][0];
        int dest = edges[i][1];

        // 添加从 src 到 dest 的边
        struct Node* newNode = createNode(dest);
        newNode->next = graph->adjList[src];
        graph->adjList[src] = newNode;

        // 添加从 dest 到 src 的边
        newNode = createNode(src);
        newNode->next = graph->adjList[dest];
        graph->adjList[dest] = newNode;
    }

    return graph;
}

3. 定义创建邻接表节点的函数。

struct Node* createNode(int dest) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

完整代码如下：

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

struct Graph {
    int V; // 顶点数量
    struct Node** adjList; // 指向邻居的指针数组
};

struct Node {
    int dest;
    struct Node* next;
};

struct Graph* createGraph(int V, int** edges, int E);
struct Node* createNode(int dest);

int main() {
    int V = 5;
    int E = 7;

    int edges[][2] = {
        { 0, 1 }, { 0, 4 }, { 1, 2 }, { 1, 3 },
        { 1, 4 }, { 2, 3 }, { 3, 4 }
    };

    struct Graph* graph = createGraph(V, edges, E);

    for (int i = 0; i < V; i++) {
        printf("顶点 %d 的邻居: ", i);
        struct Node* temp = graph->adjList[i];
        while (temp) {
            printf("%d -> ", temp->dest);
            temp = temp->next;
        }
        printf("NULL\n");
    }

    return 0;
}

struct Graph* createGraph(int V, int** edges, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjList = (struct Node**) malloc(V * sizeof(struct Node*));

    // 初始化邻接表为空
    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }

    // 添加边到邻接表
    for (int i = 0; i < E; i++) {
        int src = edges[i][0];
        int dest = edges[i][1];

        // 添加从 src 到 dest 的边
        struct Node* newNode = createNode(dest);
        newNode->next = graph->adjList[src];
        graph->adjList[src] = newNode;

        // 添加从 dest 到 src 的边
        newNode = createNode(src);
        newNode->next = graph->adjList[dest];
        graph->adjList[dest] = newNode;
    }

    return graph;
}

struct Node* createNode(int dest) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

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开始广度优先遍历
        }
    }
}