C++邻接矩阵建图与遍历图

#include<iostream>
#include <cstdlib>
using namespace std;
#define MAX_VERTEX_NUM 100
#define MAX 100
typedef struct ArcCell{
	int adj;
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
	char vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum,arcnum;
}MGraph;

typedef struct{
	char visited[MAX];
}Recording;

int judge(MGraph G,char V){
	int count = 0;
	for(int i=0;i<G.vexnum;++i){
		if(V == G.vexs[i]){
			++count;
		}
	}
	if(count == 0){
		cout<<"错误！不是顶点元素！请重新输入!"<<endl;
		exit(0);
		}
}

int LocateVex(MGraph G,char V){
	for(int i=0;i<G.vexnum;++i){
		if(G.vexs[i] == V){
			return i;
		}
	}
}

void show(MGraph &G){
	for(int i=0;i<G.vexnum;++i){
		for(int j=0;j<G.vexnum;++j){
			cout<<G.arcs[i][j].adj<<" "; 
			if(j == G.vexnum-1){
				cout<<endl;
			}
		}
	}
}

int CreateDG(MGraph &G){
		cout<<"请输入当前顶点数:"<<endl;
		cin>>G.vexnum; 
		cout<<"弧（边）数范围:0～"<<G.vexnum*(G.vexnum-1)<<endl; 
		cout<<"请输入当前弧(边)数:"<<endl; 
		cin>>G.arcnum;
		if(G.arcnum<0||G.arcnum>G.vexnum*(G.vexnum-1)){
			cout<<"弧(边)数输入有误！"<<endl; 
				return CreateDG(G);
		}
		cout<<"请输入您想用来表示顶点的元素:"<<endl;
		for(int i=0;i<G.vexnum;++i){
			cin>>G.vexs[i];
		}
		for(int i=0;i<G.vexnum;++i){
			for(int j=0;j<G.vexnum;++j){
				G.arcs[i][j]={0};
			}
		}
		for(int k=1;k<G.arcnum+1;k++){
			char V1,V2;
			int i,j;
			cout<<"输入第"<<k<<"边依附的一个顶点:"<<endl;
			cin>>V1;
			judge(G,V1);
			i = LocateVex(G,V1);
			cout<<"输入第"<<k<<"边依附的另一个顶点:"<<endl;
			cin>>V2;
			judge(G,V2);
			j = LocateVex(G,V2);
			if(V1==V2){
				cout<<"不能连接相同点！请重新输入"<<endl;
				k--;
				continue;
			}
			if(G.arcs[i][j].adj == 1){
				cout<<"此弧（边）已经连接，请重新输入"<<endl;
					k--;
					continue; 
			}
			G.arcs[i][j].adj = 1;
	}
	cout<<"此图(有向图)的邻接矩阵为："<<endl;
	show(G);
} 

int CreateDN(MGraph &G){
		cout<<"请输入当前顶点数:"<<endl;
		cin>>G.vexnum; 
		cout<<"弧（边）数范围:0～"<<G.vexnum*(G.vexnum-1)<<endl;
		cout<<"请输入当前弧(边)数:"<<endl; 
		cin>>G.arcnum;
		if(G.arcnum<0||G.arcnum>G.vexnum*(G.vexnum-1)){
			cout<<"弧(边)数输入有误！"<<endl; 
				return CreateDN(G);
		}
		cout<<"请输入您想用来表示顶点的元素:"<<endl;
		for(int i=0;i<G.vexnum;++i){
			cin>>G.vexs[i];
		}
		for(int i=0;i<G.vexnum;++i){
			for(int j=0;j<G.vexnum;++j){
				G.arcs[i][j]={0};
			}
		}
		for(int k=1;k<G.arcnum+1;k++){
			char V1,V2;
			int i,j,W;
			cout<<"输入第"<<k<<"边依附的一个顶点:"<<endl;
			cin>>V1;
			judge(G,V1);
			i = LocateVex(G,V1);
			cout<<"输入第"<<k<<"边依附的另一个顶点:"<<endl;
			cin>>V2;
			judge(G,V2);
			j = LocateVex(G,V2);
			cout<<"输入第"<<k<<"边依附的权值:"<<endl;
			cin>>W;
			if(G.arcs[i][j].adj != 0){
				cout<<"此弧（边）已经连接，请重新输入"<<endl;
					k--;
					continue; 
			}
			if(V1==V2){
				cout<<"不能连接相同点！请重新输入"<<endl;
				k--;
				continue;
			}
			G.arcs[i][j].adj = W;	
	}
	cout<<"此网(有向网)的邻接矩阵为："<<endl;
	show(G);
} 

