吐的演算法

『壹』 圖的矩陣深度和廣度遍歷演算法

圖的遍歷是指從圖中任一給定頂點出發，依次訪問圖中的其餘頂點。如果給定的圖是連通圖，則從圖中的任意一點出發，按照一個指定的順序就可以訪問到圖中的所有頂點，且每個頂點只訪問一次。這個過程稱為圖的遍歷。
圖的遍歷比樹的遍歷復雜的多。樹是一種特殊類型的圖，即無圈（無迴路）連通圖。樹中的任意兩個頂點間都有唯一的路徑相通。在一個頂點被訪問過之後，不可能又沿著另外一條路徑訪問到已被訪問過的結點。而圖中的頂點可能有邊與其他任意頂點相連
。因此在訪問了某個頂點之後，可能沿著另一條邊訪問已被訪問過的頂點。例如圖（a）中的G1，在訪問了V1，V2和V3之後，有可能沿著邊（V3，V1）訪問到V1。為了避免一頂點被多次訪問，可以設立一個集合Visited，用來記錄已被訪問過的頂點。它的初值為空
集。一旦V1被訪問過，即把V1加到集合Visited中。圖的遍厲通常有兩種:圖的深度優先
搜索和圖的廣度優先搜索。
1）圖的深度優先搜索
從圖G=（V，E）的一個頂點V0出發，在訪問了任意一個與V0相鄰且未被訪問過的頂點W1之後，再從W1出發，訪問和W1相鄰且未被訪問過的頂點W2，然後再從W2出發進行如上所述訪問，直到找到一個它相鄰的結點，都被訪問過的結點為止。然後退回到尚有相
鄰結點未被訪問過的頂點，再從該頂點出發，重復上述搜索過程，直到所有被訪問過的頂點的鄰接點都被訪問過為止。圖的這種遍歷過程就稱為圖的深度優先搜索。例如從頂點V1出發對圖3.3.5進行深度優先搜索，遍歷的順序為 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（與鄰接表中的鄰接點排列順序有關，即p->next.vertex=v2 or v3對遍歷
順序有影響 ）
例25.(p194.c)圖的深度優先搜索。從圖G的頂點V0
發進行深度優先搜索，列印出各個頂點的遍歷順序。
解：圖的深度優先搜索法為：
（1）首先訪問V0並把V0加到集合visited中；
（2）找到與V0相鄰的頂點W，若W未進入
visited中，則以深度優先方法從W開始搜索。
（3）重復過程（2）直到所有於V0相鄰的頂點
都被訪問過為止。

