算法导论：c++实现图

r囧r小猫 2022-05-31 13:47 175阅读 0赞

### 图的表示 ###

![这里写图片描述][70]

![这里写图片描述][70 1]

![这里写图片描述][70 2]

这里用结构体来表示图G，和图顶点GraphNode，后面要用到的顶点颜色用枚举类型表示

enum color
    {
        white = 0,
        gray,
        black
    };
    struct graphNode {
        char name;  //顶点名
        struct graphNode *pre;  //前驱节点
        int d; //深度
        color c; //节点颜色
        graphNode(char n):name(n),pre(NULL),c(white),d(0) {}
    };
    struct graph {
        vector<graphNode *> v;  //顶点集合
        map<char, list<graphNode *>> adj; //邻接链表，方便用顶点查找
    };

![这里写图片描述][70 3]

### 广度优先搜索 ###

![这里写图片描述][70 4]  
**伪代码**  
![这里写图片描述][70 5]

**书上的示例图解**  
![这里写图片描述][70 6]

根据书上的伪代码编写广度优先程序

graph BFS(graph G, graphNode *s)
    {
        s->c = gray;
        s->d = 0;
        deque<graphNode*> q; //创建一个双端队列
        q.push_back(s);
        while (!q.empty())
        {
            graphNode *cur = q.front();
            q.pop_front();
            char n = cur->name;
            for (graphNode *u : G.adj[n]) //遍历当前顶点的邻接链表
            {
                if (u->c == white) {
                    u->c = gray;
                    u->d = cur->d+1;    //顶点深度为当前顶点深度加1
                    u->pre = cur; //前驱为当前顶点
                    q.push_back(u); //入队
                }
            }
            cur->c = black;
        }
        return G;
    }

图的初始化由上图示例初始：

graph initGraph() {
        graph G;
        G.v = {
       new graphNode('r'),new graphNode('v'),new graphNode('s'),new graphNode('w'),
            new graphNode('t'),new graphNode('x'),new graphNode('u'),new graphNode('y') };
        //初始化邻接链表
        G.adj['r'] = { G.v[1],G.v[2] };
        G.adj['s'] = { G.v[3],G.v[0] };
        G.adj['w'] = { G.v[2],G.v[4],G.v[5] };
        G.adj['t'] = { G.v[5],G.v[1],G.v[6] };
        G.adj['x'] = { G.v[4],G.v[3],G.v[6],G.v[7] };
        G.adj['u'] = { G.v[4],G.v[5],G.v[7] };
        G.adj['y'] = { G.v[5],G.v[6] };
        G.adj['v'] = { G.v[0]};
        return G;
    }

调用：

int main()
    {
        graph G = initGraph();
        BFS(G,G.v[2]);
    }

### 打印最短路径 ###

//打印路径
    void printPath(graph G, graphNode *s, graphNode *v) {
        if (s == v) {
            cout << s->name;
        }
        else if (v->pre == NULL) {
            cout << "no path!";
        }
        else {
            printPath(G, s, v->pre);
            cout << v->name;
        }
    }

调用：

int main()
    {
        graph G = initGraph();
        G=BFS(G,G.v[2]);
        printPath(G, G.v[2], G.v[6]);
    }

输出：

> swtu

[70]: /images/20220531/4f7020c068de4f3696e8e360789e0ab8.png
[70 1]: /images/20220531/692a7b975f154464ab4cd7238784d739.png
[70 2]: /images/20220531/e600c2c3283b4b82a09d0d6cc85da482.png
[70 3]: /images/20220531/450c0ae42a4a467f9abcf5f9cd412323.png
[70 4]: /images/20220531/33fdb57c40fe4aa0987fa01fe26491df.png
[70 5]: /images/20220531/e375a7cb4bd8414ba26469e27f5f0ddd.png
[70 6]: /images/20220531/4981b2c711e44898947326220e89ed70.png