int CreateUDG(MGraph &G){
		cout<<"请输入当前顶点数:"<<endl;
		cin>>G.vexnum; 
		cout<<"弧（边）数范围:0～"<<0.5*G.vexnum*(G.vexnum-1)<<endl;
		cout<<"请输入当前弧（边）数:"<<endl; 
		cin>>G.arcnum;
		if(G.arcnum<0 || G.arcnum>0.5*G.vexnum*(G.vexnum-1)){
			cout<<"弧(边)数输入有误！"<<endl; 
				return CreateUDG(G);
		}
		cout<<"请输入您想用来表示顶点的元素:"<<endl;
		for(int i=0;i<G.vexnum;++i){
			cin>>G.vexs[i];
		}
		for(int i=0;i<G.vexnum;++i){
			for(int j=0;j<G.vexnum;++j){
				G.arcs[i][j]={0};
			}
		}
		for(int k=1;k<G.arcnum+1;++k){
			char V1,V2;
			int i,j;
			cout<<"输入第"<<k<<"边依附的一个顶点:"<<endl;
			cin>>V1;
			judge(G,V1);
			i=LocateVex(G,V1);
			cout<<"输入第"<<k<<"边依附的另一个顶点:"<<endl;
			cin>>V2;
			judge(G,V2);
			j=LocateVex(G,V2);
			G.arcs[i][j] = G.arcs[j][i];
			if(G.arcs[i][j].adj == 1){
				cout<<"此弧（边）已经连接，请重新输入"<<endl;
					k--;
					continue; 
			}
			if(V1==V2){
				cout<<"不能连接相同点！请重新输入"<<endl;
				k--;
				continue;
			}
			G.arcs[i][j].adj=G.arcs[j][i].adj=1;
		} 
	cout<<"此图(无向图)的邻接矩阵为："<<endl;
	show(G);
}

int CreateUDN(MGraph &G){
		cout<<"请输入当前顶点数:"<<endl;
		cin>>G.vexnum; 
		cout<<"弧（边）数范围:0～"<<0.5*G.vexnum*(G.vexnum-1)<<endl;
		cout<<"请输入当前弧（边）数:"<<endl; 
		cin>>G.arcnum;
		if(G.arcnum<0 || G.arcnum>0.5*G.vexnum*(G.vexnum-1)){
			cout<<"弧(边)数输入有误！"<<endl; 
				return CreateUDN(G);
		}
		cout<<"请输入您想用来表示顶点的元素:"<<endl;
		for(int i=0;i<G.vexnum;++i){
			cin>>G.vexs[i];
		}
		for(int i=0;i<G.vexnum;++i){
			for(int j=0;j<G.vexnum;++j){
				G.arcs[i][j]={0};
			}
		}
		for(int k=1;k<G.arcnum+1;++k){
			char V1,V2;
			int i,j,W;
			cout<<"输入第"<<k<<"边依附的一个顶点:"<<endl;
			cin>>V1;
			judge(G,V1);
			i=LocateVex(G,V1);
			cout<<"输入第"<<k<<"边依附的另一个顶点:"<<endl;
			cin>>V2;
			judge(G,V2);
			j=LocateVex(G,V2);
			cout<<"输入第"<<k<<"边依附的权值:"<<endl;
			cin>>W;
			G.arcs[i][j] = G.arcs[j][i];
			if(G.arcs[i][j].adj != 0){
				cout<<"此弧（边）已经连接，请重新输入"<<endl;
					k--;
					continue; 
		}
			if(V1==V2){
				cout<<"不能连接相同点！请重新输入"<<endl;
				k--;
				continue;
			}
			G.arcs[i][j].adj = G.arcs[j][i].adj =W;
	}
	cout<<"此网(无向网)的邻接矩阵为："<<endl;
	show(G); 
}

