圖的連通性，環路 以及 兩節點之間的最短路徑問題

先發表點小感慨..  其實練習算法和軟件工程之間某些準則還是有衝突的。看到算法里一堆全局變量以及閱讀性極差的編程方式，總感覺不爽。雖然老師也有講算法沒必要遵循那一套，但是還是小有糾結。 自己還是偏執的覺得應該儘量面向對象，必要的類和函數還是不可少的。

—–

進入正題，關於圖的一些基本知識。

關於圖的連通性和環路

假若圖是用鄰接矩陣的表示形式，並且矩陣中的值指的是某兩個結點之間的通路數。那麼，鄰接矩陣自乘N次代表N-1步后的通路情況，並且M(i,i)代表環路的情況。

這是線性代數在圖的連通性計算中的重要應用。

證明如下：

—————————————–

有向图的邻接矩阵

　　设有向图，，。令为邻接到的边的条数，称为D的邻接矩阵，记作。

为图7.12的邻接矩阵，不难看出：

　　(1)(即第i行元素之和为的出度)，。

　　(2)(即第j列元素之和为的入度)，。

　　(3)由(1)，(2)可知，为D中边的总数，也可看成是D中长度为1的通路总数，而为D中环的个数，即D中长度为1的回路总数。

　　D中长度大于等于2的通路数和回路数应如何计算呢？

　　为此，先讨论长度等于2的通路数和回路数。

　　在图D中，从顶点到顶点的长度等于2的通路，中间必经过一顶点。对于任意的k，若有通路，必有且，即。反之，若D中不存在通路，必有或，即。于是在图D中从顶点到顶点的长度等于2的通路数为：

　　由矩阵的乘法规则知，正好是矩阵中的第i行与第j列元素，记，即就是从顶点到顶点的长度等于2的通路数，时，表示从顶点到顶点的长度等于2的回路数。

　　因此，即矩阵中所有元素的和为长度等于2的通路总数(含回路)，其中对角线的元素和为长度等于2的回路总数。

　　根据以上分析，则有下面的推论。

定义 有向图，，D中长度为的通路数和回路数可以用矩阵(简记)来表示，这里，其中

，

　　即

　　则为顶点到顶点长度为的通路数，为到自身长度为的回路数。中所有元素之和为D中长度为的通路数，而中对角线上元素之和为D中始于(终于)各顶点的长度为的回路数。

　　在图7.12中，计算，，如下：

　　观察各矩阵发现，，，。于是，D中到长度为2的通路有3条，长度为3的通路有4条，长度为4的通路有6条。由，，可知，D中到自身长度为的回路各有1条(此时回路为复杂的)。由于，所以D中长度为2的通路总数为10，其中有3条回路。

　　从上述分析，可得下面定理。

定理7.5 设为有向图D的邻接矩阵，，则中元素为到长度为的通路数，为D中长度为的通路总数，其中为D中长度为的回路总数。

　　若再令矩阵

，

，

　　　　……

，

　　上面定理有下面推论。

推论　设，则中元素为D中到长度小于等于的通路数，为D中长度小于等于的通路总数，其中为D中长度小于等于的回路总数。

————————————————————

 

關於圖的最短路徑，常用的是Dijsktra算法

下面以題目為例：（Sicily 1031）

Sample Input

Copy sample input to clipboard

1  //case的數量
2  //通路的條數
South.xiaolitang South.xiongdelong 2   //通路及metric
South.xiongdelong Zhuhai.liyuan 100
South.xiongdelong South.xiaolitang    //計算該起始地址到目的地址的最短路徑長度

Sample Output

2               //輸出最短路徑長度

----------------------------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#define MAXINT 65535
using namespace std;

class route
{
public:
    string src;
    string dst;
    int metric;
};

int ini_graph(int**& matrix_ptr,map<string,int>& index_location_map);
void printmatrix(int** matrix,int f);
void destorymatrix(int** matrix,int f);
void Dijsktra(int** matrix,int f,map<string,int> index_location_map,string src,string dst);

 

int main()
{
    int c;
    cin >> c;
    for(int i = 0; i < c; i ++)
    {
        int f;
        int **matrix_ptr = NULL;                                      //图邻接矩阵
        map<string,int> index_location_map;          //index和location的对应关系
        f = ini_graph(matrix_ptr,index_location_map);
        //printmatrix(matrix_ptr,f);
        string src,dst;
        cin >> src >> dst;
        Dijsktra(matrix_ptr,f,index_location_map,src,dst);
        destorymatrix(matrix_ptr,f);
    }
    return 0;
}

 