下面是對用鄰接表表示的圖G進行深度優先搜索的程序
int rear=0; /*Visit和rear都為全局變數*/
int visit[500];
depth_first_search(g,v0) /*從V0開始對圖G進行深度
優先搜索*/
graphptr g[ ]; /*指針數組,為鄰接表表頭頂點指針
g[vi]...g[vn]*/
int v0; /*這里V0和W都是頂點標號,如V0=0或1*/
{ /*g[v0]是頂點V0的表頭指針*/
int w;
graphptr p; /*鏈表的結點指針*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一個頂點，通過鄰接表表頭指針
，訪問v0的鄰接頂點*/
while (p!=NULL)
{
w=p->vertex ;/*這里W是與V0相鄰的一個頂點*/
if (!visited(w))/*當V0的相鄰結點，W未被訪問時，從W開始遍厲*/
depth_first_search(g,w);
p=p->next;/*接著訪問另一個相鄰頂點*/
}
}
int visited(w) /*檢查頂點w是否進入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，說明被訪問過*/
return(0); /*W不在visit[]中，說明未被訪問過，返回0*/
}
2）圖的廣度優先搜索
從圖G的一個頂點V0出發，依次訪問V0的鄰接點K1,K2...Kn。然後再順序訪問K1,K2...Kn的所有尚未被訪問過的鄰接點。如此重復，直到圖中的頂點都被訪問過為止。圖的這種搜索稱為圖的廣度優先搜索。例如：從V1出發按廣度優先搜索方法遍歷圖3.3.5,頂
點的訪問順序為V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
圖的廣度優先搜索類似樹的按層次遍歷，需要有一個隊列來存放還沒
有來得及處理的頂點。圖的廣度優先搜索演算法為：
（1）首先把V0放入隊列；
（2）若隊列為空則結束，否則取出隊列的頭V；
（3）訪問V並把所有與V相鄰且未被訪問的頂點插入隊列；
（4）重復（2）-（3）直到隊列為空。
上述演算法中所有已被訪問過的頂點都放在隊列中，因此只要檢查某個頂點是否在隊列中就可以判斷出該頂點是否已被訪問過。
廣度搜索法的程序如下：
broad_first_search(g,v0) /*從V0開始對圖g進行廣度優先搜索*/
graphptr g[ ]; /*為鄰接表，表頭頂點指針*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入隊列queue*/
while (front <=tail)/*當隊列不為空*/
{
v=queue[front++]; /*取出隊列中的頂點*/
printf("%d\n",v); /*訪問該頂點*/
p=g[v]; /*從頂點V的鏈表來考慮與V相鄰的頂點*/
while (p!=NULL)
{
v=p->vertex; /*從第一個結點（即邊）中找出相鄰的頂點*/
if (!visited(queue,tail,v))/*判斷頂點是否進入隊列，如進入隊列
說明已被訪問或將要訪問*/
queue[++tail]=v;/*如果該頂點未被訪問過，將此相鄰頂點插入隊列*/
p=p-->next;/*再考慮該結點的下一個相鄰頂點*/
}
}
}
visited (q,tail,v)/*判斷頂點是否被訪問過，訪問過時，返回1，否則返回0*/
int q[ ],tail,v;/*進入隊列的頂點，在front之前的頂點已被訪問過列印輸出，
在front和tail之間的頂點是即將要訪問頂點*/
{
int i;
for(i=1;i<=tail;i++)/*掃描隊列，確定v是否在隊列中，在隊列中返回1，否則返回0*
/
if (q[i]==v)return(1);/*隊列中的頂點都認為已被訪問過*/
return(0);
}

深度優先的非遞歸演算法