int CreateGraph(MGraph &G){
	int i;
	cout<<"1:有向图"<<endl;
	cout<<"2:有向网"<<endl;
	cout<<"3:无向图"<<endl;
	cout<<"4:无向网"<<endl;
	cout<<"请输入您想构建的图:";
	cin>>i;
	switch(i){
		case 1:
			return CreateDG(G);
		case 2:
			return CreateDN(G);
		case 3:
			return CreateUDG(G);
		case 4:
			return CreateUDN(G);
		default:
			cout<<"错误！请重新输入"<<endl;
				return CreateGraph(G);
	} 
}

void DFS(MGraph G,Recording &R,int v){
	R.visited[v] = true;
} 

int DFSTraverse(MGraph G,Recording &R){
	int count = 0;
	for(int i=0;i<G.vexnum;++i){
		if(R.visited[i] == true){
			count++;
		} 
	}
	if(count+1 == G.vexnum){
		cout<<"深度优先搜索成功！"<<endl;
	}
	else{
		for(int v=0;v<G.vexnum;++v){
		if(R.visited[v] == false){
			DFS(G,R,v);
			}
		}
	}
	
}

int keepnode(MGraph G,Recording &R,int keepnum,int nodes){
	int keeplist[keepnum]={0};
	int keepnumkeep =0;
	for(int v=0;v<G.vexnum;++v){
		if(G.arcs[nodes][v].adj!=0&&nodes!=v){
			DFS(G,R,v);
		}
		if(G.arcs[nodes][v].adj==0&&nodes!=v){
			keeplist[v] = v;
			++keepnumkeep;
		}
	}
	if(keepnum!=0){
		return keepnode(G,R,keepnumkeep,keeplist[0]);
	} 
	else{
		return DFSTraverse(G,R);
	}
}

int keep(MGraph G,Recording &R){
	char node;
	cout<<"请输入您想开始遍历的顶点元素:";
	cin>>node;
	judge(G,node);
	int nodes;
	int keepnum = 0;
	nodes = LocateVex(G,node);
	for(int v=0;v<G.vexnum;++v){
		R.visited[v] = false;
		if(G.arcs[nodes][v].adj!=0&&nodes!=v){
			DFS(G,R,v);
		}
		if(G.arcs[nodes][v].adj==0&&nodes!=v){
			keepnum++;
		}
	}
	if(keepnum==0){
		return DFSTraverse(G,R);
	}
	return keepnode(G,R,keepnum,nodes);
}

int BFSTraverse(MGraph G,Recording &R){
	for(int v=0;v<G.vexnum;++v){
		R.visited[v] = false;
	}
	for(int v=0;v<G.vexnum;++v){
		if(R.visited[v] == false){
			DFS(G,R,v);
		}
	}
	int count = 0;
	for(int i=0;i<G.vexnum;++i){
		if(R.visited[i] == true){
			count++;
		} 
	}
	if(count == G.vexnum){
		cout<<"广度优先搜索成功！"<<endl;
	}
	else{
		for(int v=0;v<G.vexnum;++v){
		if(R.visited[v] == false){
			DFS(G,R,v);
			}
		}
	}
}

int Recordingtu(MGraph G,Recording &R){
	int i;
	cout<<"1:深度优先搜索"<<endl;
	cout<<"2:广度优先搜索"<<endl;
	cout<<"请输入您想搜索的模式:";
	cin>>i;
	switch(i){
		case 1:
			return keep(G,R);
		case 2:
			return BFSTraverse(G,R);
		default:
			cout<<"错误！请重新输入"<<endl;
				return Recordingtu(G,R);
	}
} 

int main(){
	MGraph G;
	CreateGraph(G);
	Recording R;
	Recordingtu(G,R);
	return 0;
}

最后

以上就是寒冷豆芽为你收集整理的C++邻接矩阵建图与遍历图的全部内容，希望文章能够帮你解决C++邻接矩阵建图与遍历图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。