题目要求
第一行输入顶点个数及边的个数,第二行依次输入各顶点,第三行开始依次输入边的两个顶点,用空格分开。最后输入深度优先遍历的起始点。
输出格式:
输出深度优先遍历结果,空格分开,若起始点不合理,则输出error。
输入样例:
在这里给出一组输入。例如:
8 9
0 1 2 3 4 5 6 7
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6
0
输出样例:
在这里给出相应的输出。例如:
0 2 6 5 1 4 7 3
源码如下
#include<iostream> using namespace std; #define MVNum 100 typedef char OtherInfo; int visited[MVNum]={0};//visited数组 //邻接表:顶点表、边表、邻接表 typedef struct ArcNode{ int adjvex;//下标信息 OtherInfo info;//其他信息 struct ArcNode* next; }ArcNode; typedef struct VNode{ char vex;//顶点信息 ArcNode* first; }VNode,AdjList[MVNum]; typedef struct{ AdjList vertices; int vexnum,arcnum; }ALGraph; int LocateVex(ALGraph G,char v){ for(int i=0;i<G.vexnum;++i){ if(G.vertices[i].vex==v)return i; } return -1; } void CreatALGraph(ALGraph &G,int &err) { cin>>G.vexnum>>G.arcnum;//输入的点数和边数 for(int i=0;i<G.vexnum;++i){//输入顶点信息,初始化first边表 cin>>G.vertices[i].vex; G.vertices[i].first=NULL; } for(int k=0;k<G.arcnum;++k){//边表 char v1,v2; cin>>v1>>v2; int i,j; i=LocateVex(G,v1);j=LocateVex(G,v2); if(i==-1||j==-1)err=1; else{ ArcNode * p1=new ArcNode;//**不要忘记new p1->adjvex=j; p1->next=G.vertices[i].first; G.vertices[i].first=p1; ArcNode * p2=new ArcNode;//**不要忘记new p2->adjvex=i; p2->next=G.vertices[j].first; G.vertices[j].first=p2; } } } void DFS_ALGraph(ALGraph G,int adj) { cout<<G.vertices[adj].vex<<" "; visited[adj]=1; ArcNode* p=G.vertices[adj].first; while(p!=NULL){ if(visited[p->adjvex]!=1)DFS_ALGraph(G,p->adjvex);//不要忘记还要判断visited数组 p=p->next; } } int main() { ALGraph G; int err=0; char star; CreatALGraph(G,err); cin>>star;//输入起始点 int adj=LocateVex(G,star); if(adj==-1||err==1) cout<<"error"; else{ DFS_ALGraph(G,adj); } return 0; }
代码参考网络,理解思路即可
算法简图
标签:存储,遍历,int,vertices,ALGraph,ArcNode,邻接,输入,first
From: https://www.cnblogs.com/jiacheng-712/p/16974726.html