数据结构图的建立和遍历（邻接表、邻接矩阵）

您所在的位置：网站首页 › 采用邻接矩阵表示法创建无向网 › 数据结构图的建立和遍历（邻接表、邻接矩阵）

数据结构图的建立和遍历（邻接表、邻接矩阵）

2024-07-11 14:13| 来源: 网络整理| 查看: 265

以本代码为基础增加了对图的最短路径计算,路径记录,交互界面等功能,增加代码请看数据结构课程设计——图的建立和遍历(邻接矩阵+邻接表)和最短路径dijkstra路径记录

首先是图的存储结构：

一、邻接矩阵存储方式实现

邻接矩阵存储的结构体中，包括一个存储边的结构体，存储每条边的信息(权值) 将这个边的结构体的二维数组作为图的基本存储结构，放到单个图的结构体中每个图又包含总节点数、总边数、图的类型等信息最下方定义一个遍历操作图的函数

#include #include #include #include #include #define INFINITY 0X7fffffff #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 using namespace std; #define MAX_VERTEX_NUM 30 typedef char InfoType; typedef int Status; typedef int Boolean; typedef string VertexType; typedef enum {DG,DN,UDG,UDN} GraphKind; Boolean visited[MAX_VERTEX_NUM]; typedef struct ArcCell///弧(邻接矩阵) { int adj; InfoType *info; } ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct///图(邻接矩阵) { string vexs[MAX_VERTEX_NUM];///结点名 AdjMatrix arcs; ///邻接矩阵 int vexnum,arcnum; ///结点数，弧数 GraphKind kind; } MGraph; Status (*VisitFunc)(MGraph G,int v);

建图，以建立无向无权图为例：首先输入该图的总结点数、总边数、是否包含信息然后对于每个标号输入该标号(结点)的命名

Status CreateUDG(MGraph &G)///邻接矩阵(建立无权无向图) { int IncInfo; printf("建立无权无向图，请依次输入总结点数、总边数、是否包含信息:\n"); scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo); printf("请为从1至n个结点命名:\n"); for(int i=0; i>G.vexs[i]; for(int i=0; i>v2; int i=LocateVex(G,v1); int j=LocateVex(G,v2); G.arcs[i][j].adj=TRUE;///无权 if(IncInfo)scanf("%s",G.arcs[i][j].info); G.arcs[j][i]=G.arcs[i][j];///无向图,结构体赋值 } return OK; }

对图的基本操作：根据结点名获取结点的存储位置(邻接矩阵中的标号)

Status LocateVex(MGraph G,string name)///获取结点标号 { for(int i=0; ist; int tmp=LocateVex(G,st); printf("深度优先搜索遍历序列:\n"); DFS(G,tmp); for(int v=0; vG.vexs[i]; for(int i=0; i>v2>>w; int i=LocateVex(G,v1); int j=LocateVex(G,v2); G.arcs[i][j].adj=w;///带权 if(IncInfo)scanf("%s",G.arcs[i][j].info); G.arcs[j][i]=G.arcs[i][j];///无向图,结构体赋值 } return OK; } void DFS(MGraph G,int v)///邻接矩阵DFS { visited[v]=TRUE; VisitFunc(G,v); for(int w=0; wst; int tmp=LocateVex(G,st); printf("深度优先搜索遍历序列:\n"); DFS(G,tmp); for(int v=0; vst; printf("广度优先搜索遍历序列:\n"); int temp=LocateVex(G,st); Visit(G,temp); Q.push(temp); visited[temp]=TRUE; while(!Q.empty()) { int tmp=Q.front(); Q.pop(); for(int w=0; wnextarc=q; G.vertices[v2].firstarc=p; } else { while(G.vertices[v2].firstarc!=NULL&&q->nextarc!=NULL&&p->adjvex adjvex) { h=q; q=q->nextarc; } if(q->nextarc==NULL&&p->adjvex adjvex) q->nextarc=p; else { p->nextarc=q; h->nextarc=p; } } } }

方式②：按一般随机输入方式建图，不存在规律，根据输入顺序的不同，存储的顺序也不同，遍历的顺序也随之改变，但都一定正确，只是多种遍历顺序中的其中一种序列。无优先级。

void ArcAdd(ALGraph &G,int v1,int v2,int w)///加边 { ArcNode *p,*q; p=new ArcNode; p->adjvex=v2; p->info=w; p->nextarc=NULL; q=G.vertices[v1].firstarc; if(q==NULL) G.vertices[v1].firstarc=p;///若第一条依附v2顶点的弧还未存在，新加入的边作为第一条依附弧 else///否则顺着链表向后查找 { while(q->nextarc!=NULL) q=q->nextarc; q->nextarc=p; } }

对图的基本操作，获取每个结点对应的存储位置标号

int LocateVex_2(ALGraph G,string name)///获取结点标号 { for(int i=0; iG.vertices[i].data,G.vertices[i].firstarc=NULL; string v1,v2; printf("请输入%d组相互依附的两结点:\n",G.arcnum); for(int k=0; k>v1>>v2; int i=LocateVex_2(G,v1);///获取标号 int j=LocateVex_2(G,v2); ArcAdd(G,i,j,1);///无向边 ArcAdd(G,j,i,1); } return OK; }

