成都创新互联网站建设,百度权重查询网站,文字图片在线生成器,sns社交网站 有哪些引言#xff1a; 建图#xff0c;将图放进内存的方法 常用的建图方式#xff1a;邻接矩阵#xff0c;邻接链表#xff0c;链式前向星
一、邻接矩阵 通过一个二维数组即可将图建立#xff0c;邻接矩阵#xff0c;考虑节点集合 #xff0c;用一个二维数组定义邻接矩…引言 建图将图放进内存的方法 常用的建图方式邻接矩阵邻接链表链式前向星
一、邻接矩阵 通过一个二维数组即可将图建立邻接矩阵考虑节点集合 用一个二维数组定义邻接矩阵满足以下 对于一个简单的有向图或无向图邻接矩阵如下 无向图若 u 与 v 之间存在一条边则 A[u][v]A[v][u]1 两个方向 有向图若有一条 u 指向 v 的边则 A[u][v]1若有一条 v 指向 u 的边则 A[v][u]1单向 邻接矩阵的空间消耗为无向图的邻接矩阵为对称矩阵。在某些情况下只存储邻接矩阵的对角线及以上的部分这样图占用的存储空间可以减少一半。
二、邻接链表vector建表 为一个包含 V 条链表的数组每个节点有一个链表对于每个节点u∈V邻接链表Adj[u]包含所有与节点u之间有边相连的节点v。 如果G是一个有向图则对于边uv而言节点 v 将出现在链表 Adj [ u ]里所有邻接链表的长度之和等于 E如果G是一个无向图对于边节点将出现在链表 Adj [ u ] 里节点 u 将出现在链表 Adj [ v ]里所有邻接链表的长度之和为 2*E。 对一个有向图通过vector建图 建图过程 用结构体 node 存储两个数据终点编号边权值建立 node 型的 vector 动态数组。建图也只需要将 结构体 直接插入 vector动态数组 末端即可。 typedef struct Node{int v; //终点编号int w; //起点到终点的边权
}Node;
vectorNode map[201]; //用 vector 建立不是严格意义上的链表
void get_map(int m)
{for(int i1;im;i){int u,v,w;scanf(%d%d%d,u,v,w);Node tmp;tmp.vv;tmp.ww;map[u].push_back(tmp); //将 终点节点v 和 边权w 加入 节点u 的链表末尾tmp.vu;tmp.ww; //如果为无向图反向边map[v].push_back(tmp); // 将 将终点节点u 和边权w 加入 节点v 的链表末尾}
} 邻接链表表示法的储存空间均为 OVE vector 数组建图的应用使用 最小生成树prim算法完整代码
#includestdio.h
#includeiostream
#includevector
#includequeue
#includestring.h
#includestdlib.h
using namespace std;
struct node{int w;int v;friend bool operator(node x,node y){ return x.wy.w;} // 优先队列比较 按照w从小到大排
};
priority_queuenodeq; // 建立数据类型为node结构体的优先队列
int n,m,dis[1001],vis[1001];
vectornodemap[1001]; // 以node结构体的 vector数组
int sum0;
void prim(int s)
{memset(dis,0x3f,sizeof(dis)); // 初始化 memset(vis,0,sizeof(vis));dis[s]0;q.push((node){0,s});while(!q.empty()){int uq.top().v;q.pop();if(vis[u]) continue;vis[u]1;sumdis[u];for(int i0;imap[u].size();i) // vector建图的使用 {int vmap[u][i].v;int wmap[u][i].w;if(dis[v]w){dis[v]w;q.push((node){w,v});}}}
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int u,v,w;scanf(%d%d%d,u,v,w);node tmp; // vector 建图 tmp.vv;tmp.ww;map[u].push_back(tmp);tmp.vu; map[v].push_back(tmp); // 反向边 }prim(1);for(int i1;in;i) {if(!vis[i]) {printf(orz);return 0;}}printf(%d,sum);return 0; }
三、链式前向星 链式前向星所用结构体和相关变量建图函数
struct node{int to,next,w;
}edge[2001];
int head[1001];
int cnt0;
void addedge(int u,int v,int w)
{edge[cnt].tov;edge[cnt].nexthead[u];edge[cnt].ww;head[u]cnt;
} 初始化函数
//初始化函数
void init()
{memset(head,-1,sizeof(head)); //将head数组的值全置为-1.cnt0;//初始化边的编号
}
对于一个有向图用链式前向星建图 关于结构体中 next 数组含义 某一条边的起点连接的上一个编号比它小的边。由于初始化当某条边的next值为 -1 时此条边为最后一条边。 运用链式前向星遍历图的过程 首先根据节点 u 找到以 u 为起始点的边的编号然后根据 next 找到下一条以 u 为起始点的边的编号以此类推。 以链式前向星的方法建图的最小生成树prim算法 主要代码
void addedge(int u,int v,int w)
{edge[cnt].vv;edge[cnt].nexthead[u];edge[cnt].ww;head[u]cnt;
}
void prim(int s)
{memset(dis,0x3f,sizeof(dis)); // 初始化 memset(vis,0,sizeof(vis));dis[s]0;q.push((node1){0,s});while(!q.empty()){int uq.top().v;q.pop();if(vis[u]) continue;vis[u]1;sumdis[u];for(int ihead[u];i!-1;iedge[i].next){int vedge[i].v;int wedge[i].w;if(dis[v]w){dis[v]w;q.push((node1){w,v});}}}
}
四、三种方法的优缺点比较: 1.邻接矩阵 邻接矩阵通过一个二维数组直接表示两点之间的权值但是由于二维数组容易出现空间空间的浪费并且数据量大时会出现爆栈。 2. 邻接链表vector 通过STL步骤简单vector采用可变数组的方式动态变化时会耗费额外时间复制数组。 3.链式前向星 操作简单但不容易理解。
