鍊式前向星原理、實作及BFS，DFS和Dijkstra算法

• 前言
• • 鍊式前向星的原理
  • 鍊式前向星的實作
  • • 如何用鍊式前向星存無向圖
  • BFS
  • DFS
  • Dijkstra

前言

我在學習圖的時候，接觸到鍊式前向星這個資料結構，看了很多CSDN上的部落格，非常感謝部落客們的貢獻，但是感覺他們寫的其實大同小異，而且他們大多隻說了它的用處及實作，沒有很清楚地說到鍊式前向星的原理，也就是為什麼要這樣構造，為什麼這樣構造可以work,而且可能他們習慣了C風格的命名方式使得别人更加難以根據變量名去了解這個結構。

而我在問了大神，用了鍊式前向星做BFS,DFS,還有dijkstra算法之後才真正明白為什麼鍊式前向星要這樣構造，是以分享出來給大家。因為也是剛入門資料結構，有問題請大家輕拍。

鍊式前向星的原理

一如在_Gion寫的鍊式前向星筆記及别人寫的部落格裡面說到的，鍊式前向星是用來存圖的。但是他們好像并沒有很清楚說明它的原理，是以我想說說它的原理。

鍊式前向星最基本的是用來存有向圖的，當然稍作改造就可以存無向圖了。

先附上基本的代碼：

//假定所有node和edge的編号從1開始，是以數組都要加多一個元素
struct Edge{
	int nextEdgePosition;
	int toNodePosition;
	int weight;//權重
	}

Node nodes[nodeNum+1];//圖中的所有結點
Edge edges[edgeNum+1];//用來記錄圖中的所有邊
heads[nodeNum+1];//用來記錄每一個節點的第一條邊在edges裡的位置
           

以上代碼是鍊式前向星的基礎。

其實鍊式前向星隻是一個複合的結構，一個edges數組完全可以用三個數組代替，即:

int nextEdgePositons[edgeNum+1];
int toNodePostions[edgeNum+1];
int weights[edgeNum+1];
//拆分成數組可以友善在Java裡建構更快的代碼
//特别是當OJ系統（特别辣雞的）算上GarbageCollection時間時，如果用内部類Class Edge代替C中的struct Edge，GC花費的時間會多很多
           

前面的隻是鋪墊，現在才開始講原理。

其實鍊式前向星的原理就是用數組去實作連結清單（完結撒花！）

具體是什麼意思呢？

回想存圖的時候用的鄰接表，它是用連結清單實作的，這個部落格有很形象的表示

轉圖如下

而鍊式前向星裡的heads數組就是存的是每一個節點的第一條邊在edges數組裡的位置，即

Edge firstEdgeOfOneNode = heads[oneNode];//oneNode指某個節點的編号。
           

那我們要怎麼獲得某節點第一條邊的下一條邊存在edges數組的哪裡呢？

Edge nextEdge = edges[firstEdgeOfOneNode.nextEdgePostion];
//同理可以按順序獲得某個節點的所有出度（也就是指向其他節點的邊）
//如果我們知道了某個節點的編号為nodeIdx，則可以枚舉它的所有出度

for(Edge edge = edges[heads[nodeIdx]]; 繼續條件; edge = edges[edge.nextEdgePosition] )
//在鄰接表裡，我們用的繼續條件當然是edge != null
//而鍊式前向星裡我們一般用的是edge.nextEdgePostion != -1
//因為我們一般初始化heads[]全為-1而且鍊式前向星周遊邊的順序跟存圖添加邊時的順序是反過來的（先記住，詳細的解釋在後面）
           

我們知道了邊，還要知道邊指向的節點

int nodeIndex = edge.toNodePosition; //edge裡的toNodePosition存着這一條邊指向哪一個節點
Node node = nodes[nodeIndex];
           

這之前，我們都是假設圖已經用鍊式前向星存好了，我們知道了怎麼去周遊邊，怎麼樣擷取邊指向的節點，當然可以進行跟圖相關的操作，比如說BFS，DFS,Dijkstra.接下來說鍊式前向星的實作，而之前周遊邊時用的繼續條件是edge.nextEdgePostion != -1，這個是跟實作有關的，也是我原來看别人的部落格看不明白的地方之一。

鍊式前向星的實作

鍊式前向星最重要的是加邊的操作，具體的例子可以看euzmin的文章

從該文章轉個圖，可以根據這個圖嘗試以下步驟

int count =0;
//heads[]全部初始化為-1
void addEdge(int from,int to,int weight)//from指edge出發的節點，to指指向的節點
{
    count++;//因為edge标号從1開始，可以簡化
    edges[count].weight = weight;
    edges[count].toNodePosition = to;
    edges[count].nextEdgePosition = head[from];
    heads[from] = count;
}
           

從上面的代碼可以推測：

第一個節點的第一條被加進來的邊的nextEdgePositon肯定是-1（因為heads所有元素都是-1）

更進一步，每一個節點的第一條被加進來的邊的nextEdgePosition都是-1，因為heads[from] =count這一句，如果下标from處的heads元素沒有被通路過，元素值肯定是-1。

而如果heads[from]的元素被第二次、第三次…通路（也就是給出發的節點不斷加出度）會發生什麼？

當然heads[from]的值會不斷更新。

舉例子，該節點已經有了一條出度，再添加一條出度的時候，看這三條代碼：

count++;
.....
edges[count].nextEdgePosition = heads[from];//此時heads[from]記錄的是第一條edge的位置
heads[from] = count;//更新heads[from]，使之記錄第二條edge的位置
           

更新到什麼時候為止？更新到該節點的最後一條出度為止。

所有heads[n]記錄的是标号是n的節點的加進來最後一條出度在edges裡面的位置。

