图的遍历

BFS

DFS

边的类型

有向图：

树边：第一次由u探索到v时，v为白色
后向边：第一次由u探索到v时，v为灰色。
前向边：第一次由u探索到v时，v为黑色，且u的发现时间早于v的发现时间。
横向遍：第一次由u探索到v时，v为黑色，且u的发现时间晚于v的发现时间。

无向图：

可以证明，对在无向图进行DFS时，每条边要么是树边，要么是后向边。

树边：第一次由u探索到v时，v为白色。
后向边：第一次由u探索到v时，v为灰色。

因此我们在DFS无向图时，可以只将一个节点标记为”白色”或”灰色”。当由u探索到v，再由v开始深入探索时，会发现v已经被探索。但是由于在无向图中(u, v)和(v, u)是同一条边，我们只记录第一次发现边(u, v)时的类型。我们可以修改DFS，传入一个父亲节点的标号。在我们由u调用dfs(child = v, parent = u)后，v也会遍历其子节点，如果子节点等于parent，我们continue即可。

无权图最短路径

对一个无权的有向图或无向图，从一个源节点进行BFS可以发现所有其他节点到该源节点的最短路径：
设源节点s的距离s.d = 0。在进行BFS时每当我们从一个节点a的邻接链表中找到一个未发现的节点b时，更新b的距离b.d = a.d + 1。

如果只想找到源节点s到某一节点t的最短路径，没有必要给所有节点都附上一个距离。我们可以记录当前遍历时的层次level。当我们发现节点t时，路径长度刚好是level + 1。

如何处理路径不存在：如果从s到t的路径不存在，则s和t必然分居两个不同的BFS树中。因此如果从源节点s出发直到队列为空都未发现t，则不存在路径(s, t)。

无权图单源最短路径

LC127 单词接龙

思路：

将所有单词放入一个hashset中
单词作为顶点
如果替换一个单词的某一个字母到'a' - 'z'中的一个字母后（替换后不同于原单词），能在hashset找到替换后的单词，则两个单词之间存在一条边。此hashset也可同时充当visited数组使用。
以beginWord作为源节点进行BFS，如果找到endWord，返回当前的level + 1。

注意：
恶心人的测试用例中，wordList有的包含beginWord，有的不包含beginWord。为了防止自边导致的路径长度错误，我们要求两个单词之前如果存在边，必须只能替换一个字母，且不相同。这样就排除了自边的可能性。因为beginWord并没有被放在hashset里，因此在BFS时，可能有a->b->a的路径。我们可以将一开始就将beginWord从hashset中删除，彻底杜绝这种路径。也可以放任不管，因为这样的路径一定不是最短路径。

code

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        queue<string> bfsq{};
        bfsq.push(beginWord);
        if(words.count(beginWord)) words.erase(beginWord);

        int level = 1;
        while(!bfsq.empty())
        {
            auto level_size = bfsq.size();
            for(int i = 0; i < level_size; ++i)
            {
                auto node = bfsq.front();
                bfsq.pop();

                for(auto it = node.begin(); it != node.end(); ++it)
                {
                    auto c = *it;
                    for(char i = 'a'; i <= 'z'; ++i)
                    {
                        if(i != c)
                        {
                            *it = i;
                            if(words.count(node))
                            {
                                if(node == endWord)
                                {
                                    return level + 1;
                                }
                                words.erase(node);
                                bfsq.push(node);
                            }
                        }
                    }
                    *it = c;
                }

            }
            ++level;
            
        }
        return 0;
    }
};

将word枚举抽象成类的code

class Solution {
private:
    struct wordEnum
    {
        string& node;
        string::iterator it;
        char i;
        char c;

        wordEnum(string& node)
        :node(node)
        ,it(node.begin())
        ,i('a')
        ,c(*it)
        {}

        bool next()
        {
            if(it != node.end())
            {
                if(i != c)
                {
                    *it = i;
                }

                ++i;

                if(i > 'z')
                {
                    i = 'a';
                    *it = c;
                    ++it;
                    c = *it;
                }
            }

            return it != node.end();
        }
    };
    
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        queue<string> bfsq{};
        bfsq.push(beginWord);
        if(words.count(beginWord)) words.erase(beginWord);

        int level = 1;
        while(!bfsq.empty())
        {
            auto level_size = bfsq.size();
            for(int i = 0; i < level_size; ++i)
            {
                auto node = bfsq.front();
                bfsq.pop();

                auto wordenum = wordEnum(node);

                while(wordenum.next())
                {
                    if(words.count(node))
                    {
                        if(node == endWord)
                        {
                            return level + 1;
                        }
                        words.erase(node);
                        bfsq.push(node);
                    }
                }
            }
            ++level;
            
        }
        return 0;
    }
};

