8. 数据结构——邻接表、邻接矩阵的基本操作
一、邻接表
1. 内容
2. 实现代码(直接可以复制使用)
//邻接表的相关操作
#include<bits/stdc++.h>
#define MVnum 100
#define OK 1
#define ERROR -1
using namespace std;typedef int Status;
typedef char VerTexType; //假设顶点的数据类型为char
typedef int ArcType; //假设边的权值类型为int
bool visit1[MVnum]; //dfs的时候状态数组
bool visit2[MVnum]; //bfs的时候状态数组 //定义结构体(边结点+头节点数组+相关信息)
//1.边结点
typedef struct ArcNode{int adjvex; struct ArcNode *nextarc;
}ArcNode;//2.头结点数组
typedef struct VNode{VerTexType data;ArcNode *firstarc;
}VNode,AdList[MVnum]; typedef struct{AdList vertices;int vexnum,arcnum; //图当前的顶点数、边数
}ALGraph; //查找顶点值在图中存储的位置
Status LocateVex(ALGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(G.vertices[i].data==v)return i;}return -1; //表示未找到
}//1.创建有向图
Status CreateDG(ALGraph &G){VerTexType v1,v2; //临时值 cout<<"输入总顶点、总边数："<<endl;cin>>G.vexnum>>G.arcnum;cout<<"输入每个顶点的值"<<endl; for(int i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL; //头结点指向为空 }for(int i=0;i<G.arcnum;i++){cout<<"请输入两个邻接的点："<<endl; cin>>v1>>v2;int t1=LocateVex(G,v1); int t2=LocateVex(G,v2);//建立从t1->t2的边 ArcNode *p1=new ArcNode; //建立一个新边结点p1->adjvex=t2;p1->nextarc=G.vertices[t1].firstarc;G.vertices[t1].firstarc=p1;
// //建立从t2->t1的边
// ArcNode *p2=new ArcNode; //建立一个新边结点
// p2->adjvex=t1;
// p2->nextarc=G.vertices[t2].firstarc;
// G.vertices[t2].firstarc=p2; }return OK;
}//计算有向图的出度
Status CalculateDGO(ALGraph G,VerTexType v){int x=0;int i=LocateVex(G,v); //得到该顶点的位置if(i==-1) return ERROR;ArcNode *p=G.vertices[i].firstarc;while(p){x++;p=p->nextarc;} return x;
}
//有向图的入度
//需要把每个顶点遍历一次，找到到点i的情况，增加1
Status CalculateDGI(ALGraph G,VerTexType v){int x=0;int i=LocateVex(G,v); //得到该顶点的位置if(i==-1) return ERROR;for(int k=0;k<G.vexnum;k++){ArcNode *p=G.vertices[k].firstarc;while(p){if(p->adjvex==i)x++;p=p->nextarc;}}return x;
}
//有向图的总度
Status CalculateSum(ALGraph G,VerTexType v){if(LocateVex(G,v)==-1) return ERROR;return CalculateDGO(G,v)+CalculateDGI(G,v);
}//深度优先遍历
void dfs(ALGraph G,int v){cout<<G.vertices[v].data;visit1[v]=true; //表明已经遍历过ArcNode *p=G.vertices[v].firstarc;while(p){if(!visit1[p->adjvex])dfs(G,p->adjvex);p=p->nextarc; }
} //广度优先遍历
void bfs(ALGraph G,VerTexType v){int x=LocateVex(G,v);queue<int> q; //队列q.push(x);visit2[x]=true; //表示已经遍历过while(!q.empty()){int t=q.front();q.pop();cout<<G.vertices[t].data;//找t位置结点相邻的未被访问的点ArcNode *p=G.vertices[t].firstarc;while(p){if(!visit2[p->adjvex]){q.push(p->adjvex);visit2[p->adjvex]=true;}p=p->nextarc;} }
} //输出在数据库中本身存储形式
void Reverse(ALGraph G){for(int i=0;i<G.vexnum;i++){if(i!=0) cout<<endl;cout<<G.vertices[i].data;ArcNode *p=G.vertices[i].firstarc;while(p){cout<<"->"<<G.vertices[p->adjvex].data;p=p->nextarc;}}
} void menu(){cout<<"==========================="<<endl;cout<<" 菜单 "<<endl; cout<<"==========================="<<endl;cout<<" 1.图的建立 "<<endl;cout<<" 2.求顶点的度 "<<endl;cout<<" 3.深度优先遍历 "<<endl;cout<<" 4.广度优先遍历 "<<endl; cout<<" 5.输出存储结构 "<<endl; cout<<" 0.退出程序 "<<endl; cout<<"==========================="<<endl;
} int main(void) {VerTexType v;ALGraph G;char order;int t;menu();cout<<"请输入你的选择：";cin>>order;while(order!='0'){switch(order){case '1':CreateDG(G);cout<<"此有向图的邻接表建立成功！！！"<<endl;cout<<"此有向图在邻接表中存储结构为："<<endl; Reverse(G);cout<<endl;break;case '2':cout<<"请输入需要查找度数的顶点：";cin>>v;if(LocateVex(G,v)==-1)cout<<v<<"不存在于此图中"<<endl;else {cout<<"顶点"<<v<<"的出度为："<<CalculateDGO(G,v)<<endl;cout<<"顶点"<<v<<"的入度为："<<CalculateDGI(G,v)<<endl;cout<<"顶点"<<v<<"的总度为："<<CalculateSum(G,v)<<endl; } break;case '3':cout<<"请输出深度优先遍历的起点：";cin>>v; memset(visit1,false,sizeof(visit1));t=LocateVex(G,v);cout<<"深度优先遍历结果为：";dfs(G,t);cout<<""<<endl; //实现换行 break;case '4':cout<<"请输出广度优先遍历的起点：";cin>>v; memset(visit2,false,sizeof(visit2));cout<<"广度优先遍历结果为：";bfs(G,v);cout<<""<<endl; //实现换行 break; case '5':cout<<"此有向图在邻接表中存储结构为："<<endl; Reverse(G);cout<<endl;break; case '0':cout<<"程序终止";break;default:cout<<"输入不合法，重新输入"<<endl; }if(order!='0'){menu();cout<<"请输入你的选择：";cin>>order;}}return 0;
}二、邻接矩阵
因为邻接矩阵大部分实现代码和邻接表一致，故这里就只写了邻接矩阵的创建。
#include<bits/stdc++.h>
#define MVnum 100
using namespace std;typedef int Status;
typedef char VerTexType; //假设每个顶点的数据类型是char
typedef int ArcType; //假设每条边权值的数据类型是inttypedef struct{VerTexType vexs[MVnum]; //顶点表 int vexnum,arcnum; //图当前的顶点数和边数ArcType arcs[MVnum][MVnum]; //邻接矩阵存储权值
}AMGraph; //给定顶点值，找到其位置
Status LocateVex(AMGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(G.vexs[i]==v)return i;}return -1;
}//1.建立有向图
Status CreateDG(AMGraph &G){VerTexType v1,v2; cout<<"输入总顶点、总边数："<<endl;cin>>G.vexnum>>G.arcnum;cout<<"输入每个顶点的值"<<endl; for(int i=0;i<G.vexnum;i++){cin>>G.vexs[i];}for(int i=0;i<G.arcnum;i++){cout<<"请输入两个邻接的点："<<endl; cin>>v1>>v2; int t1=LocateVex(G,v1); int t2=LocateVex(G,v2);G.arcs[t1][t2]=1;}
}//2.输出
void Reverse(AMGraph G){for(int i=0;i<G.vexnum;i++){if(i!=0) cout<<endl;for(int j=0;j<G.vexnum;j++){cout<<G.arcs[i][j]<<" ";}}
}int main(void){AMGraph G;CreateDG(G);Reverse(G);return 0;
}