如果我們用1~k按添加的先後順序給某個節點（節點編号為n）的所有出度标号，則heads[n] = 第k出度在edges裡面的位置，而k.nextEdgePosition = 第(k-1)出度在edges裡面的位置。

是以使用

for(Edge edge = edges[heads[nodeIdx]]; 繼續條件; edge = edges[edge.nextEdgePosition] )
           

是從第k->1條出度周遊某個節點的出度。最終周遊到的出度是該節點第一條被加進來的出度，而該出度的nextEdgePosition是什麼？ 是-1

知道了怎麼樣周遊出度，怎麼樣獲得出度指向的節點，就可以開心地用BFS,DFS,Dijkstra啦。

如何用鍊式前向星存無向圖

其實無向圖就是有向圖的一種（大概），給每個相連節點直接加兩條相反的邊就行

附上代碼

int count =0;
//heads[]全部初始化為-1
void addEdge(int node1,int node2,int weight)
{
    count++;
    edges[count].weight = weight;
    edges[count].toNodePosition = node1;
    edges[count].nextEdgePosition = head[node2];
    heads[node2] = count;
    
    count++;
    edges[count].weight = weight;
    edges[count].toNodePosition = node2;
    edges[count].nextEdgePosition = head[node1];
    heads[node1] = count;
}
           

BFS

BFS的原理請另看他處

附上Java代碼，C++的大同小異

//因為要應付辣雞OJ（就是說的是南科大的OJ）是以把edges[]拆成了兩個數組（無權圖）int[] tos,int[] nexts
//這兩個數組長度是OJ測試樣例最大長度，實際使用時可以稍作修改
    static Queue<Integer> queue = new LinkedList<>();
    private static boolean bfsTraverse(int startNode, int endNode, int nodeNum, int[] head, int[] tos,int[] nexts )
    {
        boolean[] beenVisited = new boolean[nodeNum+1];
        queue.offer(startNode);
        while(!queue.isEmpty())
        {
            int currentNode = queue.poll();
            if(currentNode==endNode)
                return true;
            for(int edge = head[currentNode];edge!=-1;edge = nexts[edge])
            {
                int neighbor = tos[edge];
                if(!beenVisited[neighbor])
                {
                    beenVisited[neighbor] =true;
                    queue.offer(neighbor);
                }
            }
        }
        return false;
    }
           

DFS

DFS的原理請另看他處

//也是把edges[]拆成了兩個數組
    static boolean canAccess = false;
    private static void dfs(int current, int end,boolean[] beenVisited, int[] head, int[] tos,int[] nexts)
    {
        if(current==end)
            canAccess=true;
        else
        {
            beenVisited[current] =true;
            for(int edge=head[current];edge !=-1;edge = nexts[edge])
            {
                int neighbor = tos[edge];
                if(!beenVisited[neighbor])
                    dfs(neighbor,end,beenVisited,head,tos,nexts);
            }
        }
    }
           

Dijkstra

這個是C++的代碼

//把有權圖的edges[]拆成了int tos[],int nexts[],int heads[],int weights[]
//這個是根據資料結構課上的僞代碼實作的，還有更快的實作方式
void dijkstra (int tos[],int nexts[],int heads[],int weights[],int start)
{
    int dist[nodeNum+1];
    int parents[nodeNum+1];
    fill(dist,dist+(nodeNum+1),INT_MAX);
    fill(parents,parents+nodeNum+1,-1);
    dist[start] =0;
    int currentNode = start;
    set<int> nodeset;
    for(int i=1;i<=nodeNum;i++)
        nodeset.insert(i);
    while(!nodeset.empty())
    {
        if(currentNode==0)
        {
            //找最小距離的點作為current node
            currentNode = *nodeset.begin();
            for(int node:nodeset)
                if(dist[node]<dist[currentNode])
                    currentNode = node;
        }

        int nextEdge=0;
        for(int edge=heads[currentNode];edge!=-1;edge = nexts[edge])
        {
            int neighbor = tos[edge];
            if(nodeset.find(neighbor)!=nodeset.end()) //Java裡等價的是nodeset.contains(neighbor)
            {
                if (dist[neighbor] > dist[currentNode] + weights[edge])
                {
                    dist[neighbor] = dist[currentNode] + weights[edge];
                    parents[neighbor] = currentNode;
                }
                if (weights[edge] < weights[nextEdge])
                    nextEdge = edge;
            }
        }
        nodeset.erase(currentNode);
        currentNode =tos[nextEdge];
    }
}
//如果看懂了以上版本，以下堆優化版本會容易明白一些
typedef pair<int,int> distAndToPair;//記錄從起始點到to點的距離和to點
priority_queue<distAndToPair,vector<distAndToPair>,greater<>> min_heap;
void dijkstra(int start){
    memset(dist,INF,sizeof(int)*(MAX_NODE_NUM+1));
    dist[start]=0;//初始化所有的節點除了開始節點距離都為INF
    min_heap.push(distAndToPair(0,start));
    while(!min_heap.empty()){
        distAndToPair p = min_heap.top();//取最小距離點
        min_heap.pop();
        int currentNode=p.second;
        if(dist[currentNode]<p.first)//避免重複插入相同節點導緻的問題
            continue;
        for(int edgeIdx=heads[currentNode];edgeIdx!=-1;edgeIdx=edges[edgeIdx].nex)
        {
            Edge& edge=edges[edgeIdx];
            if(edge.weight+dist[currentNode]<dist[edge.to]){
                dist[edge.to]=edge.weight+dist[currentNode];//relaxation
                min_heap.push(distAndToPair(dist[edge.to],edge.to));//有重複插入
            }
        }
    }
}