优化：双端搜索 //TODO

无权图多源最短路径

LC286 墙与门

反过来去找门到所有空房间的最短距离
将所有的门放入一个队列
BFS，记录层数，直到队列为空
- 探索上下左右，不是INF的忽略
- 发现INF时，用层数填充INF

技巧：把一个点移动四个方向，如果每次在移动前判断这个点能否朝某个方向移动，会导致程序逻辑分支很多，而且也容易写错。不如我们将四个方向{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} }预先放置在一个数组里，在移动时先加后判断。

code

class Solution {
private:

    enum
    {
        WALL  = -1,
        DOOR  = 0 ,
        EMPTY = INT_MAX
    };

    struct point
    {
        int x;
        int y;

        point(int x, int y)
        :x(x)
        ,y(y)
        {}

        friend point operator+(point lhs, point rhs)
        {
            return {lhs.x + rhs.x, lhs.y + rhs.y};
        }
    };

    

public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if(rooms.empty() || rooms.front().empty()) return;
        size_t row = rooms.size();
        size_t col = rooms.front().size();
        auto DIRECTIONS = vector<point>{{1,0},{-1,0},{0,1},{0,-1}};

        queue<point> bfsq{};
        // find all the doors 
        for(size_t i = 0; i < row; ++i)
        {
            for(size_t j = 0; j < col; ++j)
            {
                if(rooms[i][j] == DOOR)
                {
                    bfsq.emplace(i, j);
                }
            }
        }

        int level = 1;

        while(!bfsq.empty())
        {
            auto level_size = bfsq.size();
            for(int i = 0; i < level_size; ++i)
            {
                auto p = bfsq.front();
                bfsq.pop();

                for(const auto& direction : DIRECTIONS)
                {
                    auto np = p + direction;
                    if( np.x < 0 || 
                        np.y < 0 || 
                        np.x >= row || 
                        np.y >= col || 
                        rooms[np.x][np.y] != EMPTY)
                    {
                        continue;
                    }

                    rooms[np.x][np.y] = level;
                    bfsq.push(np);
                }
            }
            ++level;
        }
    }
};

LC542 01矩阵

同上题，将所有的为1的元素改为不可能存在的距离，比如-1。并将所有的0的坐标放入队列中。定义四个运动方向。进行BFS即可。

code

class Solution {
private:
    enum
    {
        EMPTY = 0,
        WALL  = -1,
    };

    struct point
    {
        int x;
        int y;

        point(int x, int y)
        :x(x)
        ,y(y)
        {}

        friend point operator+(const point& lhs, const point& rhs)
        {
            return {lhs.x + rhs.x, lhs.y + rhs.y};
        }
    };

    int row;
    int col;

    const static vector<point> DIRECTIONS;

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix.front().empty()) return {};

        row = matrix.size();
        col = matrix.front().size();

        queue<point> bfsq{};
        for(size_t i = 0; i < row; ++i)
        {
            for(size_t j = 0; j < col; ++j)
            {
                if(auto& pt = matrix[i][j]; pt == 1)
                {
                    pt = WALL;
                }
                else if(pt == 0)
                {
                    bfsq.emplace(i, j);
                }
            }
        }

        int level = 1;

        while(!bfsq.empty())
        {
            auto level_size = bfsq.size();
            for(size_t i = 0; i < level_size; ++i)
            {
                auto pt = bfsq.front();
                bfsq.pop();

                for(const auto& direction : DIRECTIONS)
                {
                    auto&& tmp = pt + direction;
                    if( tmp.x < 0 || 
                        tmp.y < 0 || 
                        tmp.x >= row || 
                        tmp.y >= col || 
                        matrix[tmp.x][tmp.y] != WALL)
                    {
                        continue;
                    }
                    matrix[tmp.x][tmp.y] = level;
                    bfsq.emplace(tmp);
                }
            }
            ++level;
        }

        return matrix;
    }
};

const vector<Solution::point> Solution::DIRECTIONS = {{1,0},{-1,0},{0,1},{0,-1}};

LC490 迷宫

无权图的路径问题。BFS即可。
产生一个点的四个边：

像前一题LC286 墙与门一样定义四个移动方向。不断使点向一个方向移动，直到再移动会碰到障碍物或超出边界为止。如果该点移动后和原来点一样，则不是一个可行的方向。

code

class Solution {
private:
    enum
    {
        EMPTY = 0,
        WALL = 1,
    };
    
    struct point
    {
        int x;
        int y;

