鲁大师的图的DFS c++实现

缺乏、安全感 2022-12-24 00:39 161阅读 0赞

主体还是PPT上的代码，只是访问函数稍稍改动了一下  
然后补充了辅助函数的实现，都不难  
时间复杂度分析在注释里

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int MVNUM = 1e2 +5;
    const int INF = 65535;
    typedef int Status;
    typedef char VertexType;
    
    typedef struct
    {
        
        VertexType vextable[MVNUM];
        int adj[MVNUM][MVNUM];
        int vexnum, arcnum;
    }MGraph;
    
    //0表示没被访问
    //1表示访问过了
    int visited[MVNUM];
    
    //查找节点的对应的数组下标
    int LocateVex(MGraph G, VertexType u)
    {
        
        for (int i = 0; i < G.vexnum; i++)
        {
        
            if (G.vextable[i] == u)
                return i;
        }
    }
    
    Status visit(MGraph G, int v)
    {
        
        printf("%c ", G.vextable[v]);
        return 1;
    }
    int FirstAdjVex(MGraph G, int v)
    {
        
        for (int i = 0; i < G.vexnum; i++)
        {
        
            if (G.adj[v][i] != 0)
                return i;
        }
        return -1;
    }
    int NextAdjVex(MGraph G, int v, int w)
    {
        
        for (int i = w + 1; i < G.vexnum; i++)
        {
        
            if (G.adj[v][i] != 0)
                return i;
        }
        return -1;
    }
    void DFS(MGraph G, int v, Status(*visit)(MGraph, int))
    {
        
        visit(G, v);
        visited[v] = 1;
        for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
            if (visited[w] == 0)
            {
        
                DFS(G, w, visit);
            }
    }
    //DFS的时间复杂度
    //邻接矩阵的存储结构
    //毕竟要遍历n个节点，每个节点都要找他的全部临界点又是一个n
    //所以时间复杂度是O(n^2)
    
    void DFSTraverse(MGraph G, Status(*visit)(MGraph, int))
    {
        
        for (int v = 0; v < G.vexnum; v++) visited[v] = 0;
        //这种处理是为了处理非连通图
        for (int v = 0; v <G.vexnum; v++)
            if (visited[v] == 0)
                DFS(G, v, visit);
    }
    int main()
    {
        
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        MGraph G;
        cin >> G.vexnum >> G.arcnum;
        for (int i = 0; i < G.vexnum; i++)
            cin >> G.vextable[i];
    
        for (int i = 0; i < G.vexnum; i++)
            for (int j = 0; j < G.vexnum; j++)
                G.adj[i][j] = 0;
    
        for (int i = 0; i < G.arcnum; i++)
        {
        
            VertexType v1, v2;
            int pos1, pos2;
            cin >> v1 >> v2;
            pos1 = LocateVex(G, v1);
            pos2 = LocateVex(G, v2);
            G.adj[pos1][pos2] = 1;
            G.adj[pos2][pos1] = 1;
        }
        DFSTraverse(G, visit);
        return 0;
    }