轉自大佬博客https://blog.csdn.net/ACdreamers/article/details/16902023
我們首先來看一下什么是前向星.
?
前向星是一種特殊的邊集數組,我們把邊集數組中的每一條邊按照起點從小到大排序,如果起點相同就按照終點從小到大排序,
并記錄下以某個點為起點的所有邊在數組中的起始位置和存儲長度,那么前向星就構造好了.
?
用len[i]來記錄所有以i為起點的邊在數組中的存儲長度.
用head[i]記錄以i為邊集在數組中的第一個存儲位置.
?
那么對于下圖:
?
?
?
我們輸入邊的順序為:
?
1 2
2 3
3 4
1 3
4 1
1 5
4 5
?
那么排完序后就得到:
?
編號: ? ? 1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?5 ? ? ?6 ? ? ?7
起點u: ? ?1 ? ? ?1 ? ? ?1 ? ? ?2 ? ? ?3 ? ? ?4 ? ? ?4
終點v: ? ?2 ? ? ?3 ? ? ?5 ? ? ?3 ? ? ?4 ? ? ?1 ? ? ?5
?
得到:
?
head[1] = 1 ? ?len[1] = 3
head[2] = 4 ? ?len[2] = 1
head[3] = 5 ? ?len[3] = 1
head[4] = 6 ? ?len[4] = 2
?
但是利用前向星會有排序操作,如果用快排時間至少為O(nlog(n))
?
?
如果用鏈式前向星,就可以避免排序.
?
我們建立邊結構體為:
?
struct Edge
{
? ? ?int next;
? ? ?int to;
? ? ?int w;
};
?
其中edge[i].to表示第i條邊的終點,edge[i].next表示與第i條邊同起點的下一條邊的存儲位置,edge[i].w為邊權值.
?
另外還有一個數組head[],它是用來表示以i為起點的第一條邊存儲的位置,實際上你會發現這里的第一條邊存儲的位置其實
在以i為起點的所有邊的最后輸入的那個編號.
?
head[]數組一般初始化為-1,對于加邊的add函數是這樣的:
1 void add(int u,int v,int w) 2 { 3 edge[cnt].w = w; 4 edge[cnt].to = v; 5 edge[cnt].next = head[u]; 6 head[u] = cnt++; 7 } 8
初始化cnt = 0,這樣,現在我們還是按照上面的圖和輸入來模擬一下:
?
?
edge[0].to = 2; ? ? edge[0].next = -1; ? ? ?head[1] = 0;
edge[1].to = 3; ? ? edge[1].next = -1; ? ? ?head[2] = 1;
edge[2].to = 4; ? ? edge[2],next = -1; ? ? ?head[3] = 2;
edge[3].to = 3; ? ? edge[3].next = 0; ? ? ? head[1] = 3;
edge[4].to = 1; ? ? edge[4].next = -1; ? ? ?head[4] = 4;
edge[5].to = 5; ? ? edge[5].next = 3; ? ? ? head[1] = 5;
edge[6].to = 5; ? ? edge[6].next = 4; ? ? ? head[4] = 6;
?
很明顯,head[i]保存的是以i為起點的所有邊中編號最大的那個,而把這個當作頂點i的第一條起始邊的位置.
?
這樣在遍歷時是倒著遍歷的,也就是說與輸入順序是相反的,不過這樣不影響結果的正確性.
比如以上圖為例,以節點1為起點的邊有3條,它們的編號分別是0,3,5 ? 而head[1] = 5
?
我們在遍歷以u節點為起始位置的所有邊的時候是這樣的:
?
for(int i=head[u];~i;i=edge[i].next)
?
那么就是說先遍歷編號為5的邊,也就是head[1],然后就是edge[5].next,也就是編號3的邊,然后繼續edge[3].next,也
就是編號0的邊,可以看出是逆序的.
?
![javascript --- [FormData的使用] 表單元素轉換成表單 對象二進制文件上傳](http://pic.xiahunao.cn/javascript --- [FormData的使用] 表單元素轉換成表單 對象二進制文件上傳)
![javascript --- [FormData的使用] 文件上傳進度條展示 文件上傳圖片即使預覽](http://pic.xiahunao.cn/javascript --- [FormData的使用] 文件上傳進度條展示 文件上傳圖片即使預覽)
![javascript --- [jsonp] script標簽的妙用(繞過同源限制)](http://pic.xiahunao.cn/javascript --- [jsonp] script標簽的妙用(繞過同源限制))