        point(int x, int y)
        :x(x)
        ,y(y)
        {}

        friend point operator+(const point& lhs, const point& rhs)
        {
            return {lhs.x + rhs.x, lhs.y + rhs.y};
        }

        friend bool operator==(const point& lhs, const point& rhs)
        {
            return lhs.x == rhs.x && lhs.y == rhs.y;
        }

        vector<point> nextValidPoint(const vector<vector<int>>& maze)
        {
            auto pts = vector<point>{};
            for(const auto& d : VALID_DIRECTIONS)
            {
                auto tmp = point(this->x, this->y);
                while(isValidPoint(tmp + d, maze))
                {
                    tmp = tmp + d;
                }
                if(!(tmp == *this)) pts.push_back(tmp);
            }
            return pts;
        }

        bool isValidPoint(point p, const vector<vector<int>>& maze)
        {
            return !(   p.x < 0 || 
                        p.y < 0 || 
                        p.x >= maze.size() || 
                        p.y >= maze.front().size() || 
                        maze[p.x][p.y] == WALL
                    );
        }
    };

    struct pointHash
    {
        size_t operator()(const point& p) const
        {
            return hash<int>()(p.x) ^ hash<int>()(p.y);
        }
    };

    unordered_set<point, pointHash> visited;

    
    const static vector<point> VALID_DIRECTIONS;

public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        auto start_pt = point{start[0], start[1]};
        auto dest_pt = point{destination[0], destination[1]};
        queue<point> bfsq;
        bfsq.push(start_pt);
        visited.insert(start_pt);
         
        while(!bfsq.empty())
        {
            auto p = bfsq.front();
            bfsq.pop();

            for(auto pt : p.nextValidPoint(maze))
            {
                if(pt == dest_pt) return true;
                if(!visited.count(pt))
                {
                    visited.insert(pt);
                    bfsq.push(pt);
                }
            }
        }

        return false;
    }
};

const vector<Solution::point> Solution::VALID_DIRECTIONS = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};

有向无环图(DAG)

拓扑排序的实现

DFS实现

入度实现

思路：

统计所有点的入度。
循环直到图为空
- 选择一个入度为0的顶点，将其和其所有的出边从图中移除
- 如果不存在入度为0的顶点，图中有环，结束算法。
- 将该点放入输出中。
  实现：
建立一个hashmap或数组，统计所有点的入度。
建立一个栈，其中放入所有入度为0的点。
当栈非空时循环：
- 从栈中取出一个顶点，将其输出
- 减少所有和该顶点相邻的顶点的入度，如果减少后入度变为0，放入栈中
检查输出的大小和原来的顶点数是否一致。如果不一致则存在环。

拓扑排序

LC207 课程表
 LC210 课程表II
LC639 课程表III —>时间安排，贪心

LC269 火星词典

为所有出现的字符在图中生成节点
从头遍历两个相邻的字符串：
- 如果两个字符相等，查看下面两个字符
- 如果两个字符不相等，说明从前一个字符到后一个字符之间存在一条边。
将所有字符节点进行拓扑排序

code

class graph
{
private:
    struct Node
    {
        int inDegree;
        vector<char> neighbors;
    };
    unordered_map<char, Node*> nodes;
    Node* getOrCreateVertex(char vertex);
public:
    void createVertex(char vertex);
    void insertEdge(char from, char to);
    string topological_sort();
    ~graph();
};

void graph::createVertex(char vertex)
{
    if(nodes.count(vertex)) return;
    nodes[vertex] = new Node{};
}

graph::~graph()
{
    for(const auto& pair : nodes)
    {
        delete pair.second;
    }
}

graph::Node* graph::getOrCreateVertex(char vertex)
{
    if(nodes.count(vertex)) 
        return nodes[vertex];
    auto node = new Node{};
    nodes[vertex] = node;
    return node;
}

void graph::insertEdge(char from, char to)
{
    auto from_node = getOrCreateVertex(from);
    auto to_node = getOrCreateVertex(to);
    from_node->neighbors.push_back(to);
    ++to_node->inDegree;
}

string graph::topological_sort()
{
    auto tpsort = string{};
    
    vector<char> st{};
    unordered_map<char, int> inDegrees{};
    for(const auto& pair : nodes)
    {
        inDegrees[pair.first] = pair.second->inDegree;
        if(pair.second->inDegree == 0)
        {
            st.push_back(pair.first);
        }
    }
    
    while(!st.empty())
    {
        auto node = st.back();
        tpsort += node;
        st.pop_back();
        for(const auto& neighbor : nodes[node]->neighbors)
        {
            if(--inDegrees[neighbor] == 0)
            {
                st.push_back(neighbor);
            }
        }
    }

    return tpsort.size() == nodes.size() ? tpsort : "";

}