遍历每个节点的邻接表的基础操作：因为利用邻接表存储结点间的关系，那么就不能像邻接矩阵一样用for循环遍历二维数组而是用指针传递的方式遍历每一条边和结点，这里有两个函数，一个是获取某结点的头指针。一个是获取某结点的下一条(next)边信息

int FirstAdjVex(ALGraph G,int v) { if(G.vertices[v].firstarc) return G.vertices[v].firstarc->adjvex; return -1; } int NextAdjVex(ALGraph G,int v,int w) { ArcNode *p=G.vertices[v].firstarc; while(p->adjvex!=w&&p->nextarc!=NULL)p=p->nextarc; if(p->nextarc==NULL)return -1; return p->nextarc->adjvex; }

有了以上基础操作，可以利用这些操作实现DFS(深度优先搜索)遍历和BFS(广度优先搜索)遍历的操作

深度优先遍历：

void DFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v)) { VisitFunc_2=Visit; printf("请输入深度优先搜索起始结点:\n"); for(int v=0; v>st; int tmp=LocateVex_2(G,st); printf("深度优先搜索遍历序列:\n"); DFS_2(G,tmp); for(int v=0; v=0; w=NextAdjVex(G,v,w)) if(!visited[w])DFS_2(G,w); }

广度优先遍历：

void BFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v))///邻接表BFS { for(int v=0; v>st; printf("广度优先搜索遍历序列:\n"); int temp=LocateVex_2(G,st); Visit(G,temp); Q.push(temp); visited[temp]=TRUE; while(!Q.empty()) { int tmp=Q.front(); Q.pop(); for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w)) { if(!visited[w]) { visited[w]=TRUE; Visit(G,w); Q.push(w); } } } for(int v=0; v=0; w=NextAdjVex(G,tmp,w)) { if(!visited[w]) { visited[w]=TRUE; Visit(G,w); Q.push(w); } } } } } printf("\n"); }

为了更清楚的看到邻接表的存储结构，可以输出邻接表以理解该表的存储方式

void PrintGraph(ALGraph G)///输出邻接表 { cout>w; int i=LocateVex_2(G,v1);///获取标号 int j=LocateVex_2(G,v2); ArcAdd(G,i,j,w); } return OK; } Status CreateUDG_2(ALGraph &G)///邻接表(建立无权无向图) { printf("建立无权无向图，请依次输入总结点数、总边数:\n"); scanf("%d%d",&G.vexnum,&G.arcnum); printf("请为从1至n个结点命名:\n"); for(int i=0; i>G.vertices[i].data,G.vertices[i].firstarc=NULL; string v1,v2; printf("请输入%d组相互依附的两结点:\n",G.arcnum); for(int k=0; k>v1>>v2; int i=LocateVex_2(G,v1);///获取标号 int j=LocateVex_2(G,v2); ArcAdd(G,i,j,1);///无向边 ArcAdd(G,j,i,1); } return OK; } Status CreateUDN_2(ALGraph &G)///邻接表(建立带权无向网) { printf("建立带权无向网，请依次输入总结点数、总边数:\n"); scanf("%d%d",&G.vexnum,&G.arcnum); printf("请为从1至n个结点命名:\n"); for(int i=0; i>G.vertices[i].data,G.vertices[i].firstarc=NULL; string v1,v2; int w; printf("请输入%d组相互依附的两结点与边权:\n",G.arcnum); for(int k=0; k>v1>>v2>>w; int i=LocateVex_2(G,v1);///获取标号 int j=LocateVex_2(G,v2); ArcAdd(G,i,j,w);///无向边 ArcAdd(G,j,i,w); } return OK; } int FirstAdjVex(ALGraph G,int v) { if(G.vertices[v].firstarc) return G.vertices[v].firstarc->adjvex; return -1; } int NextAdjVex(ALGraph G,int v,int w) { ArcNode *p=G.vertices[v].firstarc; while(p->adjvex!=w&&p->nextarc!=NULL)p=p->nextarc; if(p->nextarc==NULL)return -1; return p->nextarc->adjvex; } void DFS_2(ALGraph G,int v)///邻接表DFS { visited[v]=TRUE; VisitFunc_2(G,v); for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)) if(!visited[w])DFS_2(G,w); } void DFSTraverse_2(ALGraph G,Status (*Visit)(ALGraph G,int v)) { VisitFunc_2=Visit; printf("请输入深度优先搜索起始结点:\n"); for(int v=0; v>st; int tmp=LocateVex_2(G,st); printf("深度优先搜索遍历序列:\n"); DFS_2(G,tmp); for(int v=0; vst; printf("广度优先搜索遍历序列:\n"); int temp=LocateVex_2(G,st); Visit(G,temp); Q.push(temp); visited[temp]=TRUE; while(!Q.empty()) { int tmp=Q.front(); Q.pop(); for(int w=FirstAdjVex(G,tmp); w>=0; w=NextAdjVex(G,tmp,w)) { if(!visited[w]) { visited[w]=TRUE; Visit(G,w); Q.push(w); } } } for(int v=0; v=0; w=NextAdjVex(G,tmp,w)) { if(!visited[w]) { visited[w]=TRUE; Visit(G,w); Q.push(w); } } } } } printf("\n"); } void PrintGraph(ALGraph G)///输出邻接表 { cout

【本文地址】

数据结构图的建立和遍历（邻接表、邻接矩阵）

数据结构图的建立和遍历（邻接表、邻接矩阵）

今日新闻

推荐新闻