图的表示方法

参见图的存储结构|邻接矩阵、邻接表、十字链表、邻接多重表、边集数组

正由于图的表示方法多种多样，各种题目给出的图结构也大不相同，我们难以同时熟练掌握这么多结构。但是，我们可以很容易地将其他图结构转换成自己熟悉的图结构，然后在此基础上解题，就会显得更有把握。下面的适配器就是用于此目的。

适配器

我们自己定义的图结构是最形象，功能最全面的结构，包含图、节点和边，如下：

struct graphEdge;
struct graphNode
{
    int value;
    int in;  //入度
    int out; //出度
    list<graphNode*> nexts; //邻点(指出去)
    list<graphEdge*> edges; //邻边(指出去)
    graphNode(int _value):value(_value), in(0), out(0){}
};
struct graphEdge
{
    int weight;
    graphNode* from;
    graphNode* to;
    graphEdge(int _weight, graphNode* _from, graphNode* _to):weight(_weight), from(_from), to(_to){}
};
struct graph
{
    unordered_map<int, graphNode*> nodes;
    unordered_set<graphEdge*> edges;
};

注意！该图是有向图，graphNode 中的 nexts 和 edges 都是指出去的对象，并不含指进来的对象！

graph 中的 nodes 为什么是 unordered_map<int, graphNode*> ？因为我们一般用整形来指代节点，而 graphNode 是自己定义的结构，它对客户是不透明的，所以必须建立映射关系。

在算法面试中，常见的图结构表示如下：

[weight, from, to]

这表示从 from 节点指向 to 节点，且边的权重为 weight，一个二维数组即可表示整张图：

vector<vector<int>> nodes = {{0,1,2},
                             {0,1,3},
                             {0,2,3},
                             {0,2,4},
                             {0,2,5},
                             {0,3,4},
                             {0,4,5},
                             {0,5,3}};

以该结构为例，将其转换为 graph 结构，适配函数如下：

graph graphAdaptor(vector<vector<int>> _graph)
{
    graph gra;
    int weight;
    int from;
    int to;
    for(int i = 0; i < _graph.size(); i++)
    {
        weight = _graph[i][0];
        from = _graph[i][1];
        to = _graph[i][2];
        if(gra.nodes.find(from) == gra.nodes.end())//易忽略,没有才加入
        {
            graphNode* node = new graphNode(from);
            gra.nodes.emplace(from, node);
        }
        if(gra.nodes.find(to) == gra.nodes.end())
        {
            graphNode* node = new graphNode(to);
            gra.nodes.emplace(to, node);
        }
        graphNode* nodeFrom = gra.nodes.at(from);
        graphNode* nodeTo = gra.nodes.at(to);
        graphEdge* edge = new graphEdge(weight, nodeFrom, nodeTo);
        nodeFrom->edges.push_back(edge);
        nodeFrom->out++;
        nodeTo->in++;
        nodeFrom->nexts.push_back(nodeTo);
        gra.edges.emplace(edge);
    }
    return gra;
}

当然，我们的图结构对某些题目而言可能存在冗余信息，不要紧，不用的信息直接忽略，只在适配器函数中初始化我们想要的信息即可。

图的深度优先遍历

思想很简单，唯一需要注意的是，必须保证已经访问过的节点不再访问，否则将无限递归。

void graphDFS_in(graphNode* node, unordered_set<graphNode*> &accessed)//注意这里必须引用！作为全局对象
{
    if(accessed.find(node) != accessed.end())//如果已经访问过,则返回
        return;
    std::cout << node->value << ", ";
    accessed.emplace(node);
    auto p = node->nexts.begin();
    while(p != node->nexts.end())
    {
        graphDFS_in(*p, accessed);
        p++;
    }
}
void graphDFS(graphNode* node)
{
    if(node == nullptr)
        return;
    unordered_set<graphNode*> accessed;
    graphDFS_in(node, accessed);
    std::cout << std::endl;
}

以上是递归实现，简洁易懂，下面看看迭代版本：

void graphDFS_stack(graphNode* node)
{
    stack<graphNode*> stk;
    unordered_set<graphNode*> set;
    graphNode* tmp;
    stk.push(node);
    set.emplace(node);
    std::cout<< node->value << ", ";
    while(!stk.empty())
    {
        tmp = stk.top();
        stk.pop();
        for(auto n : tmp->nexts)
        {
            if(set.find(n) == set.end())
            {
                stk.push(tmp);
                stk.push(n);
                set.emplace(n);
                std::cout<< n->value << ", ";
            }
        }
    }
    std::cout << std::endl;
}

图的广度优先遍历

和树的层序遍历相同，仍然使用队列进行 BFS ，但仍须注意已经访问过的节点不能再次访问。

void graphBFS(graphNode* node)
{
    if(node == nullptr)
        return;
    graphNode* tmp;
    queue<graphNode*> que;
    unordered_set<graphNode*> accessed;
    que.push(node);
    accessed.emplace(node);
    while(!que.empty())
    {
        tmp = que.front();
        que.pop();
        std::cout << tmp->value << ", ";
        auto p = tmp->nexts.begin();
        while(p != tmp->nexts.end())
        {
            if(accessed.find(*p) == accessed.end())
            {
                que.push(*p);
                accessed.emplace(*p);
            }
            p++;
        }
    }
    std::cout << std::endl;
}

注意，当图为非连通图时，以上方法无法遍历所有节点；对非连通图，需要以每个节点为起点都遍历一次，才能遍历完所有节点。