class Solution {
private:
    graph g;
public:
    string alienOrder(vector<string>& words) {
        if(words.empty()) return {};
        if(words.size() == 1)
        {
            return words.front();
        }

        for(const auto& word : words)
        {
            for(auto c : word)
            {
                g.createVertex(c);
            }
        }

        auto it1 = words.begin();
        auto it2 = ++words.begin();

        while(it2 != words.end())
        {
            insertEdge(*it1, *it2);
            ++it1; ++it2;
        }

        return g.topological_sort();
    }

    void insertEdge(const string& w1, const string& w2)
    {
        auto it1 = w1.begin();
        auto it2 = w2.begin();

        while(it1 != w1.end() && it2 != w2.end())
        {
            if(*it1 != *it2)
            {
                g.insertEdge(*it1, *it2);
                break;
            }

            ++it1; ++it2;
        }
    }
};

无根树

无根树是一个连通无向无环图。
在对无根树进行DFS时，只存在树边。因此遍历过程中不需要标记颜色，只要验证继续遍历的child不是其parent即可。
在对无根树进行BFS时，仍然需要visited数组。

树(图论), Wikipedia)
如果一个无向简单图$G$满足以下互相等价的条件之一，那么$G$是一棵树：

$G$是没有回路的连通图。
$G$没有回路，但是在$G$内添加任意一条边，就会形成一个回路。
$G$是连通的，但是如果去掉任意一条边，就不再连通。
$G$内的任意两个顶点能被唯一路径所连通。

树中路径的唯一性

LC582 杀死进程

利用树的性质：$G$内的任意两个顶点能被唯一路径所连通。我们只需遍历所有的PID，找到其到PID0进程的路径。如果被kill的进程是该PID的祖先，那么被kill的进程一定在该路径上。因此，如果某一PID到PID0的路径上中包含被kill的进程，则认为该进程是被kill进程的后代，因此也需要被kill。

code

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        auto res = vector<int>{};
        unordered_map<int, int> pid_map{};
        for(size_t i = 0; i < pid.size(); ++i)
        {
            pid_map[pid[i]] = ppid[i];
        }
        for(auto p : pid)
        {
            auto tmp = p;
            while(tmp)
            {
                if(tmp == kill) 
                {
                    res.push_back(p);
                    break;
                }
                tmp = pid_map[tmp];
            }
        }
        return res;
    }
};

判断无向图是否为树

用DFS对一无向图进行搜索，未发现后向边且只有一个连通分量。

LC261 以图判树

给定一个无向图，判断是否为树。

思路一：
一个无向图是树，当且仅当其没有后向边且连通分量为1时。用DFS检查后向边和连通分量即可。

DFS code

class Solution {
private:
    bool backEdge;
    vector<int> visited;
    vector<vector<int>> adjList;
public:
    bool validTree(int n, vector<vector<int>>& edges) {

        visited.resize(n);
        adjList.resize(n);
        backEdge = false;
        // since C++03 POD vector is guaranteed to be continuous
        memset(&visited[0], 0, sizeof(int) * visited.size());

        for(const auto& edge : edges)
        {
            // undirected graph
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        bfs(0, -1);

        return !backEdge && !count(visited.begin(), visited.end(), 0);
    }

    void bfs(int x, int parent)
    {
        if(backEdge) return;

        visited[x] = 1;

        for(auto child : adjList[x])
        {
            if(child == parent)
            {
                continue;
            }

            if(visited[child])
            {
                backEdge = true;
                return;
            }
                 bfs(child, x);
        }
    }
};

思路二：

不断地去合并边上的两个节点：

如果两个节点在没有合并之前就在同一个集合之中，则图中有环。
如果所有节点在合并之后，有多个根节点，则连通分量不为1。

code

class disjoint_set
{
private:
    vector<size_t> tree;
    vector<size_t> size;
public:
    disjoint_set(size_t sz)
    : tree(sz)
    , size(sz, 1)
    {
        iota(tree.begin(), tree.end(), 0);
    }
    size_t find(size_t idx)
    {
        vector<size_t> ids{};
        while(idx != tree[idx])
        {
            ids.push_back(idx);
            idx = tree[idx];
        }
        for(auto x : ids) tree[x] = idx;
        return idx;
    }

