物流网站建设方案范文,17zwd一起做网店,有没有免费的推广网站,正规的电商平台有哪些图的存储#xff1a;
1.邻接矩阵#xff1a; 我们用map[i][j]表示i---j的边权
2.用vector数组#xff08;在搜索专题的游戏一题中应用过#xff09;
3.用邻接表#xff1a;
下面是用链表实现的基本功能的代码#xff1a;
#includebits/stdc.h
using nam…图的存储
1.邻接矩阵 我们用map[i][j]表示i---j的边权
2.用vector数组在搜索专题的游戏一题中应用过
3.用邻接表
下面是用链表实现的基本功能的代码
#includebits/stdc.h
using namespace std;
struct node{int dian,zhi;struct node* next;
};
void insert(int x,int y,int z){node *pnew node;p-diany;p-zhiz;p-nexthead[x];head[x]p;
}
4.用伪邻接表链式前向星注意第一个next-1开始直接memset head-1即可)
对于1330,-1表示1的点指向3边权为30,下一条边.
我们把这个存在edge[1]里并令head[1]1;
(3,6,10-1),我们存在edge[2]里并令head[3]2;
(1,2,10head[1])我们存在edge【3】里并让head[1]3;
下面是实现的代码
#includebits/stdc.h
using namespace std;
struct node{int dian,zhi;int next;
};
void insert(int x,int y,int z){edge[m].diany;edge[m].zhiz;edge[m].nexthead[x];head[x]m;
}
欧拉图前提是联通
如果图的一个路径包括每个边恰好一次则为欧拉路径。
欧拉路径回路欧拉回路。
具有欧拉回路的图为欧拉图具有欧拉路径但无欧拉回路的图为半欧拉图
那么如何判断是否为欧拉图呢
对于无向图等价于该图所有顶点的度数为偶数一进一出联通。
对于有向图等价于该图所有顶点的入度出度联通。
拓扑排序
即按照一定的规则安排活动的先后次序可能有多解。
现在给一张图a--》b表示要完成b必须先完成a那我们如何排序呢
1.先找没有前驱的点作为开始。
2.把它连着的边给删除产生更多没有前驱的点作为下一步入度-1。
3.删不动则无法完成。
具体实现中我们不能总是去跑入度为0的点。
于是我们用一个队列。在删后发现入度为0的点就放入队列中即可。
下面是实现的代码
#includebits/stdc.h
using namespace std;
int n,m,cnt;
struct node{int dian;int next;
}edge[1000000];
int head[1010],inc[1010];
queueint q;
void insert(int x,int y){edge[cnt].diany;edge[cnt].nexthead[x];head[x]cnt;
}
void tuopu(){for(int i1;in;i){if(inc[i]0) q.push(i);}int tot0;while(!q.empty()){int xq.front();q.pop();coutxendl;tot;for(int ihead[x];i!-1;iedge[i].next){inc[edge[i].dian]--;if(inc[edge[i].dian]0){q.push(edge[i].dian);}}}if(tot!n) cout-1;
}
int main(){cinnm;memset(head,-1,sizeof(head));for(int i1;im;i){int x,y;cinxy;insert(x,y);inc[y];}tuopu();
}
拓扑排序的应用
1.判断一个有向图是否有环无环的图所有点都可以拓扑排序。
2.AOE网 对于第一个我们只用在拓扑排序上维护时间的max即可。
对于第二个我们可以计算一下每一个活动的最早开始时间与最晚开始时间因此我们相当于求最早开始时间等于最晚开始时间的点。
那么我们如何求最晚开始时间呢
我们只要从结尾反方向跑一回即可。
下面是AC代码
#includebits/stdc.h
using namespace std;
int n,m,cnt;
struct node{int dian;int next;int zhi;
}edge[1000000];
int head[1010],inc[1010],shijian[1010];
queueint q;
void insert(int x,int y,int z){edge[cnt].diany;edge[cnt].nexthead[x];edge[cnt].zhiz;head[x]cnt;
}
void tuopu(){for(int i1;in;i){if(inc[i]0){q.push(i);shijian[i]0;}}while(!q.empty()){int xq.front();q.pop();for(int ihead[x];i!-1;iedge[i].next){inc[edge[i].dian]--;shijian[edge[i].dian]max(shijian[edge[i].dian],shijian[x]edge[i].zhi);if(inc[edge[i].dian]0){q.push(edge[i].dian);}}}
}
int main(){cinnm;memset(head,-1,sizeof(head));for(int i1;im;i){int x,y,z;cinxyz;insert(x,y,z);inc[y];}tuopu();coutshijian[n];
}
