建图与遍历

图的存储方式

一、邻接矩阵

邻接矩阵是最简单的存储图的方式，用两个数组来保存数据：一个一维数组存储图中顶点信息，称为顶点数组；一个二维数组存储图中边或狐的信息，称为边数组。顶点数组中的数据是顶点信息。在无向图中，只要两点之间有边，那么array[x][y]就为1，若无边则为0；所以无向图是沿主对角线对称的。在有向图中，若有一条边由x指向y，则array[x][y]=1，否则为0；

二、Vector邻接表

定义一个容器数组，里面装的数据为结构体，其中，结构体中保存边的信息，分别表示这条边指向的边和边的权值。这样定义的含义为保存每个点所关联的边的信息。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1000;
struct Edge
{
int to;
int cost;
};
vector<Edge> vt[N];
//初始化容器数组，防止未更新数据的干扰
void init()
{
for (int i = 0; i < N; i++)
{
vt[i].clear();
}
}
void AddEdges(int s, int e, int cost)
{ //添加一条由点s指向点e的边，且存储边权cost值
struct Edge edge;
edge.to = e;
edge.cost = cost;
vt[s].push_back(edge);
return;
}
//查找所有与点s有关联的边以及边权信息
void Search(int s)
{
for (int i = 0; i < vt[s].size(); i++)
{
struct Edge edge = vt[s][i];
cout << "from" << s << "to" << edge.to << "and cost is" << edge.cost << endl;
}
}

三、链式前向星

使用邻接矩阵建图虽然直观但是遍历效果太低，并且不能处理重边（即图中有两条或者两条以上相同的边），适用于稠密图。Vector邻接表是使用STL中vector模拟链表，适用于稀疏图。而链式前向星是一种相对中庸的办法，但适用度最广，几乎在任何情况下代替两种建图方式。
链式前向星采用数组模拟链表的方式实现邻接表。
建立一个结构体，存储边的信息，其中edge[i].next指的是与第i条边同起点的下一边的存储位置，edge[i].to指的是第i条边的终点，edge[i].cost为第i条边的权值。head[]存储的是以i为起点的边存储的位置。

最后

以上就是包容豌豆为你收集整理的建图与遍历的全部内容，希望文章能够帮你解决建图与遍历所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。