    bool connect(size_t idx1, size_t idx2)
    {
        auto rt1 = find(idx1);
        auto rt2 = find(idx2);

        if(rt1 == rt2) 
            return false;

        if(size[rt1] < size[rt2]) 
            swap(rt1, rt2);
        
        tree[rt2] = rt1;
        rt1 += size[rt2];

        return true;
        
    }

    bool single_set()
    {
        return adjacent_find(tree.begin(), tree.end(), [this](auto lhs, auto rhs){return find(lhs) != find(rhs);}) == tree.end();
    }
};

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        disjoint_set dset(n);
        for(const auto& edge : edges)
        {
            if(!dset.connect(edge[0], edge[1]))
                return false;
        }

        return dset.single_set();
    }
};

LC1361 验证二叉树|周赛177

code

class disjoint_set
{
private:
    vector<size_t> tree;
    vector<size_t> size;
public:
    disjoint_set(size_t sz)
    : tree(sz)
    , size(sz, 1)
    {
        iota(tree.begin(), tree.end(), 0);
    }
    size_t find(size_t idx)
    {
        vector<size_t> ids{};
        while(idx != tree[idx])
        {
            ids.push_back(idx);
            idx = tree[idx];
        }
        for(auto x : ids) tree[x] = idx;
        return idx;
    }

    bool connect(size_t idx1, size_t idx2)
    {
        auto rt1 = find(idx1);
        auto rt2 = find(idx2);

        if(rt1 == rt2) 
            return false;

        if(size[rt1] < size[rt2]) 
            swap(rt1, rt2);
        
        tree[rt2] = rt1;
        rt1 += size[rt2];

        return true;
        
    }

    bool single_set()
    {
        return adjacent_find(tree.begin(), tree.end(), [this](auto lhs, auto rhs){return find(lhs) != find(rhs);}) == tree.end();
    }
};

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        // find the root
        vector<int> isRoot(n, 1);

        for(int i = 0; i < n; ++i)
        {
            if(leftChild[i] != -1)
            {
                isRoot[leftChild[i]] = 0;
            }
            if(rightChild[i] != -1)
            {
                isRoot[rightChild[i]] = 0;
            }
        }

        if(count(isRoot.begin(), isRoot.end(), 1) != 1)
            return false;
        using edge = pair<int, int>;
        vector<edge> edges{};
        // generate all the edges
        for(int i = 0; i < n; ++i)
        {
            if(leftChild[i] == i || 
              rightChild[i] == i || 
              (leftChild[i] == rightChild[i] && leftChild[i] != -1))
            {
                return false;
            }
            
            if(leftChild[i] > i)
            {
                edges.emplace_back(i, leftChild[i]);
            }

            if(rightChild[i] > i)
            {
                edges.emplace_back(i, rightChild[i]);
            }
            
        }


        disjoint_set dset{n};

        for(const auto& edge : edges)
        {
            if(!dset.connect(edge.first, edge.second))
                return false;
        }

        return true;
    }
};

树的直径

LC1245 树的直径

树中所有最短路径中的最大值。

思路一：
对树中的每一个节点都做一次BFS。由于BFS一定会给出该节点到无根树中所有其他节点的最短距离，因此求所有最短距离的最大值即可。节点个数为$N$的无根树上做一次BFS复杂度为$\Theta(N)$，要做$N$次，则复杂度为$\Theta(N^2)$。

思路二：
对任意一个节点x做BFS找到距离它最远的节点s，再对s做BFS找到距离它最远的节点t。则$\delta(s, t)$即为直径。

证明参考：树的直径 Dedication

思路三：
可以将BFS换成需要维护状态较少的DFS。因为无根树是连通的，所以DFS也可以用来找到距离x最远的节点。虽然都是$\Theta(N)$的算法，但可以明显发现DFS速度要比BFS快很多。而且DFS的代码采用递归，写起来也比BFS更简洁。

两次BFS

