数据结构——图的遍历代码实现

蔚落 2024-04-18 19:04 52阅读 0赞

//图的邻接链表表示
    #define MaxN 50 //顶点数目最大值
    
    typedef struct ArcNode //邻接链表的表结点
    {
        int adjvex;//邻接顶点的顶点序号
        double weight;//边上的权值
        struct ArcNode *nextarc;//指向下一个邻接顶点的指针
    }EdgeNode;
    
    typedef struct VNode{//表头结点
        char data;//顶点标识的数据，以字符表示
        struct ArcNode *firstarc;//指向第一条依附于该顶点的边或弧的指针
    }AdjList[MaxN];
    
    typedef struct{
        int Vnum; //顶点数目
        AdjList Vertices;//邻接链表的表头列表
    }Graph;
    
    //深度优先搜索（DFS）
    int visitedDFS[MaxN] = {0};
    void DFS(Graph G,int i)
    {
        EdgeNode *t,int j;
        cout << i << endl;//访问序号为i的顶点
        visitedDFS[i] = 1;//标记已经被访问的顶点
    
        t = G.Vertices[i].firstarc;
        while (t != NULL) {
            j = t->adjvex;//顶点j为顶点i的一个邻接顶点
            if(visitedDFS[j] == 0){
                DFS(G,j);
            }
            t = t->nextarc;//继续访问下一个邻接顶点
        }
    }
    
    //调用
    //Graph G;
    //for(int i = 0; i < G.Vnum;i++){
    //    if(visitedDFS[i] == 1){
    //        continue;
    //    }
    //    DFS(G,i);
    //}

# 广度优先搜索暂未验证，不可轻易使用！代码如下： #

//图以及需要遍历的顶点的列表
    int visitedBFS[MaxN] = {0};
    void BFS(Graph G,vector<int> vecIndex)
    {
        if(vecIndex.size() == 0){
            return;
        }
        EdgeNode *t;
        vector<int> vecNewIndex;
        for(int i = 0; i < vecIndex.size();i++){
            int index = vecIndex[i];
            if(visitedBFS[index] == 1){
                continue;
            }
            visitedBFS[index] = 1;
            cout << index << endl;
            t = G.Vertices[index].firstarc;
            while (t != NULL) {
                vecNewIndex.push_back(t->adjvex);
                t = t->nextarc;
            }
        }
        BFS(G,vecNewIndex);
    }
    
    //调用BFS
    //Graph G;
    //for(int i = 0; i < G.Vnum;i++){
    //    if(G.Vertices[i].firstarc == NULL || visitedBFS[i] == 1){
    //        visitedBFS[i] = 1;
    //        continue;
    //    }
    //    vector<int> vec;
    //    vec.push_back(i);
    
    //    BFS(G,vec);
    //}