邻接矩阵法的实现 const int MAX VerteX NUM= 20 //图的类型:有向图、有向网、无向图、无向网 typedef enum (DG, DN, UDG, UDN Graphkind; typedef struct t VertexType表示顶点的类型,例如char、int VertexType vexs [MAX VERTEX NUM]; Arc Type表示边和权值的类型 //若为无权图,可取bOL型 若为网,可取nt型、 fLoat型 ArcType arcs[MAX VERTEX NUM][MAX VERTEX NUM]; int vexnum, arcum; Graphkind kind; 3 MGraph; 2021/2/11 数据结构及其算法第7章图
•邻接矩阵法的实现 2021/2/11 数据结构及其算法 第7章 图 17 const int MAX_VERTEX_NUM = 20; // 图的类型：有向图、有向网、无向图、无向网 typedef enum {DG, DN, UDG, UDN} GraphKind; typedef struct { // VertexType表示顶点的类型，例如char、int…… VertexType vexs[MAX_VERTEX_NUM]; // ArcType表示边和权值的类型 // 若为无权图，可取bool型 // 若为网，可取int型、float型…… ArcType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum, arcnum; GraphKind kind; } MGraph;
·算法7.1使用邻接矩阵构造无向网 void CreateUDN(MGraph &G)t G.kind=UDN;//UDN表示无向网 cin >>G. vexnum >>Garcum; int i,j,k 「:22本址….i;/读入点数据 int LocateVex (MGraph G, VertexType v)i for (int i=0; i<G. vexnum; ++1) NITY=INT MAX if (G. vexs[i]== v) return i return -1: i=LocateVex(G, vi); j=LocateVex(G, vi); G.acs[[j=Gacs[j[i]=W;无向网的物接矩阵是对称的 2021/2/11 数据结构及其算法第7章图 18
•算法7.1 使用邻接矩阵构造无向网 2021/2/11 数据结构及其算法 第7章 图 18 void CreateUDN(MGraph &G) { G.kind = UDN; // UDN表示无向网 cin >> G.vexnum >> G.arcnum; int i,j,k; for (i=0; i<G.vexnum; ++i) cin >> G.vexs[i]; // 读入顶点数据 for (i=0; i<G.vexnum; ++i) for (j=0; j<G.vexnum; ++j) G.arcs[i][j] = INFINITY; // 例如，INFINITY=INT_MAX for (k=0; k<G.arcnum; ++k) { VertexType vi, vj; WeightType w; cin >> vi >> vj >> w; i = LocateVex(G, vi); j = LocateVex(G, vj); G.arcs[i][j] = G.arcs[j][i] = w; // 无向网的邻接矩阵是对称的 } } 算法7.2 查找顶点 int LocateVex(MGraph G, VertexType v) { for (int i=0; i<G.vexnum; ++i) if (G.vexs[i] == v) return i; return -1; }
邻接表法:对每个顶点建立一个单链表用于存储相 关的边 G k-[2-[1人 1∧ 2|巧 3∧ 3 V 0∧ G2 0 ⑧⑧ 1245 0∧ 2 1∧ 2021/2/11 数据结构及其算法第7章图 19
•邻接表法：对每个顶点建立一个单链表用于存储相 关的边 2021/2/11 数据结构及其算法 第7章 图 19
邻接表( adjacency1ist)法的实现 struct ArcNode t int adivex WeightType weight; ArcNode nextarci }; typedef struct t VertexType data; ArcNode *firstard F VertexNode, AdjList[MAXVERTEX NUM]; ILv2 typedef struct i AdjList vertices; 0|∧ int vexnum arcum Graph ohkind kind; ALGraph j 2021/2/11 数据结构及其算法第7章图 20
•邻接表(adjacency list)法的实现 2021/2/11 数据结构及其算法 第7章 图 20 struct ArcNode { int adjvex; WeightType weight; ArcNode *nextarc; }; typedef struct { VertexType data; ArcNode *firstarc; } VertexNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; GraphKind kind; } ALGraph;
·算法7.6使用邻接表构造无向网 void CreateUDN (ALGraph &G)t G kind udn cin >>G. vexnum >>Garcum; int i,j,k; for (i=0; i<G. vexnum; ++1)t cin >>Gvertices[i].data; G vertices[i]. firstarc =NULL for (k=0; k<G arcum; ++k)i VertexType vi, vi; WeightType W; cn>>V1>>V]>>W; 1= LocateVex(G, v1);j=LocateVex(G. v]); 算法7.7查找顶点 Weight =W; int Locatevex(ALGraph G, VertexType v)t ceshi]. firstarc =p; for (int i=0; i<G. vexnum; ++1) W if (Gvertices[i]. data ==v)return ii ces[i].firstarc pj return -1 2021/2/11 数据结构及其算法第7章图 21
•算法7.6 使用邻接表构造无向网 2021/2/11 数据结构及其算法 第7章 图 21 void CreateUDN(ALGraph &G) { G.kind = UDN; cin >> G.vexnum >> G.arcnum; int i,j,k; for (i=0; i<G.vexnum; ++i) { cin >> G.vertices[i].data; G.vertices[i].firstarc = NULL; } for (k=0; k<G.arcnum; ++k) { VertexType vi, vj; WeightType w; cin >> vi >> vj >> w; i = LocateVex(G, vi); j = LocateVex(G. vj); ArcNode *p = new ArcNode; p->adjvex = j; p->weight = w; p->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p; p = new ArcNode; p->adjvex = i; p->weight = w; p->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p; } } 算法7.7 查找顶点 int LocateVex(ALGraph G, VertexType v) { for (int i=0; i<G.vexnum; ++i) if (G.vertices[i].data == v) return i; return -1; }