class Solution {
private:
    vector<vector<int>> adjList;
    int vec_num;
public:
    int treeDiameter(vector<vector<int>>& edges) {
        vec_num = edges.size() + 1;
        adjList.resize(vec_num);
        for(const auto& edge : edges)
        {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        return bfs(bfs(0).first).second - 1;

    }

    pair<int, int> bfs(int start)
    {
        deque<int> bfsq{};
        vector<int> visited(vec_num, 0);
        bfsq.push_back(start);
        visited[start] = 1;
        
        int level = 0;
        int vec   = 0;

        while(!bfsq.empty())
        {
            auto level_size = bfsq.size();
            for(int i = 0; i < level_size; ++i)
            {
                vec = bfsq.front();
                bfsq.pop_front();
                for(auto child : adjList[vec])
                {
                    if(!visited[child])
                    {
                        bfsq.push_back(child);
                        visited[child] = 1;
                    }
                }
            }
            ++level;
        }

        return {vec, level};
    }
};

两次DFS

class Solution {
private:
    vector<vector<int>> adjList;
    int max_path_len;
    int max_path_end;
    int vec_num;
public:
    int treeDiameter(vector<vector<int>>& edges) {
        vec_num = edges.size() + 1;
        adjList.resize(vec_num);
        for(const auto& edge : edges)
        {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        max_path_len = 0;
        max_path_end = 0;

       dfs(0, -1, 0);
       max_path_len = 0;
       dfs(max_path_end, -1, 0);
       return max_path_len;

    }

    void dfs(int vec, int parent, int path_len)
    {     
        for(auto child : adjList[vec])
        {
            if(child != parent)
            {
                dfs(child, vec, path_len + 1);
            }
        }

        if(path_len > max_path_len)
        {
            max_path_len = path_len;
            max_path_end = vec;
        }
    }
};

LC310 最小高度树

思路一：
直径是无根树中最长的最短路径。
猜想：如果选出一个节点i作为该无根树的根节点，使得形成的树的高度最小，则该节点必然在此无根树的直径上，且是直径的中点：

如果该节点i不在无根树的直径上：因为无根树是连通的，则必然存在一条路径$\delta(i,j)$连接i到直径上的一点j。假设j是该直径$\delta(s, t)$的中点，那么形成的树的高度至少也是$\delta(i,j) + \frac\delta(s, t)}{2}$。
如果该节点i在无根树的直径上，要想让形成的树高度最小，就得让他能把直径分成尽量相等的两部分。所以i应该是直径的中点。

同上题使用DFS。第一次DFS找到直径的一个端点。第二次DFS找到直径长度。第三次DFS用回溯将直径构造出来，并切一旦找到长度为直径的path，其余遍历可全部剪掉。如果直径的长度为奇数，返回中点。如果直径的长度为偶数，就返回中间的两个点。

3次DFS

using namespace std;
class Solution {
private:
    int diameter_vec;
    int diameter;
    bool path_found;
    vector<int> path;
    vector<vector<int>> adjList;
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        adjList.resize(n);
        for(const auto& edge : edges)
        {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        diameter_vec = 0;
        diameter = 0;
        path_found = false;
        dfs(0, -1, 0);
        diameter = 0;
        dfs(diameter_vec, -1, 0);
        dfs_path(diameter_vec, -1, 0);

        if(path.size() & 1)
        {
            return {path[path.size() / 2]};
        }
        else
        {
            return {path[path.size() / 2], path[path.size() / 2 - 1]};
        }

    }

    void dfs(int vec, int parent, int sum)
    {
        for(auto child : adjList[vec])
        {
            if(child != parent)
            {
                dfs(child, vec, sum + 1);
            }
        }

        if(diameter < sum)
        {
            diameter = sum;
            diameter_vec = vec;
        }
    }

    void dfs_path(int vec, int parent, int sum)
    {
        if(path_found) return;
        path.push_back(vec);
        for(auto child : adjList[vec])
        {
            if(child != parent)
            {
                dfs_path(child, vec, sum + 1);
            }
        }

        if(path_found || diameter == sum)
        {
            path_found = true;
            return;
        }
        path.pop_back();
    }
};

树的重心

在无根树中找到这样一个节点i，当以i为根时，使i所有子树的节点数的最大值最小。

距离和问题

LC834 树中距离之和

利用无根树的性质：去掉无根树中任意一条边，无根树就不再连通，并且分成两个无根树。假设无根树中存在两个节点$x$, $y$，并且$x$和$y$是相邻的($\delta(x, y) = 1$)。则所有其他节点到$x$的路径和

= 以x为根的树中所有节点到x的路径和 + 以y为根的树中所有节点到y的路径和 + 以y为根的树中所有节点到x的路径和
= 以x为根的树中所有节点到x的路径和 + 以y为根的树中所有节点到y的路径和 + 以y为根的树中节点的个数
= 以x为根的树中所有节点到x的路径和 + 以y为根的树中所有节点到y的路径和 + 节点总数 - 以x为根的树中节点的个数

其他所有节点到$y$的路径和为：以y为根的树中所有节点到x的路径和 + 以x为根的树中所有节点到y的路径和 + 节点总数 - 以y为根的树中节点的个数

所以我们有：
其他所有节点到$x$的路径和 - 其他所有节点到$y$的路径和 = 以$y$为根的树中节点的个数 - 以$x$为根的树中节点的个数
因此：
其他所有节点到$x$的路径和
= 其他所有节点到$y$的路径和 + 以$y$为根的树中节点的个数 - 以$x$为根的树中节点的个数
= 其他所有节点到$y$的路径和 + 节点总数 - 2 * 以$x$为根的树中节点的个数

以一个节点为根的树的节点总数为：所有以其孩子为根的子树的节点总数的和 + 1
以一个节点为根的树的路径和为：所有以其孩子为根的子树的路径和的和 + 以该节点为根的树的节点总数 - 1
如果一个节点没有孩子
以该节点为根的树的节点总数为1
以该节点为根的树的路径和为0

code

class Solution {
private:
    vector<int> subsum;
    vector<int> count;
    vector<vector<int>> adjList;
    int N;
public:
    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
        this->N = N;
        subsum.resize(N);
        count.resize(N);
        adjList.resize(N);

