本文主要是介绍数组模拟邻接表-头插法(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数组模拟邻接表-头插法
有权有向图
![在这里插入图片描述](/upload/202109/09/202109091104166039.png)
![在这里插入图片描述](/upload/202109/09/202109091104167802.png)
结构体方式实现:
#include <iostream>
#include <iomanip>
#define V 10000 //开的数组顶点最大值的容量
using namespace std;
struct Edge //边的结构体
{
int to; //边要指向的点
int w; //边的权值
int next; //存储当前边的编号的下一条边的编号
} e[V << 1]; //
int idx = 0; //当前边的编号
int head[V << 1]; //表头数组,存放当前顶点i的出边的编号
int n, m; //要插入的顶点的数量和边的数量
//在邻接表中插入一条带权值的边
void addEdge(int u, int v, int w)
{
e[++idx].to = v; //当前边编号idx所指向的顶点
e[idx].w = w; //当前边编号idx的权值
e[idx].next = head[u]; //当前边编号idx指向的边的编号,头插法
head[u] = idx; //更新当前u所在的表头数组的边的编号idx
}
void print()
{
for (int i = 1; i <= n; i++)
{
for (int j = head[i]; j != 0; j = e[j].next)
{
cout << i << " " << e[j].to << " " << e[j].w << endl;
}
}
}
int main(int argc, char const *argv[])
{
//顶点4个,边6条
n = 4, m = 6;
//初始化表头数组head
memset(head, 0, sizeof(head));
//初始化e结构
for (int i = 1; i <= n; i++)
{
e[i].to = 0;
e[i].next = 0;
e[i].w = 0;
}
//添加带权值的边
addEdge(1, 2, 10);
addEdge(1, 3, 7);
addEdge(3, 4, 9);
addEdge(2, 3, 8);
addEdge(2, 4, 12);
addEdge(1, 4, 11);
// 打印
print();
return 0;
}
数组方式实现:
#include <iostream>
using namespace std;
#define V 1000 //开的数组顶点最大值的容量
int idx = 0; //边的编号
int head[V]; //表头数组,存储当前顶点i的出边的编号idx
int to[V << 1]; //终点数组,存储编号idx号边的终点,也是顶点i的邻接点
int W[V << 1]; //边权数组,存储编号idx号边的权值,即顶点i指向to[idx]的权值
int nxt[V << 1]; //指针数组,存储编号idx号边的下一条边
void addEdge(int u, int v, int w) //添加边
{
nxt[++idx] = head[u]; //当前边编号idx指向的边的编号,头插法
to[idx] = v; //当前边编号idx所指向的顶点
W[idx] = w; //当前边编号idx的权值
head[u] = idx; //更新当前u所在的表头数组的边的编号idx
}
int n, m; //要插入的顶点的数量和边的数量
void print()
{
//邻接表访问
for (int i = 1; i <= n; i++)
{
for (int j = head[i]; j != 0; j = nxt[j]) //注意 j = nxt[j] 一直到该链表遍历结束
{
printf("%d, %d , %d \n", i, to[j], W[j]);
}
}
}
int main(int argc, char const *argv[])
{
//顶点4个,边6条
n = 4, m = 6;
//初始化表头数组head
memset(head, 0, sizeof(head));
//添加带权值的边
addEdge(1, 2, 10);
addEdge(1, 3, 7);
addEdge(3, 4, 9);
addEdge(2, 3, 8);
addEdge(2, 4, 12);
addEdge(1, 4, 11);
// 打印
print();
return 0;
}
无权有向图
#include <iostream>
using namespace std;
#define V 1000 //开的数组顶点最大值的容量
struct Edge
{
int to;
int next;
} e[V << 1];
int idx = 0;
int head[V << 1];
void addEdge(int u, int v)
{
e[++idx].to = v;
e[idx].next = head[u];
head[u] = idx;
}
int n, m;
void print()
{
for (int i = 1; i <= n; i++)
{
for (int j = head[i]; j != 0; j = e[j].next)
{
cout << i << " " << e[j].to << " " << endl;
}
}
}
int main(int argc, char const *argv[])
{
//顶点4个,边6条
n = 4, m = 6;
//初始化表头数组head
memset(head, 0, sizeof(head));
//初始化e结构
for (int i = 1; i <= n; i++)
{
e[i].to = 0;
e[i].next = 0;
}
//添加带权值的边
addEdge(1, 2);
addEdge(1, 3);
addEdge(3, 4);
addEdge(2, 3);
addEdge(2, 4);
addEdge(1, 4);
// 打印
print();
return 0;
}
无权无向图
有权无向图
这篇关于数组模拟邻接表-头插法(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!