int ini_graph(int**& matrix_ptr,map<string,int>& index_location_map)
{
    int c;
    cin >> c;    //路的条数
    vector<route> routes;
    int f = 0;
    for(int i = 0; i < c; i ++)
    {
        route r;
        string src;
        string dst;
        int metric;
        cin >> src >> dst;
        cin >> metric;
        r.src = src;
        r.dst = dst;
        r.metric = metric;
        routes.push_back(r);
        r.src = dst;
        r.dst = src;
        routes.push_back(r);    //因为是无向图,两个方向都要

        typedef map<string,int> String2int;
        if(index_location_map.find(src) == index_location_map.end())  //若找不到src
        {
            index_location_map.insert(String2int::value_type(src,f));
            f ++;
        }
        if(index_location_map.find(dst) == index_location_map.end())  //若找不到dst
        {
            index_location_map.insert(String2int::value_type(dst,f));
            f ++;
        }
    }

    //构造邻接矩阵
    //分配空间
    matrix_ptr = new int*[f];
    for(int i = 0; i < f; i ++)
        matrix_ptr[i] = new int[f];

    //初始化邻接矩阵，设为MAXINT
    for(int i = 0; i < f; i ++)
        for(int j = 0; j < f;  j ++)
        {
            matrix_ptr[i][j] = MAXINT;
        }
    for(int i = 0; i < f; i ++)
        matrix_ptr[i][i] = 0;  
    for(int i = 0;i < routes.size(); i ++)
    {
        matrix_ptr[index_location_map[routes[i].src]][index_location_map[routes[i].dst]] = routes[i].metric;
    }
    return f;
}

void printmatrix(int** matrix,int f)
{
    for(int i = 0; i < f; i ++)
    {
        for(int j = 0; j < f; j ++)
        {
            cout << matrix[i][j] << "  ";
        }
        cout << endl;
    }

}

void destorymatrix(int** matrix,int f)
{

    for(int j = 0; j < f; j ++)
    {
        delete[] matrix[j];
    }
    delete[] matrix;

}

void Dijsktra(int** matrix,int f,map<string,int> index_location_map,string src,string dst)
{
    if(src==dst)
    {
        cout << "0" << endl;
        return;
    }
    if(index_location_map.find(src)==index_location_map.end()||index_location_map.find(dst)==index_location_map.end())
    {
        cout << "-1" << endl;
        return;
    }
    int srcnum = index_location_map[src];
    int dstnum = index_location_map[dst];
    //初始化距离向量
    vector<int> distance_vector;
    for(int i = 0; i < f; i ++)                             
    {
        distance_vector.push_back(matrix[srcnum][i]);
    }

    vector<int> s;                        //s集合
    s.push_back(srcnum);
    vector<int> t;                        //t集合
    for(int i = 0; i < f; i ++)
    {
        if(i != srcnum)
            t.push_back(i);
    }

    int min_num;
    int tc;
    int d;
    for(int i = 0; i < f; i ++)
    {
        if(i != srcnum)
        {
            min_num = MAXINT;
            tc = 0; 
            d = t[0];   //这两行不加的话
            //第i行
            for(int j = 0; j < s.size(); j ++)                   //最核心部份。遍歷S中各個元素到T中各個元素
            {
                int k;
               for(k = 0; k < t.size(); k ++)
                {
                    if(distance_vector[t[k]]>(distance_vector[s[j]]+matrix[s[j]][t[k]]))
                    {
                        distance_vector[t[k]] = matrix[s[j]][t[k]]+distance_vector[s[j]];   //更新距離矢量
                    }
                    if(min_num>distance_vector[t[k]])
                    {
                        min_num = distance_vector[t[k]];
                        tc = k;
                        d = t[k];
                    }
                }
            }
            s.push_back(d);
            t.erase(t.begin()+tc);
        }
    }
    if(distance_vector[index_location_map[dst]]!=MAXINT)
        cout << distance_vector[index_location_map[dst]] << endl;
    else
        cout << "-1" << endl;
}

———————————-

