数据结构和算法之如何建立图-创新互联
小白BG.1 邻接矩阵表示的图结点的结构
文章题目:数据结构和算法之如何建立图-创新互联
当前URL:http://pwwzsj.com/article/despgp.html
小白BG.2 邻接矩阵表示的图——初始化typedef struct GNode *PtrToGNode;//PtrToGNode是指向GNode的一个指针 struct GNode{ int Nv;//顶点数 int Ne;//边数 WeightType G[MaxVertexNum][MaxVertexNum]; DataType Data[MaxVertexNum];//存顶点的数据 }; typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型。定义为指向节点的指针。因为要用到的时候 一个指针远远比一整个图来的快捷
初始化一个有VertexNum个顶点但没有边的图
兴安网站制作公司哪家好,找创新互联!从网页设计、网站建设、微信开发、APP开发、响应式网站开发等网站项目制作,到程序开发,运营维护。创新互联成立于2013年到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联。小白BG.3 邻接矩阵表示的图——插入边typedef int Vertex;//用顶点下标表示顶点,为整型 MGraph CreateGraph(int VertexNum)//VertexNum这个顶点数真的是整数, { Vertex V , W;//我们在说V跟W的时候不是在说整数,而是顶点 MGraph Graph; Graph = (MGraph)malloc(sizeof(struct GNode)); Graph->Nv = VertexNum; Graph->Ne = 0; //注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) for(V=0;VNv;V++) for((W=0;W Nv;W++)) Graph->G[V][M] = 0;//或者INFINITY,表示这两个顶点之间是没有边的 return Graph }
小白BG.4 邻接矩阵表示的图——建立图 完整的建立一个MGraphtypedef struct ENode *PtrToENode; struct ENode{ Vertex V1,V2;//有向边,V1V2两个顶点一个出发点一个终点 WeightType Weight;//权重,有权图才需要。权重的类型是WeightType }; typedef PtrToENode Edge; void InsertEdge(MGraph Graph,Edge E) { //插入边 ,这是一条边 Graph->G[E->V1][E->V2] = E->Weight; //无向图的话还需要一条边(一共两条), Graph->G[E->V2][E->V1] = E->Weight; }
输入格式
Nv Ne
V1 V2 Weight
......
简易建法MGraph BuildGraph() { MGraph Graph; scanf("%d",&Nv); Graph = CreateGraph(Nv); //读入边数 scanf("%d",&(Graph->Ne)); if(Graph ->Ne = 0){//有边就还需要经过这里,没有边直接结束 E = (Edge)malloc(sizeof(struct ENode));//临时存一下边 for(i = 0; i< Graph->Ne; i++){ scanf("%d %d %d",&E->V1,&E->V2,&E->Weight); InsertEdge(Graph,E); } } //如果顶点有数据的话,读入数据 for(V=0;VNv;V++) scanf("%c",&(Graph->Data[V])); return Graph; }
int G[MAXN][MAXN],Nv,Ne;//声明为全局变量 void BuildGraph() { int i,j,v1,v2,w; scanf("%d",&Nv); //CreateGraph for(i=0;i小白BG.5 邻接表表示的图结点的结构
邻接表:G[N]为指针数组,对应矩阵每一行一个链表,只存非0元素
小白BG.6 邻接表表示的图——建立图typedef struct GNode *PtrToGNode; struct GNode { int Nv;//顶点数 int Ne;//边数 AdjList G;//邻接表 }; typedef PtrToGNode LGraph; //以邻接表方式存储的图类型 //AdjList是自己定义的 typedef struct Vnode{ PtrToAdjVNode FirstEdge; DataType Data;//存顶点的数据 }AdjList[MaxVertexNum];//AdjList是邻接表类型 typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV;//邻接点下标,定义为整型 WeightType Weight;//边权重 PtrToAdjVNode Next; };
初始化一个有VertexNum个顶点但没有边的图
typedef int Vertex;//用顶点下标表示顶点,为整型 LGraph CreateGraph(int VertexNum) { Vertex V,W; LGraph Graph; Graph = (LGraph)malloc(sizeof(struct GNode)); Graph->Nv = VertexNum; Graph->Ne = 0; //没有边的意思是每个顶点跟着的那个链表都是空的 //注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) for(V=0;VNv;V++) Graph->G[V].FirstEdge = NULL; return Graph; }
void InsertEdge(LGraph Graph,Edge E) { PtrToAdjVNode NewNode; //-------------------插入边------------------------------ //为V2建立新的邻接点 NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode)); NewNode->AdjV = E->V2; NewNode->Weight = E->Weight //将V2插入到V1的表头 NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; //-------------------若是无向图,还需插入边 ------------------ //为V1建立新的邻接点 NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode)); NewNode->AdjV = E->V1; NewNode->Weight = E->Weight //将V2插入到V1的表头 NewNode->Next = Graph->G[E->V2].FirstEdge; Graph->G[E->V2].FirstEdge = NewNode; }
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章题目:数据结构和算法之如何建立图-创新互联
当前URL:http://pwwzsj.com/article/despgp.html