        // initialize these vectors
        fill(subsum.begin(), subsum.end(), 0);
        fill(count.begin(), count.end(), 1);

        for(const auto& edge : edges)
        {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        dfs(0, -1);
        dfs_sum(0, -1);

        return subsum;
    }

    void dfs(int root, int parent)
    {
        for(auto child : adjList[root])
        {
            if(child != parent)
            {
                dfs(child, root);
                count[root]  += count[child];
                subsum[root] += subsum[child] + count[child];
            }
        }
    }

    void dfs_sum(int root, int parent)
    {
        for(auto child : adjList[root])
        {
            if(child != parent)
            {
                subsum[child] = subsum[root] + N - count[child] - count[child];
                dfs_sum(child, root);            
            }
        }
    }
};

欧拉轨迹

在图G中找到一条路径，这条路径包含图G中所有的边，且没有重复的边。这样的一条路径被称为欧拉路径(Eulerian path)。如果路径闭合，则称为欧拉回路(Eulerian cycle)。存在欧拉路径但不存在欧拉回路的图被称为半欧拉图(semi-Eulerian graph)。存在欧拉回路的图被称为欧拉图(Eulerian graph)

对于无向图：

连通的无向图G存在欧拉路径的充要条件是：G中度数为奇数的顶点的数目为0或2。
连通的无向图G存在欧拉回路的充要条件是：G中度数为奇数的顶点的数目为0。
连通的无向图G存在不是欧拉回路的欧拉路径的充要条件是：G中度数为奇数的顶点的数目为2。

对于有向图：

连通的有向图G存在欧拉路径的充要条件是：G中所有顶点的入度数等于出度数或有且仅有两个顶点，其中一个入度数比出度数大1，另一个出度数比入度数大1。
连通的有向图G存在欧拉回路的充要条件是：G中所有顶点的入度数等于出度数。
连通的有向图G存在不是欧拉回路的欧拉路径的充要条件是：有且仅有两个顶点，其中一个入度数比出度数大1，另一个出度数比入度数大1。

Heirholzer算法

在一个欧拉图或半欧拉图中，从任意一个顶点出发，做DFS。在从顶点u经过边(u, v)进入顶点v之前，删除边(u, v)。当一个顶点已经没有边时，将该顶点放入一个栈中。

dfs(node):
    while(u存在一条边(u, v)):
        删除边(u, v)
        dfs(v)
    将u加入栈中

如果图是欧拉图，那么栈的底部必然是开始遍历时的起点。
如果图是半欧拉图，那么栈的底部必然是异于开始遍历时的起点的一个顶点，且该顶点为奇度数顶点。
栈中自底到顶的第n个顶点就是欧拉回路上的第n的顶点。

参考
『图论』入门以及 Hierholzer 算法 - zxbsmk
欧拉回路 - Dedication

LC332 重新安排行程

思路：典型的求欧拉轨迹的问题。麻烦的地方在于其要求生成的行程必须是按字典许排列最大的。我们自然想到将顶点的出边按字典序排序。但如果我们将每个顶点的所有出边按照正字典序排序，得到的欧拉路径反而是按字典序排列最小的。[//TODO：原因可能跟函数调用栈返回的顺序有关，因为最后输出的欧拉路径也是相反的。]因此我们需要将顶点的出边按照逆字典序排序。

code

class Solution {
private:
    vector<string> path;
    unordered_map<string, vector<string>> adjList;
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(const auto& edge : tickets)
        {
            adjList[edge[0]].push_back(edge[1]);
        }
        
        for(auto& node : adjList)
        {
            sort(node.second.begin(), node.second.end(), greater<string>{});
        }
      
        dfs("JFK");
        reverse(path.begin(), path.end());
        return path;
    }

    void dfs(const string& node)
    {
        auto& neighbors = adjList[node];
        while(!neighbors.empty())
        {
            auto&& neighbor = neighbors.back();
            neighbors.pop_back();
            dfs(neighbor);
        }
        path.push_back(node);
    }
};

DeBruijn序列

De Bruijn 序列$B(k, n)$是

由k种元素构成。
是一个循环序列。
所有长度为$n$的子串恰好组成长度为n的k种符号的所有排列。

比如$01100$为$B(2,2)$序列中的一个，他恰好组成所有排列$01,\,11,\,10,\,00$：

+--------------+
| 0| 1| 1| 0| 0|
+--------------+
| 0| 1|  |  |  |
+--------------+
|  | 1| 1|  |  |
+--------------+
|  |  | 1| 0|  |
+--------------+
|  |  |  | 0| 0|
+--+--+--+------

构造方法：

将k元素$(n-1)$位的所有排列视为顶点
将k元素n位的所有排列视为边
一个顶点如果加上一个元素，其后$(n-1)$位能成为另一个顶点，则两个顶点之间存在一条边。
图中所有顶点必然有k个出边，$k$个入边，因此这样构造的图必然为欧拉图，存在欧拉环路。
利用Heirholzer算法，从任意顶点出发。求出其欧拉环路按顺序经过的边，记录为产生这些边而在顶点后加上的数字。将这些数字放入一个栈中。将这些数字从栈中取出(逆序)，在其序列头上附上出发顶点，即为一个De Brujin序列。

比如B(2,2)的例子：0加上0之后形成00，00的后1位仍然是0，则0存在自边。0加上1后形成01，01的后一位是1，则01之间存在一条边。

