无向图创建邻接表

邻接表是一种表示图的数据结构，可以用于存储无向图的信息。它将每个顶点与其相邻的顶点列表关联起来。

下面是创建无向图邻接表的步骤：

1. 定义一个包含 n 个链表的数组，其中 n 是图中顶点的数量。
2. 遍历图的每个边，将每条边所连接的两个顶点分别加入到对方的链表中。
3. 如果边是自环边，则只需将一个顶点加入到其自身链表中即可。

以下是一个示例代码，用于创建一个无向图的邻接表：

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = [[] for _ in range(vertices)]
        
    def add_edge(self, u, v):
        # add edge u -> v
        self.adj_list[u].append(v)
        # add edge v -> u
        self.adj_list[v].append(u)

在此示例中，我们首先定义了一个 Graph 类，它包含一个 vertices 属性和一个 adj_list 属性，分别表示图中顶点的数量和邻接表。add_edge 方法用于将给定的两个顶点相互连接。对于无向图来说，需要同时在两个顶点的链表中加入对方。

相关问题

c语言无向图创建邻接表

创建邻接表可以通过链式存储结构实现。具体步骤如下：

1. 定义结构体`Node`表示图中的一个节点，其中包含一个整型变量`vertex`表示节点编号以及一个指向`struct Node`的指针`next`表示该节点的下一个节点。

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

2. 定义一个数组`adjList`，数组的每个元素是一个指向`struct Node`的指针，数组元素的下标表示节点的编号。

struct Node* adjList[MAX_N];

3. 对于每一条边(u, v)，创建一个新的节点`newNode`，将节点的`vertex`设置为v，然后将`newNode`插入到节点u的邻接表中。具体实现如下：

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = adjList[u];
adjList[u] = newNode;

完整代码如下：

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

#define MAX_N 1000

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

struct Node* adjList[MAX_N]; // 邻接表

void addEdge(int u, int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = adjList[u];
    adjList[u] = newNode;
}

int main() {
    int n, m; // n为节点数，m为边数
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        addEdge(v, u); // 如果是无向图，还需要加上边(v, u)
    }
    return 0;
}

创建无向图的邻接表c语言

以下是创建无向图的邻接表的C语言代码示例：

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

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

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

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

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));

    int i;
    for (i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph) {
    int v;
    for (v = 0; v < graph->numVertices; v++) {
        struct Node* temp = graph->adjLists[v];
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (temp) {
            printf("-> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);

    return 0;
}

这个例子中，我们创建了一个无向图的邻接表，它包含4个顶点。我们使用`createGraph`函数创建一个名为`graph`的指向图的结构体的指针。然后，我们使用`addEdge`函数添加顶点之间的边。最后，我们使用`printGraph`函数打印邻接表。

这个例子中的无向图如下所示：

     1
   /   \
  0     2
   \   /
     3

打印出来的邻接表如下所示：

 Adjacency list of vertex 0
 head -> 2-> 1

 Adjacency list of vertex 1
 head -> 2-> 0

 Adjacency list of vertex 2
 head -> 3-> 1-> 0

 Adjacency list of vertex 3
 head -> 2