图1

2024-07-09 04:46| 来源: 网络整理| 查看: 265

零、说明本文中，V代表Vertex，即顶点，E代表Edge，即边。什么Vnum，Enum，firstE都按照这个来理解。原理我是按《大话数据结构》来的，我也解释不好这个原理，就不献丑了存储方式还远不止这些，有个好像叫前向星，我现在还不会（流下了菜鸡的眼泪）本文有很多地方不严谨，后续待修改一、邻接矩阵数据类型 typedef struct { char Vertex[MAXSIZE]; int Edge[MAXSIZE][MAXSIZE]; int Vnum,Enum; }MGraph;//叫MGraph是因为矩阵（Matrix）

包含顶点表和矩阵两个部分，矩阵的每一个元素都代表某点（行）到某点（列）是否有边存在 2. 初始化

void CreateMGraph(MGraph *M) { int i,j,start,end; for(i=0;iVnum>>M->Enum; coutM->Vertex[i]; } coutstart; cin>>end; cin>>M->Edge[start][end]; M->Edge[end][start]=M->Edge[start][end]; //这一行 } }

说明几点：计数从零开始，所以就比如0号点到3号点有边用在无向图中，如果想用在有向图，上面示意的那一行删掉即可

二、邻接表

0.起因：邻接矩阵直观是直观，但是空间浪费挺多的，联想到前面用链式结构节省空间，用链式结构存储图彳亍不彳亍？彳亍！

数据类型（List）分三层：首先定义边节点，然后定义图中的节点，节点中有指向一个边的指针（所以不是第一个定义它），最后定义整个图，就是点的数组 typedef struct LEnode { int Vdata;//连接的点序号 int weight;//该边权值 struct LEnode *next;//同节点的下一条边 }LEnode; typedef struct LVnode { int data; LEnode *firstE; }LVnode,lGraph[MAXSIZE]; typedef struct { int Vnum,Enum; lGraph G; }LGraph; 初始化很容易理解，就是新建一个边，输入，按头插法连接到点上 void CreateLGraph(LGraph *L) { int i,start,end,weight; LEnode *e; coutL->Vnum>>L->Enum; coutL->G[i].data; L->G[i].firstE=NULL; } coutstart>>end>>weight; e=new LEnode; e->Vdata=end; e->weight=weight; e->next=L->G[start].firstE; L->G[start].firstE=e; e=new LEnode; e->Vdata=start; e->weight=weight; e->next=L->G[end].firstE; L->G[end].firstE=e; } } 三、十字链表（邻接多重表）

A.有向的称为十字链表

数据类型（Cross） typedef struct CEnode1 { int weight; int tailV,headV; struct CEnode1 *headnext,*tailnext;//分别指向弧头、弧尾相同的下一条边 }CEnode1; typedef struct CVnode1 { int data; CEnode1 *firstIn,*firstOut; //第一条入/出这个点的边（按输入顺序，所以没有严格正确的先后之分， //只是代表性地用一下'第一条'这个词罢了） }CVnode1,cGraph1[MAXSIZE]; typedef struct { int Vnum,Enum; cGraph1 G; }CGraph1; 初始化 void CreateCGraph1(CGraph1 *C)//有向图 { int i; CEnode1 *e; coutC->Vnum>>C->Enum; coutC->G[i].data; C->G[i].firstIn=NULL; C->G[i].firstOut=NULL; } coute->tailV>>e->headV>>e->weight; e->tailnext=C->G[e->tailV].firstOut; C->G[e->tailV].firstOut=e; e->headnext=C->G[e->headV].firstIn; C->G[e->headV].firstIn=e; } }

B. 无向的称为邻接多重表

数据类型说实话，无向的数据类型和有向的挺像，不过简洁了许多 typedef struct CEnode2 { int weight; int Vi,Vj;//这条边两端的顶点 struct CEnode2 *Vinext,*Vjnext;//Vi,Vj连接的下一条边 }CEnode2; typedef struct CVnode2 { int data; CEnode2 *firstE; }CVnode2,cGraph2[MAXSIZE]; typedef struct { int Vnum,Enum; cGraph2 G; }CGraph2; 初始化 void CreateCGraph2(CGraph2 *C)//无向图 { int i; CEnode2 *e; coutC->Vnum>>C->Enum; coutC->G[i].data; C->G[i].firstE=NULL; } coute->Vi>>e->Vj>>e->weight; e->Vinext=C->G[e->Vi].firstE; C->G[e->Vi].firstE=e; e->Vjnext=C->G[e->Vj].firstE; C->G[e->Vj].firstE=e; } } 四、边集数组大概类似邻接矩阵的三元组存储法？（矩阵还没写。。。）数据类型 typedef struct { int Vnum,Enum; int V[MAXSIZE]; int E[MAXSIZE][3]; }EGraph; 初始化没什么好说的 void CreateEGraph(EGraph *E) { int i; coutE->Vnum>>E->Enum; coutE->V[i]; } coutE->E[i][0]>>E->E[i][1]>>E->E[i][2]; } }

【本文地址】

图1

图1

今日新闻

推荐新闻