LeetCode-剑指 Offer II 114. 外星文字典，BFS 搜索算法及图的表示

剑指 Offer II 114. 外星文字典
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

背景知识

图的概念

图是由节点以及连接这些节点边组成.

图的表示方法

①．邻接矩阵
邻接矩阵是表示图中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵的row和col表示的是0-n-1的n个点。
对包含n个节点的图，可以用二维数组（矩阵）来表示节点之间两两的连接关系

vector<vector<int>> edges;//用二纬数组表示各点之间两两的连通关系
int val = edges[i][j];//表示从节点i到节点j的边，0则表示非连通，有权重时也可以表示权重值

②．邻接列表

邻接矩阵可以方便的得到一个节点到另个节点的关联关系，但是邻接矩阵给每个节点都分配n个边的空间，但实际有许多变是不存在的，会造成空间的浪费。

vector<vector<vector<int>>>edges(n);//无权图时，用n个二维数组构成的vector来存储邻接列表
edges[i][j][0];//表示节点i的第j个连通节点编号
edges[i][j][1];//表示节点i到第j个连通节点边的权重

③．边缘列表
边缘列表是具有连接顶点及其权重的边的集合。

vector<vector<int>> edges;//带权图时，用一系列长度为3的vector构成vector来存储边缘列表
int u = edges[i][0];//第i条边的起点
int v = edges[i][1];//第i条边的终点
int val = edges[i][2];//边 u -> v 的权重

BFS 搜索算法

①．概念
广度优先搜索（BFS）的本质就是从源点出发，按层顺序进行遍历，把每一层的所有节点访问完后再转到下一层；使用队列（queue）来记录将要访问的点，访问完每个点就出队，然后把它的邻近点入队；同时要记录哪些点被访问过以避免重复访问。

②．BFS 搜索算法模板

int depth = 0 // 记录遍历到第几层，当前在第几层则和源点的距离为几
while( !queue.empty())//队列非空
{
    depth++;//
    int queue_size = queue.size();// 当前层的元素个数
    for(int i = 0;i < queue_size;i++)
    {
        cur_node = queue.front();queue.pop();//取出当前节点并从队列中删除
        for node 的所有相邻结点 m:
            if m 未访问过:
                queue.push(m);
                //标记访问状态，一定要在加入队列时就要标记其访问状态
                /*****/
    }
}

题目分析

题目分析

①．两个相邻字符的第一个不相同的字符，构成了一个先后顺序，可视为有向图的一条边。

②．依次遍历和比较列表中的所有相邻字符串，构建图的邻接列表，并记录节点的入度。

③．采用 BFS 算法，入度为 0 的节点先入队。

④．根据题目描述，若前面字符串是后面字符串的前缀，则直接返回空。

代码示例

class Solution {
public:
    string alienOrder(vector<string>& words) {
        
        unordered_map<char,unordered_set<char> > edges;//邻接列表
        unordered_map<char,int> inedg;//节点的入度
        //初始化图的节点
        for( auto & word : words )
        {
            for( auto & c : word)
            {
                if( edges.find(c) == edges.end() )
                {
                    edges[c] = {};
                    inedg[c] = 0;
                }
            }
        }
        //构建邻接列表
        int size = words.size();
        for( int i = 0;i+1 < size;++i)
        {
            auto word_1 = words[i];
            auto word_2 = words[i+1];

            int size_1 = word_1.size();
            int size_2 = word_2.size();

            int j = 0;
            while( j < size_1 && j < size_2 )
            {
                if( word_1[j] != word_2[j] )//第一个不相同的字母
                {
                    if( edges[ word_1[j] ].find(word_2[j]) == edges[ word_1[j] ].end() )
                    {
                        edges[ word_1[j] ].insert( word_2[j] );//可访问节点增加
                        inedg[word_2[j]] ++;//节点入度增加
                        
                    }
                    break;
                }   
                ++j;
            }
            if( j == size_2 && j < size_1) return "";// 前面字符串长度大于后面字符串
        }

        queue<char> m_queue;
        for( auto & edg : inedg )
        {
            if( edg.second == 0 ) m_queue.push( edg.first );
        }

        string res = "";
        while( !m_queue.empty())
        {
            auto u = m_queue.front();m_queue.pop();
            res.push_back(u);
            for( auto v : edges[u])
            {
                if( --inedg[v] == 0)
                {
                    m_queue.push(v);
                }
            }
        }
        if( res.size() != edges.size() ) return "";
        return res;

    }
};