图的定义
图（graph）是一种非线性数据结构，由顶点和边组成。我们可以将图 抽象地表示为一组顶点和一组边的集合。G(V,E)
图分为有向图和无向图，下图带箭头为有向图，无箭头为无向图
我们可以用两种方式来表示图，邻接矩阵和邻接表，我们主要来讲一下邻接表
代码如下：
#include <iostream>
using namespace std;
#include <vector>// 定义链表节点结构
struct node
{int x; // 节点编号int w; // 某个起始点到x的边的权值node* next; // 指向下一个节点的指针// 节点构造函数node(int _x, int _w){this->x = _x; // 设置节点编号this->w = _w; // 设置边权值next = nullptr; // 初始化下一个节点指针为nullptr}
};vector<node*> head; // 创建一个节点指针的向量，表示图的邻接表// 添加边的函数
void add_edge(int u, int v, int w)
{node* a = head[u]; // 获取起始节点unode* b = new node(v, w); // 创建一个新节点b，表示边(u, v)及其权值wb->next = a->next; // 将b的next指针指向a的下一个节点a->next = b; // 将u的下一个节点指针指向b，形成边的连接
}int main()
{int n, m;cout << "输入节点数和边数: ";cin >> n >> m; // 输入节点数和边数head.resize(n + 1); // 调整head的大小以容纳所有节点（节点编号从1到n）for (int i = 0; i <= n; i++){head[i] = new node(i, 0); // 初始化每个节点}cout << "输入每条边的信息（格式: 起始节点 结束节点 权值）: " << endl;for (int i = 0; i < m; i++){int u, v, w;cin >> u >> v >> w; // 输入每条边的起始节点u、结束节点v和权值wadd_edge(u, v, w); // 添加边到邻接表中}// 输出邻接表cout << "邻接表: " << endl;for (int i = 1; i <= n; i++){node* p = head[i]->next; // 从节点i的下一个节点开始遍历while (p){cout << i << " -> " << p->x << " (权值: " << p->w << ")" << endl; // 输出当前节点及其边的目的节点和权值p = p->next; // 移动到下一个节点}}cout << endl;return 0;
}
用数组模拟空间来实现
我们来开四个数组，分别是 edge， next， head， weight
代码如下
#include <iostream>
using namespace std;
#include <vector>vector<int> head, edge, Next, weight; // 定义4个数组：head存储每个节点的头指针，edge存储边的目标节点，Next存储下一条边的索引，weight存储边的权值int idx = 0; // 记录边的数量，用于给边编号// 添加边的函数
void add_edge(int u, int v, int w)
{edge[idx] = v; // 设置边的目标节点为vweight[idx] = w; // 设置边的权值为wNext[idx] = head[u]; // 将当前节点的第一条边设置为u节点之前的第一条边（实现链表连接）head[u] = idx++; // 更新u的头指针为当前边，并递增边的计数
}int main()
{int n, m;cout << "输入节点数和边数: ";cin >> n >> m; // 输入节点数n和边数mhead.resize(n + 1, -1); // 初始化head数组，大小为n+1（节点编号从1到n），初始值为-1，表示没有边edge.resize(m + 1); // 初始化edge数组，大小为m+1Next.resize(m + 1); // 初始化Next数组，大小为m+1weight.resize(m + 1); // 初始化weight数组，大小为m+1cout << "输入每条边的信息（格式: 起始节点 结束节点 权值）: " << endl;for (int i = 0; i < m; i++){int u, v, w;cin >> u >> v >> w; // 输入每条边的起始节点u、结束节点v和权值wadd_edge(u, v, w); // 调用add_edge函数，将边添加到邻接表中}// 输出邻接表cout << "邻接表: " << endl;for (int i = 1; i <= n; i++){for (int j = head[i]; ~j /*j != -1*/; j = Next[j]) // 遍历与节点i相关的所有边{int u = i;int v = edge[j]; // 获取边的目标节点int w = weight[j]; // 获取边的权值cout << u << " -> " << v << " (权值: " << w << ")" << endl; // 输出该边}}cout << endl;return 0;
}
邻接表，数组模拟邻接表gitee源码