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;
}