以邻接表存储创建无向图的代码

以下是使用邻接表存储创建无向图的代码示例：

#include<iostream>
#include<vector>

using namespace std;

// 存储每个节点及其相邻节点的链表
struct Node{
    int val; // 节点值
    vector<int> adj; // 与该节点相邻的节点
};

int main(){
    int n, m; // n个节点，m条边
    cin >> n >> m;

    vector<Node> graph(n+1); // 存储图的数组，下标从1开始

    // 读入边并建立邻接表
    for(int i=0; i<m; i++){
        int u, v; // 边的两个节点
        cin >> u >> v;

        // 加入相邻节点
        graph[u].adj.push_back(v);
        graph[v].adj.push_back(u);
    }

    return 0;
}

以上代码中，我们利用结构体 `Node` 存储每个节点及其相邻节点的链表。在读入每条边时，我们将它的两个节点加入对方的相邻节点中，这样就建立了无向图的邻接表。

相关问题

创建邻接表存储的无向图，并输出图的邻接表。c语言

以下是创建邻接表存储的无向图的示例代码：

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

// 定义邻接表结构体
typedef struct node {
    int vertex;  // 顶点
    struct node* next;  // 指向下一个节点的指针
} Node;

// 定义无向图结构体
typedef struct graph {
    int num_vertices;  // 顶点数
    Node** adj_list;  // 邻接表数组
} Graph;

// 创建节点
Node* create_node(int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->vertex = v;
    node->next = NULL;
    return node;
}

// 创建无向图
Graph* create_graph(int num_vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    graph->adj_list = (Node**)malloc(num_vertices * sizeof(Node*));
    for (int i = 0; i < num_vertices; i++) {
        graph->adj_list[i] = NULL;
    }
    return graph;
}

// 添加边
void add_edge(Graph* graph, int src, int dest) {
    // 添加一条从src到dest的边
    Node* node = create_node(dest);
    node->next = graph->adj_list[src];
    graph->adj_list[src] = node;

    // 添加一条从dest到src的边
    node = create_node(src);
    node->next = graph->adj_list[dest];
    graph->adj_list[dest] = node;
}

// 打印邻接表
void print_graph(Graph* graph) {
    for (int i = 0; i < graph->num_vertices; i++) {
        printf("顶点 %d 的邻接表：", i);
        Node* temp = graph->adj_list[i];
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Graph* graph = create_graph(5);
    add_edge(graph, 0, 1);
    add_edge(graph, 0, 4);
    add_edge(graph, 1, 2);
    add_edge(graph, 1, 3);
    add_edge(graph, 1, 4);
    add_edge(graph, 2, 3);
    add_edge(graph, 3, 4);
    print_graph(graph);
    return 0;
}

输出结果：

顶点 0 的邻接表：4 -> 1 -> NULL
顶点 1 的邻接表：4 -> 3 -> 2 -> 0 -> NULL
顶点 2 的邻接表：3 -> 1 -> NULL
顶点 3 的邻接表：4 -> 2 -> 1 -> NULL
顶点 4 的邻接表：3 -> 1 -> 0 -> NULL

创建图的邻接表存储结构，并用邻接表表示法编写无向图的邻接表和逆邻接表，编写有向图的邻接表和有向图的逆邻接表，并输出。

邻接表是一种用于存储图的数据结构，它将每个顶点的所有邻接点存储在一个链表中。对于一个无向图，我们可以分别使用邻接表和逆邻接表来表示它，而对于有向图，则需要使用邻接表和有向图的逆邻接表来表示它。

以下是无向图和有向图的邻接表和逆邻接表的实现代码：

#include <iostream>
#include <vector>

using namespace std;

// 无向图的邻接表和逆邻接表
class UndirectedGraph {
public:
    // 初始化顶点数和边数
    UndirectedGraph(int vertices, int edges) {
        V = vertices;
        E = edges;
        adj = new vector<int>[V];
        reverse_adj = new vector<int>[V];
    }

    // 添加一条边
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
        reverse_adj[v].push_back(u);
        reverse_adj[u].push_back(v);
    }

    // 打印邻接表和逆邻接表
    void printGraph() {
        for (int i = 0; i < V; ++i) {
            cout << "顶点 " << i << " 的邻接表: ";
            for (auto x : adj[i])
                cout << "-> " << x;
            cout << endl;
            cout << "顶点 " << i << " 的逆邻接表: ";
            for (auto x : reverse_adj[i])
                cout << "-> " << x;
            cout << endl;
        }
    }

private:
    int V, E; // 顶点数和边数
    vector<int>* adj; // 邻接表
    vector<int>* reverse_adj; // 逆邻接表
};

// 有向图的邻接表和逆邻接表
class DirectedGraph {
public:
    // 初始化顶点数和边数
    DirectedGraph(int vertices, int edges) {
        V = vertices;
        E = edges;
        adj = new vector<int>[V];
        reverse_adj = new vector<int>[V];
    }

    // 添加一条边
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        reverse_adj[v].push_back(u);
    }

    // 打印邻接表和逆邻接表
    void printGraph() {
        for (int i = 0; i < V; ++i) {
            cout << "顶点 " << i << " 的邻接表: ";
            for (auto x : adj[i])
                cout << "-> " << x;
            cout << endl;
            cout << "顶点 " << i << " 的逆邻接表: ";
            for (auto x : reverse_adj[i])
                cout << "-> " << x;
            cout << endl;
        }
    }

private:
    int V, E; // 顶点数和边数
    vector<int>* adj; // 邻接表
    vector<int>* reverse_adj; // 逆邻接表
};

以上代码中，我们首先定义了一个UndirectedGraph类和一个DirectedGraph类来分别表示无向图和有向图。在这两个类中，我们都使用了vector来存储邻接表和逆邻接表。在初始化时，我们需要传入顶点数和边数，然后使用addEdge方法来添加一条边。最后，我们可以使用printGraph方法来打印出每个顶点的邻接表和逆邻接表。

示例代码：