/*設當前圖(或圖的某個連通分枝)的起始訪問點為p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//將當前點的鄰接點中的所有結點壓入副棧中
if(v.marked==false)
statckSec.push(v)
//將副棧中的點依次彈出，壓入主棧中，這與非遞歸演算法中使用隊列的意圖類似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一個未訪問的結點或者沒找到，直到棧為空
{
if(!stackMain.isEmpty())

{
p=stackMain.pop();

}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//訪問未訪問結點.

{

visit(p);

p.marked=true;

}

}while(!stackMain.isEmpty())

『貳』 圖像分割演算法總結

       圖像處理的很多任務都離不開圖像分割。因為圖像分割在cv中實在太重要(有用)了，就先把圖像分割的常用演算法做個總結。

        接觸機器學習和深度學習時間已經不短了。期間看過各種相關知識但從未總結過。本文過後我會盡可能詳細的從工程角度來總結，從傳統機器學習演算法，傳統計算機視覺庫演算法到深度學習目前常用演算法和論文，以及模型在各平台的轉化，量化，服務化部署等相關知識總結。

        圖像分割常用演算法大致分為下面幾類。由於圖像的能量范函，邊緣追蹤等方法的效果往往只能解決特定問題，效果並不理想，這里不再闡述。當然二值化本身也可以分割一些簡單圖像的。但是二值化演算法較多，我會專門做一個文章來總結。這里不再贅述。

        1.基於邊緣的圖像分割演算法：

            有利用圖像梯度的傳統演算法運算元的sobel，roberts，prewitt,拉普拉斯以及canny等。

            這些演算法的基本思想都是採用合適的卷積運算元，對圖像做卷積。從而求出圖像對應的梯度圖像。(至於為什麼通過如圖1這樣的運算元卷積，即可得到圖像的梯度圖像，請讀者復習下卷積和倒數的概念自行推導)由於圖像的邊緣處往往是圖像像素差異較大，梯度較大地方。因此我們通過合適的卷積核得到圖像的梯度圖像，即得到了圖像的邊緣圖像。至於二階運算元的推導，與一階類似。優點：傳統運算元梯度檢測，只需要用合適的卷積核做卷積，即可快速得出對應的邊緣圖像。缺點：圖像邊緣不一定準確，復雜圖像的梯度不僅僅出現在圖像邊緣，可以能出現在圖像內部的色彩和紋理上。

             也有基於深度學習方法hed，rcf等。由於這類網路都有同一個比較嚴重的缺陷，這里只舉例hed網路。hed是基於FCN和VGG改進，同時引出6個loss進行優化訓練，通過多個層輸出不同scale的粒度的邊緣，然後通過一個訓練權重融合各個層的邊緣結果。hed網路結構如下：

可以得到一個比較完整的梯度圖像，可參考github的hed實現。優點：圖像的梯度細節和邊緣完整性，相比傳統的邊緣運算元要好很多。但是hed對於邊緣的圖像內部的邊緣並不能很好的區分。當然我們可以自行更改loss來嘗試只擬合外部的圖像邊緣。但最致命的問題在於，基於vgg的hed的網路表達能力有限，對於圖像和背景接近，或者圖像和背景部分相融的圖片，hed似乎就有點無能為力了。

        2.基於區域分割的演算法：

            區域分割比較常用的如傳統的演算法結合遺傳演算法，區域生長演算法，區域分裂合並，分水嶺演算法等。這里傳統演算法的思路是比較簡單易懂的，如果有無法理解的地方，歡迎大家一起討論學習。這里不再做過多的分析。

            基於區域和語意的深度學習分割演算法，是目前圖像分割成果較多和研究的主要方向。例如FCN系列的全卷積網路，以及經典的醫學圖像分割常用的unet系列，以及rcnn系列發展下的maskrcnn，以及18年底的PAnet。基於語意的圖像分割技術，無疑會成為圖像分割技術的主流。

            其中，基於深度學習語意的其他相關演算法也可以間接或直接的應用到圖像分割。如經典的圖像matting問題。18年又出現了許多非常優秀的演算法和論文。如Deep-Image-Matting，以及效果非常優秀的MIT的 semantic soft segmentation(sss).

            基於語意的圖像分割效果明顯要好於其他的傳統演算法。我在解決圖像分割的問題時，首先嘗試用了hed網路。最後的效果並不理想。雖然也參考github，做了hed的一些fine-tune,但是還是上面提到的原因，在我多次嘗試後，最終放棄。轉而適用FCN系列的網路。但是fcn也無法解決圖像和背景相融的問題。圖片相融的分割，感覺即需要大的感受野，又需要未相融部分原圖像細節，所以單原FCN的網路，很難做出准確的分割。中間還測試過很多其他相關的網路，但都效果不佳。考慮到感受野和原圖像細節，嘗試了resnet和densenet作為圖像特徵提取的底層。最終我測試了unet系列的網路：

                unet的原始模型如圖所示。在自己拍照爬蟲等手段採集了將近1000張圖片。去掉了圖片質量太差的，圖片內容太過類似的。爬蟲最終收集160多張，自己拍照收集200張圖片後，又用ps手動p了邊緣圖像，採用圖像增強變換，大約有300*24張圖片。原生unet網路的表現比較一般。在將unet普通的卷積層改為resnet後，網路的表達能力明顯提升。在將resnet改為resnet101，此時，即使對於部分相融的圖像，也能較好的分割了。但是unet的模型體積已經不能接受。

                在最後階段，看到maskrcnn的實例分割。maskrcnn一路由rcnn,fasterrcnn發展過來。於是用maskrcnn來加入自己的訓練數據和label圖像進行訓練。maskrcnn的結果表現並不令人滿意，對於邊緣的定位，相比於其他演算法，略顯粗糙。在產品應用中，明顯還不合適。                

        3.基於圖的分割演算法

            基於深度學習的deepgrab,效果表現並不是十分理想。deepgrab的git作者backbone採用了deeplabv2的網路結構。並沒有完全安裝原論文來做。

論文原地址參考： https://arxiv.org/pdf/1707.00243.pdf

整體結構類似於encode和decoder。並沒有太仔細的研究，因為基於resent101的結構，在模型體積，速度以及deeplab的分割精度上，都不能滿足當前的需求。之前大致總結過計算機視覺的相關知識點，既然目前在討論移動端模型，那後面就分模塊總結下移動端模型的應用落地吧。

由於時間實在有限。這里並沒有針對每個演算法進行詳細的講解。後續我會從基礎的機器學習演算法開始總結。

『叄』 用C語言編程實現圖的遍歷演算法

圖的遍歷是指按某條搜索路徑訪問圖中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。圖的遍歷有深度遍歷演算法和廣度遍歷演算法，最近阿傑做了關於圖的遍歷的演算法，下面是圖的遍歷深度優先的演算法（C語言程序）：
#include<stdio.h>
#include<malloc.h>
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0
typedef struct node
{
int adjvex;
struct node *next;
}JD;
typedef struct EdgeNode
{
int vexdata;
JD *firstarc;
}TD;
typedef struct
{
TD ag[m];
int n;
}ALGRAPH;
void DFS(ALGRAPH *G,int i)
{
JD *p;
int visited[80];
printf("visit vertex:%d->",G->ag[i].vexdata);
visited[i]=1;
p=G->ag[i].firstarc;
while(p)
{
if (!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void creat(ALGRAPH *G)
{
int i,m1,j;
JD *p,*p1;
printf("please input the number of graph\n");
scanf("%d",&G->n);
for(i=0;i<G->n;i++)
{
printf("please input the info of node %d",i);
scanf("%d",&G->ag[i].vexdata);
printf("please input the number of arcs which adj to %d",i);
scanf("%d",&m1);
printf("please input the adjvex position of the first arc\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
G->ag[i].firstarc=p;
p1=p;
for(j=2 ;j<=m1;j++)
{
printf("please input the position of the next arc vexdata\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
p1->next=p;
p1=p;
}
}
}
int visited[MaxVertexNum];
void DFSTraverse(ALGRAPH *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=0;
for(i=0;i<G->n;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf("下面以臨接表存儲一個圖；\n");
creat(G);
printf("下面以深度優先遍歷該圖 \n");
DFSTraverse(G);
getchar();
}

『肆』 在圖像處理中有哪些演算法

1、圖像變換：

由於圖像陣列很大，直接在空間域中進行處理，涉及計算量很大。採用各種圖像變換的方法，如傅立葉變換、沃爾什變換、離散餘弦變換等間接處理技術，將空間域的處理轉換為變換域處理，可減少計算量，獲得更有效的處理。它在圖像處理中也有著廣泛而有效的應用。

2、圖像編碼壓縮：

圖像編碼壓縮技術可減少描述圖像的數據量，以便節省圖像傳輸、處理時間和減少所佔用的存儲器容量。

壓縮可以在不失真的前提下獲得，也可以在允許的失真條件下進行。

編碼是壓縮技術中最重要的方法，它在圖像處理技術中是發展最早且比較成熟的技術。

3、圖像增強和復原：

圖像增強和復原的目的是為了提高圖像的質量，如去除雜訊，提高圖像的清晰度等。

圖像增強不考慮圖像降質的原因，突出圖像中所感興趣的部分。如強化圖像高頻分量，可使圖像中物體輪廓清晰，細節明顯；如強化低頻分量可減少圖像中雜訊影響。

4、圖像分割：

圖像分割是數字圖像處理中的關鍵技術之一。

圖像分割是將圖像中有意義的特徵部分提取出來，其有意義的特徵有圖像中的邊緣、區域等，這是進一步進行圖像識別、分析和理解的基礎。

5、圖像描述：

圖像描述是圖像識別和理解的必要前提。

一般圖像的描述方法採用二維形狀描述，它有邊界描述和區域描述兩類方法。對於特殊的紋理圖像可採用二維紋理特徵描述。

6、圖像分類：

圖像分類屬於模式識別的范疇，其主要內容是圖像經過某些預處理（增強、復原、壓縮）後，進行圖像分割和特徵提取，從而進行判決分類。

圖像分類常採用經典的模式識別方法，有統計模式分類和句法模式分類。

(4)吐的演算法擴展閱讀：

圖像處理主要應用在攝影及印刷、衛星圖像處理、醫學圖像處理、面孔識別、特徵識別、顯微圖像處理和汽車障礙識別等。

數字圖像處理技術源於20世紀20年代，當時通過海底電纜從英國倫敦到美國紐約傳輸了一幅照片，採用了數字壓縮技術。

數字圖像處理技術可以幫助人們更客觀、准確地認識世界，人的視覺系統可以幫助人類從外界獲取3/4以上的信息，而圖像、圖形又是所有視覺信息的載體，盡管人眼的鑒別力很高，可以識別上千種顏色，

但很多情況下，圖像對於人眼來說是模糊的甚至是不可見的，通過圖象增強技術，可以使模糊甚至不可見的圖像變得清晰明亮。

『伍』 數據結構中圖的建立及演算法實現

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 20
struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
};
struct Vnode
{
int data;
struct ArcNode *firstarc;
};
struct Vnode AdjList[MaxSize];
int m,n,v,cord;
void main()
{
void creatgraph(struct Vnode A[MaxSize]);
void dfs(struct Vnode A[MaxSize]);
do
{
printf("\n 主菜單");
printf("\n 1 建立無向圖的鄰接表");
printf("\n 2 按深度遍歷圖");
printf("\n 3 結束程序運行");
printf("\n-----------------------------------");
printf("\n 請輸入您的選擇 1, 2, 3 -->");
scanf("%d",&cord);
switch(cord)
{
case 1:
creatgraph(AdjList);
break;
case 2:
dfs(AdjList);
break;
case 3:
exit(0);
}
}while(cord<=3);
}//main end
void creatgraph(struct Vnode A[MaxSize])
{
int i,j,k;
struct ArcNode *p;
printf("input arces and vexes:");
scanf("%d %d",&m,&n);
for(k=0;k<n;k++)
{
printf("\ninput arc:");
scanf("%d%d",&i,&j);
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=j;
p->nextarc=A[i-1].firstarc;
A[i-1].firstarc=p;
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=i;
p->nextarc=A[j-1].firstarc;
A[j-1].firstarc=p;
}
printf("\n");
for(k=0;k<n;k++)
{
printf("%d",A[k].data);
p=A[k].firstarc;
while(p)
{
printf("%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}///creatgraph end
void dfs(struct Vnode A[MaxSize])
{
struct ArcNode *p,*ar[MaxSize];
int x,i,y,top=-1;
int visited[MaxSize];
for(i=0;i<n;i++)
visited[i]=0;
printf("\ninput x:");
scanf("%d",&x);
printf("%d",x);
visited[x-1]=1;
p=A[x-1].firstarc;
while((p)||(top>=0))
{
if(!p)
{
p=ar[top];
top--;
}
y=p->adjvex;
if(visited[y-1]==0)
{
visited[y-1]=1;
printf("->%d",y);
p=p->nextarc;
if(p)
{
top++;
ar[top]=p;
}
p=A[y-1].firstarc;
}
else p=p->nextarc;
}
}

『陸』 圖的廣度、深度優先搜索和拓撲排序

廣度優先搜索是最簡單的圖搜索演算法之一。之所以得名是因為該演算法始終將已經發現的結點集合，沿著其 廣度方向 向外擴展去尋找未發現結點。
具體演算法執行過程如下圖所示：

深度優先搜索，只有可能就在圖中盡可能的 深入 ，總是從最近才發現的結點出發，尋找下一個結點。
具體演算法執行過程如下圖所示：

拓撲排序是計算機中經常遇到的概念，下面用於《演算法導論》的定義

如下圖3-1所示，事件E1完成之後，可以同時執行事件E2和E3，兩事件執行結束之後，執行事件E4，最後可以同時執行事件E5和E6。每個事件的執行都依賴於它之前事件是否執余槐陪行完成，執行的順序是固定的，這樣的線性順序就是 拓撲排序 。

圖的廣度、深度優先搜索和拓撲排序是圖論演算法中的基礎，也是實踐中經常遇到的問題。在考研和面試筆試中會通過選擇題或者填空題考察，學習理解上文圖示中的演算法思想，輔助練習問題不大。當然也有關於這里的演算法題，例如LeetCode815公交路線問題，就是利用圖的廣度優先搜索求解，因豎蠢為解題復雜，並且在平時的應試中出現概率不大，這里不做詳細講解。有興趣的可明段以在LeetCode中搜索，題目後面有我提交過的題解。

『柒』 有向圖的演算法

樓上的真是，估計沒明白樓主意思吧。。。明顯可以證明這個圖是完全強連通的，這個也不難看出來。
但是這個問題本身比較怪異，開始懷疑是不是 NP。

初步感覺，應該歸約成某種網路流吧。。

我再想想吧。。想到了再貼上來吧，樓主放這么重本，不想出來也不好意思收啊。。