《1988-我想和这个世界谈谈》

       中午的时候很惊叹卓越的出货速度，昨晚很晚才订的书今天中午就到了，很是惊喜。于是中午慵懒的爬起来去取书。混迹饭堂，图书馆，自然辩证法课堂，用了大约3个半钟就看完了。

      豆瓣上褒贬不一，自己看完也是五味杂陈，似乎书里面的世界是那么熟悉，但又是那么陌生。说实话，不知道是不是我还未充分深入探析，目前来说对这本书倒是也没太多的感觉。

      且不去过多研究“公路小说”的成色，受其影响，我总觉得主人公就是“韩寒”，或许他车开多了吧。但是结合书里面的情节把主人公和韩寒本人联系起来，总是感觉怪怪的。至于那个怀孕的妓女，或许他是想表达目前被社会强奸的当代人，而她的“孩子”或者就是她的一个寄托和一个梦。但从书中的描述来看，这个孩子注定却也是悲剧，因为他甚至不知道她的生父是谁，更不知道自己的未来在何方 —  或者去朝鲜留学，回来“光宗耀祖”？ 最后，妓女因为各种各样的病死了，孩子被寄托在了主人公手中，面对浑浊的一切，其实也不知道何去何从。 结合面对着“温水煮青蛙”的谎言，以及青蛙想要跳出而被锅盖挡住，被沸水烫死的过往经验，以及正义必将战胜邪恶，但是掌权者可以定义什么是正义的无奈，整个基调有些低沉及灰暗。

      其回忆的儿时的一些东西，我虽然很熟悉，却难以有共鸣 —  不知道是否有“代沟”。在小学的时候，早已经不会把什么“革命”“反革命”之类的挂在嘴边。虽然也会有暗恋女孩子，也会跟要好的朋友讨论女生如何如何；也会有疑惑红领巾是用“鲜血”染红的，那是不是会整天要去工厂用血去染布。但是，在书中的视角下，总是萦绕着一层厚重的折射镜。在我的记忆中，儿时的伙伴都是天真到不行。或者书中想拿那些最终或死或被投去监狱的伙伴来隐喻什么，但是实在难以引起我的共鸣。

      至于主人公的女友“孟孟”，那里描述的有段话我倒很喜欢：“我走的比她慢，只是她在超越我和我并肩的时候我推了她一把，仅此，这是所有我能做的，而后，她离开了我的臂长范围，我只能给她喊几句话，再远，她就听不到我说什么了。我不想走得快一些，因为那是我的节奏，在哪个节奏里我已经应接不暇。”或许是自己有类似的经历吧，我也不习惯无休止的追逐，特别是在追求一些我觉得很无趣的事情的时候。现代人确实有些忙碌，追名逐利到疯狂，虚荣的面具带了一层又一层。

     其实分析一下自己，自己带着自欺欺人的保护罩幸运的落在了世界上一个比较柔软的地方。对于一些不愿意看到的，或者一些暗面，大可“自欺欺人”的去无视了。当然，世界上不公平大把，好吧，中国不公平的事大把。但，我个人觉得，如果每个人都以各自的理想为主体，而不是一味去埋怨这个时代会更好。毕竟，目前来讲趋势还是好的，并且也没那么那么的黑暗。况且“黑暗势力”再庞大，我们才是未来的主体 — 尚是白纸的婴儿。当然，此类的“鞭挞”必不可少，这是社会进步的催化剂，而我们每个人的努力才是社会进步的驱动力嗬。

反省

       <刚刚打开Windows Live Writer的时候，发现上次版本更迭后变成了Writer 2011，不由得嘴角上扬 —  确实蛮符合我现在的心情嘛~>

       今天不知道是 出于什么原因，突然有一种心情：要对之前的自己的行为进行反省，以此“赎罪”。每年每年都在反省，而今年又快过去了，我也来慢慢的对今年的“所做所为”来一个总结，对未来有个小小的展望。

       2010年是非常神奇的一年，期间发生的事情也跌宕起伏。其实对于命运女神赐予我的身份，总是在“幸运儿”和“弃儿”之间交替。  最大的幸运是：我能听从孙老师的教诲，最终踏上了读研的道路。 孙老师，虽然您可能不知道，但是在我的心里我真的非常非常感谢您，您的教诲真的会影响到我的一生！我永远也不会忘记您没有吃饭等我到晚上10点，开车带我去吃晚饭谈心的那个晚上。   不幸运的是：我对于职场产生了陌生感和不确定感。连带去年去应聘IBM的实习生，到今年年初去应聘腾讯上海研究院，面完之后的心情无论是信心满满还是低落万分，最后都被刷掉了。这让我对自己的职业生涯有些信心不足。

       上半年，由于是毕业班，大家都很疯狂。除开忙完毕业论文的事，就被毕业旅行，各种聚餐和各种玩乐占据了。好吧，上半年的得失我就不再去追究，毕竟“毕业”这个理由有够充分。况且加入东校研究生会去当了个学术部副部长虽然是不务正业，但是认识了很多好朋友；加入cisco team更是认识了很多牛人朋友！！

       暑假的那两个月，那个项目我也不能多埋怨自己什么，加上做大四孩子们的实训TA也很enjoy，cisco team的training也很enjoy，所以pass….

       下半年，开始的踌躇满志，希望能达到某个目标，开始有够认真，一直持续了半个学期。期间一直在好好温习《Thinking in C++》,好好做算法和研习模式识别。但是之后，被老师讲说研究方向性错误，恰逢其中考试，不知道为什么，就如分水岭般懈怠了好多。虽然也有下载论文来看，但总是感觉静不下心来。并且，C++也没看了，算法也懈怠了。之后也被分手这种无聊的事情影响，并以此为借口没有认真学习，跑去AIESEC和一堆小朋友玩去了，整天虽然陪外国友人逛幼儿园逛街很开心，但却是浪费了不少时间。研会的“百川交汇”也故作焦头烂额状，其实也是以此为借口浪费了不少学习时间。至此，已经进入了期末考试月，由于固执的不喜欢java，一做java那死鬼作业也有所怨恨及懈怠。并且10多天来，天天早上逃课睡到中午 —  以不想上无聊课为借口浪费了不少本应该是学习的时间。期末考试的分数也是我追求的目标之一，却天天在抱怨作业的无聊，实属不该！

      反省如下：

      1。不要轻易被影响情绪，要把握好自己的方向。

      2。别借口多多，你其他事情其实没有那么忙

      3。要有一个完整的规划，并要严格按照计划来进行

      4。还有，别整天微波校内的了，人都变傻了！！！

      完

      好吧，要淡定…  无论在什么情况下….