# 7-1 邻接表存储实现图的深度优先遍历(7-1 depth first traversal of adjacency table storage implementation diagram)-其他

## 7-1 邻接表存储实现图的深度优先遍历(7-1 depth first traversal of adjacency table storage implementation diagram)

### include

using namespace std;
struct edge{
int v;
edge* next;
};
struct node{
char val;
edge* next;
}a[1010];
int n;

int find(char ch){
for(int i=0;i<n;i++){
if(a[i].val==ch){
return i;
}
}
return -1;
}

edge* e=new edge();
e->next=a[u].next;
e->v=v;
a[u].next=e;
}

bool st[1010];
void dfs(int u){
cout<<a[u].val<<‘ ‘;
st[u]=1;
edge* e=a[u].next;
while(e!=NULL){
if(st[e->v]==0){
dfs(e->v);
}
e=e->next;
}
}

int main(){
int m;
cin>>n>>m;

``````for(int i=0;i<n;i++){
char ch;
cin>>ch;
a[i].val=ch;
}

for(int i=0;i<m;i++){
char u,v;
cin>>u>>v;
int uu=find(u),vv=find(v);
}

char ch;
cin>>ch;
int k;
if((k=find(ch))!=-1){
dfs(k);
}else{
cout<<"error";
}

return 0;
``````

}

————————

Write a program to realize the function of depth first search traversal of the graph stored in the adjacency table. Vertices are character type.
Input format:
In the first line, enter the number of vertices and edges, in the second line, enter each vertex in turn, and in the third line, enter the two vertices of the edge in turn, separated by a space. Finally, enter the starting point of depth first traversal.
Output format:
Output depth first traversal results, separated by spaces. If the starting point is unreasonable, output error.

### include

using namespace std;
struct edge{
int v;
edge* next;
};
struct node{
char val;
edge* next;
}a[1010];
int n;

int find(char ch){
for(int i=0;i<n;i++){
if(a[i].val==ch){
return i;
}
}
return -1;
}

edge* e=new edge();
e->next=a[u].next;
e->v=v;
a[u].next=e;
}

bool st[1010];
void dfs(int u){
cout<<a[u].val<<‘ ‘;
st[u]=1;
edge* e=a[u].next;
while(e!=NULL){
if(st[e->v]==0){
dfs(e->v);
}
e=e->next;
}
}

int main(){
int m;
cin>>n>>m;

``````for(int i=0;i<n;i++){
char ch;
cin>>ch;
a[i].val=ch;
}

for(int i=0;i<m;i++){
char u,v;
cin>>u>>v;
int uu=find(u),vv=find(v);
}

char ch;
cin>>ch;
int k;
if((k=find(ch))!=-1){
dfs(k);
}else{
cout<<"error";
}

return 0;
``````

}