首页 > 其他分享 >邻接表存储实现图的深度优先遍历

邻接表存储实现图的深度优先遍历

时间:2022-12-11 22:34:50浏览次数:49  
标签:存储 遍历 int vertices ALGraph ArcNode 邻接 输入 first

题目要求

第一行输入顶点个数及边的个数,第二行依次输入各顶点,第三行开始依次输入边的两个顶点,用空格分开。最后输入深度优先遍历的起始点。

输出格式:

输出深度优先遍历结果,空格分开,若起始点不合理,则输出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

相关文章