一、邻接表
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; //假设每条边权值的数据类型是int
typedef 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;
}