无向图创建邻接表
时间: 2023-07-16 11:13:16 浏览: 147
邻接表是一种表示图的数据结构,可以用于存储无向图的信息。它将每个顶点与其相邻的顶点列表关联起来。
下面是创建无向图邻接表的步骤:
1. 定义一个包含 n 个链表的数组,其中 n 是图中顶点的数量。
2. 遍历图的每个边,将每条边所连接的两个顶点分别加入到对方的链表中。
3. 如果边是自环边,则只需将一个顶点加入到其自身链表中即可。
以下是一个示例代码,用于创建一个无向图的邻接表:
```python
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++
#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方法来打印出每个顶点的邻接表和逆邻接表。
示例代码:
阅读全文