       +---------------+
       |      01       |
       |               v
  +-----+             +-----+
00|   |0|             |1|   |11
  +-->--+             +--<--+
       ^               |
       |      10       |
       +---------------+

dfs(vertex):
    for(i = 0; i < n; ++i):
        if((vertex.append(i)) is not visited):
            set vertex.append(i) visited
            dfs(vertex.append(i).substr(1))
            path.append(i)

参考
De Beruijn sequence - En-Jan Chou

LC753 破解保险箱

密码的每一位都由k种元素之一构成，一共有n位。保险箱会自动记住最后的n位。因此我们要生成含有所有排列的最短序列，即生成De Beruijn序列$B(k, n)$。思路同上。实现欧拉算法时比较麻烦的问题在于如何删除已经遍历的边。我们可以将已经遍历的边加入到一个hashset当中做查询。

code

class Solution {
private:
    unordered_set<string> visited;
    string ans;
    int k;
public:
    string crackSafe(int n, int k) {
        this->k = k;
        auto start = string{};
    
        for(int i = 0; i < n -1; ++i)
        {
            start += "0";
        }

        dfs(start);
        ans += start;
        reverse(ans.begin(), ans.end());
        return ans;
    }

    void dfs(string node)
    {
        for(int i = 0; i < k; ++i)
        {
            string edge = node + to_string(i);
            if(!visited.count(edge))
            {
                visited.insert(edge);  
                dfs(edge.substr(1));
                ans += to_string(i);
            }
        }
    }
};

其他

LC133 克隆图
思路类似LC138 复制带随机指针的链表

首先遍历图并复制一份所有图的节点。复制过程用建立<原节点，新节点>的对应hashmap。复制后再遍历hashmap，通过原节点到新节点的对应关系，恢复新节点之间的对应关系。

code

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(!node) return nullptr;
        unordered_map<Node*, Node*> mp{};
        deque<Node*> bfsq{};
        bfsq.push_back(node);
        mp[node] = new Node(node->val);

        while(!bfsq.empty())
        {
            auto nd = bfsq.front();
            bfsq.pop_front();
            for(auto neighbor : nd->neighbors)
            {
                if(!mp.count(neighbor))
                {
                    mp[neighbor] = new Node(neighbor->val);
                    bfsq.push_back(neighbor);
                }
            } 
        }

        for(const auto& pair : mp)
        {
            for(auto neighbor : pair.first->neighbors)
            {
                pair.second->neighbors.push_back(mp[neighbor]);
            }
        }

        return mp[node];
    }
};

Xuanyi Fu Blog

图(施工中)

图的遍历

BFS

DFS

边的类型

无权图最短路径

无权图单源最短路径

无权图多源最短路径

有向无环图(DAG)

拓扑排序的实现

DFS实现

入度实现

拓扑排序

无根树

树中路径的唯一性

判断无向图是否为树

树的直径

树的重心

距离和问题

欧拉轨迹

Heirholzer算法

DeBruijn序列

其他