導航:首頁 > 源碼編譯 > 深度優先遍歷非遞歸演算法

深度優先遍歷非遞歸演算法

發布時間:2023-09-21 03:49:07

『壹』 無向圖的深度優先遍歷怎麼做

#include<stdio.h>
#define n 5
int a[10]={0};
int top=0;//定義堆棧
int main()
{
void dfs(int (*edge)[n],int *status);
int edge[n][n]={{0,0,1,1,0},{0,0,0,0,1},{1,0,0,0,0},{1,0,0,0,1},{0,1,0,1,0}};//臨接矩陣表示的圖
int status[n]={0};//每個點的狀態,有沒有被訪問
int i=0,j=0;
// for(i=0;i<n;i++)
// for(j=0;j<n;j++)
// scanf("%d",&edge[i][j]);
dfs(edge,status);
return 0;
}
void dfs(int (*edge)[n],int *status)//遍歷
{
int k=0,j=0;
while(top>=0)
{
// for(i=0;i<n;i++)
// {
if(status[k]==0)
{
top++;
a[top]=k;
// b[count++]=k;
printf("%d",k);
status[k]=1;
}
while(j<n)
{
// for(j=0;j<n;j++)
if(edge[k][j]==1)
{
if(status[j]==0)
{
top++;
a[top]=j;
// b[count++]=k;
printf("%5d",j);
status[j]=1;
k=j;
j=0;
}
else
j++;
}
else
j++;
}
top-=1;
k=a[top];
j=0;
}
}

這個是非遞歸的,
#include<stdio.h>
#define n 5
int main()
{
void dft(int (*edge)[n],int *status);
int i=0,j=0;
int edge[n][n]={0};
int status[n]={0};
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&edge[i][j]);
dft(edge,status);
return 0;
}
void dft(int (*edge)[n],int *status)
{
void dftcore(int (*edge)[n],int *status,int i);
int i=0;
for(i=0;i<n;i++)
dftcore(edge,status,i);
}
void dftcore(int (*edge)[n],int *status,int i)
{
int j=0;
if(status[i]==1)
return;
printf("%5d",i);
status[i]=1;
for(j=0;j<n;j++)
if(edge[i][j]==1)
dftcore(edge,status,j);
}
這個遞歸的

『貳』 JS 深度優先遍歷(DFS)和廣度優先遍歷(BFS)

深度優先遍歷DFS

自定義:深度單線遊走,從根走完最後一個節點,在遊走兄弟節點,走完兄弟的所有子節點,循環之。

     遞歸演算法

function deepFirstSearch(node, nodeList = []) {

  if (node) {

    nodeList.push(node);

    var children = node.children;

    for (var i = 0; i < children.length; i++)

      //每次遞歸的時候將 需要遍歷的節點 和 節點所存儲的數組傳下去

      deepFirstSearch(children[i], nodeList);

  }

  return nodeList;

}

非遞歸演算法:

function deepFirstSearch(node) {

  var nodes = [];

  if (node != null) {

    var stack = [];

    stack.push(node);

    while (stack.length != 0) {

      var item = stack.pop();

      nodes.push(item);

      var children = item.children;

      for (var i = children.length - 1; i >= 0; i--)

        stack.push(children[i]);

    }

  }

  return nodes;

}

廣度優先遍歷(BFS)

自定義:從根開始 層層推進 走完一層 走下一層 (猶如爬樓,走完一層的樓梯,繼續下一層的樓梯)

遞歸演算法:(容易棧溢出)

function breadthFirstSearch(node) {

  var nodes = [];

  var i = 0;

  if (!(node == null)) {

    nodes.push(node);

    breadthFirstSearch(node.nextElementSibling);

    node = nodes[i++];

    breadthFirstSearch(node.firstElementChild);

  }

  return nodes;

}

非遞歸演算法:(推薦)

function breadthFirstSearch(node) {

  var nodes = [];

  if (node != null) {

    var queue = [];

    queue.unshift(node);

    while (queue.length != 0) {

      var item = queue.shift();

      nodes.push(item);

      var children = item.children;

      for (var i = 0; i < children.length; i++)

        queue.push(children[i]);

    }

  }

  return nodes;

}

『叄』 數據結構 圖的遍歷 1.圖的遍歷的演示 2.實現圖的廣度,深度優先遍歷。<用鄰接表實現> 3.遞歸的方法實現

Status Build_AdjList(ALGraph &G)//輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接表
{
InitALGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //頂點數不能為負
G.vexnum=v;
scanf("%d",&a);
if(a<0) return ERROR; //邊數不能為殲世負
G.arcnum=a;
for(m=0;m<v;m++)
G.vertices[m].data=getchar(); //輸入各頂點的符號
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t為弧尾,h為弧頭
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<氏團肢0) return ERROR; //頂點未找到
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);
q->nextarc=p;
}
p->adjvex=j;p->nextarc=NULL;
}//while
return OK;
}//Build_AdjList
7.15
//本題中的圖G均為有向無權圖,其餘情況容易由此寫出
Status Insert_Vex(MGraph &G, char v)//在鄰接矩陣表示的圖G上插入頂點v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
G.vexs[++G.vexnum]=v;
return OK;
}//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在鄰接矩陣表示的圖G上插入邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(i==j) return ERROR;
if(!G.arcs[i][j].adj)
{
G.arcs[i][j].adj=1;
G.arcnum++;
}
return OK;
}//Insert_Arc
Status Delete_Vex(MGraph &G,char v)//在鄰接矩陣表示的圖G上刪除頂點v
{
n=G.vexnum;
if((m=LocateVex(G,v))<0) return ERROR;
G.vexs[m]<->G.vexs[n]; //將待刪除頂點交換到最後一個頂點
for(i=0;i<n;i++)
{
G.arcs[i][m]=G.arcs[i][n];
G.arcs[m][i]=G.arcs[n][i]; //將邊的關系隨之交換
}
G.arcs[m][m].adj=0;
G.vexnum--;
return OK;
}//Delete_Vex
分析:如果不把待刪除頂點交換到最後或碰一個頂點的話,演算法將會比較復雜,而伴隨著大量元素的移動,時間復雜度也會大大增加.
Status Delete_Arc(MGraph &G,char v,char w)//在鄰接矩陣表示的圖G上刪除邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.arcs[i][j].adj)
{
G.arcs[i][j].adj=0;
G.arcnum--;
}
return OK;
}//Delete_Arc
7.16
//為節省篇幅,本題只給出Insert_Arc演算法.其餘演算法請自行寫出.
Status Insert_Arc(ALGraph &G,char v,char w)//在鄰接表表示的圖G上插入邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;p->nextarc=NULL;
if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)
if(q->adjvex==j) return ERROR; //邊已經存在
q->nextarc=p;
}
G.arcnum++;
return OK;
}//Insert_Arc
7.17
//為節省篇幅,本題只給出較為復雜的Delete_Vex演算法.其餘演算法請自行寫出.
Status Delete_Vex(OLGraph &G,char v)//在十字鏈表表示的圖G上刪除頂點v
{
if((m=LocateVex(G,v))<0) return ERROR;
n=G.vexnum;
for(i=0;i<n;i++) //刪除所有以v為頭的邊
{
if(G.xlist[i].firstin->tailvex==m) //如果待刪除的邊是頭鏈上的第一個結點
{
q=G.xlist[i].firstin;
G.xlist[i].firstin=q->hlink;
free(q);G.arcnum--;
}
else //否則
{
for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink);
if(p)
{
q=p->hlink;
p->hlink=q->hlink;
free(q);G.arcnum--;
}
}//else
}//for
for(i=0;i<n;i++) //刪除所有以v為尾的邊
{
if(G.xlist[i].firstout->headvex==m) //如果待刪除的邊是尾鏈上的第一個結點
{
q=G.xlist[i].firstout;
G.xlist[i].firstout=q->tlink;
free(q);G.arcnum--;
}
else //否則
{
for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink);
if(p)
{
q=p->tlink;
p->tlink=q->tlink;
free(q);G.arcnum--;
}
}//else
}//for
for(i=m;i<n;i++) //順次用結點m之後的頂點取代前一個頂點
{
G.xlist[i]=G.xlist[i+1]; //修改表頭向量
for(p=G.xlist[i].firstin;p;p=p->hlink)
p->headvex--;
for(p=G.xlist[i].firstout;p;p=p->tlink)
p->tailvex--; //修改各鏈中的頂點序號
}
G.vexnum--;
return OK;
}//Delete_Vex
7.18
//為節省篇幅,本題只給出Delete_Arc演算法.其餘演算法請自行寫出.
Status Delete_Arc(AMLGraph &G,char v,char w)////在鄰接多重表表示的圖G上刪除邊(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.adjmulist[i].firstedge->jvex==j)
G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink;
else
{
for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink);
if (!p) return ERROR; //未找到
p->ilink=p->ilink->ilink;
} //在i鏈表中刪除該邊
if(G.adjmulist[j].firstedge->ivex==i)
G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink;
else
{
for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink);
if (!p) return ERROR; //未找到
q=p->jlink;
p->jlink=q->jlink;
free(q);
} //在i鏈表中刪除該邊
G.arcnum--;
return OK;
}//Delete_Arc
7.19
Status Build_AdjMulist(AMLGraph &G)//輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接多重表
{
InitAMLGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //頂點數不能為負
G.vexnum=v;
scanf(%d",&a);
if(a<0) return ERROR; //邊數不能為負
G.arcnum=a;
for(m=0;m<v;m++)
G.adjmulist[m].data=getchar(); //輸入各頂點的符號
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t為弧尾,h為弧頭
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<0) return ERROR; //頂點未找到
p=(EBox*)malloc(sizeof(EBox));
p->ivex=i;p->jvex=j;
p->ilink=NULL;p->jlink=NULL; //邊結點賦初值
if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->ivex==i) q=q->ilink;
else q=q->jlink;
}
if(r->ivex==i) r->ilink=p;//注意i值既可能出現在邊結點的ivex域中,
else r->jlink=p; //又可能出現在邊結點的jvex域中
}//else //插入i鏈表尾部
if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->jvex==j) q=q->jlink;
else q=q->ilnk;
}
if(r->jvex==j) r->jlink=p;
else r->ilink=p;
}//else //插入j鏈表尾部
}//for
return OK;
}//Build_AdjList
7.20
int Pass_MGraph(MGraph G)//判斷一個鄰接矩陣存儲的有向圖是不是可傳遞的,是則返回1,否則返回0
{
for(x=0;x<G.vexnum;x++)
for(y=0;y<G.vexnum;y++)
if(G.arcs[x][y])
{
for(z=0;z<G.vexnum;z++)
if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0;//圖不可傳遞的條件
}//if
return 1;
}//Pass_MGraph
分析:本演算法的時間復雜度大概是O(n^2*d).
7.21
int Pass_ALGraph(ALGraph G)//判斷一個鄰接表存儲的有向圖是不是可傳遞的,是則返回1,否則返回0
{
for(x=0;x<G.vexnum;x++)
for(p=G.vertices[x].firstarc;p;p=p->nextarc)
{
y=p->adjvex;
for(q=G.vertices[y].firstarc;q;q=q->nextarc)
{
z=q->adjvex;
if(z!=x&&!is_adj(G,x,z)) return 0;
}//for
}//for
}//Pass_ALGraph
int is_adj(ALGraph G,int m,int n)//判斷有向圖G中是否存在邊(m,n),是則返回1,否則返回0
{
for(p=G.vertices[m].firstarc;p;p=p->nextarc)
if(p->adjvex==n) return 1;
return 0;
}//is_adj
7.22
int visited[MAXSIZE]; //指示頂點是否在當前路徑上
int exist_path_DFS(ALGraph G,int i,int j)//深度優先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回1,否則返回0
{
if(i==j) return 1; //i就是j
else
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//i下游的頂點到j有路徑
}//for
}//else
}//exist_path_DFS
7.23
int exist_path_BFS(ALGraph G,int i,int j)//廣度優先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回1,否則返回0
{
int visited[MAXSIZE];
InitQueue(Q);
EnQueue(Q,i);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
visited[u]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(k==j) return 1;
if(!visited[k]) EnQueue(Q,k);
}//for
}//while
return 0;
}//exist_path_BFS
7.24
void STraverse_Nonrecursive(Graph G)//非遞歸遍歷強連通圖G
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //將第一個頂點入棧
visit(1);
visited =1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i);
if(j&&!visited[j])
{
visit(j);
visited[j]=1;
Push(S,j); //向左走到盡頭
}
}//while
if(!StackEmpty(S))
{
Pop(S,j);
Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步
if(k&&!visited[k])
{
visit(k);
visited[k]=1;
Push(S,k);
}
}//if
}//while
}//Straverse_Nonrecursive
分析:本演算法的基本思想與二叉樹的先序遍歷非遞歸演算法相同,請參考6.37.由於是強連通圖,所以從第一個結點出發一定能夠訪問到所有結點.
7.25
見書後解答.
7.26
Status TopoNo(ALGraph G)//按照題目要求順序重排有向圖中的頂點
{
int new[MAXSIZE],indegree[MAXSIZE]; //儲存結點的新序號
n=G.vexnum;
FindInDegree(G,indegree);
InitStack(S);
for(i=1;i<G.vexnum;i++)
if(!indegree[i]) Push(S,i); //零入度結點入棧
count=0;
while(!StackEmpty(S))
{
Pop(S,i);
new[i]=n--; //記錄結點的拓撲逆序序號
count++;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!(--indegree[k])) Push(S,k);
}//for
}//while
if(count<G.vexnum) return ERROR; //圖中存在環
for(i=1;i<=n;i++) printf("Old No:%d New No:%d\n",i,new[i])
return OK;
}//TopoNo
分析:只要按拓撲逆序對頂點編號,就可以使鄰接矩陣成為下三角矩陣.
7.27
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判斷鄰接表方式存儲的有向圖G的頂點i到j是否存在長度為k的簡單路徑
{
if(i==j&&k==0) return 1; //找到了一條路徑,且長度符合要求
else if(k>0)
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩餘路徑長度減一
}//for
visited[i]=0; //本題允許曾經被訪問過的結點出現在另一條路徑中
}//else
return 0; //沒找到
}//exist_path_len
7.28
int path[MAXSIZE],visited[MAXSIZE]; //暫存遍歷過程中的路徑
int Find_All_Path(ALGraph G,int u,int v,int k)//求有向圖G中頂點u到v之間的所有簡單路徑,k表示當前路徑長度
{
path[k]=u; //加入當前路徑中
visited[u]=1;
if(u==v) //找到了一條簡單路徑
{
printf("Found one path!\n");
for(i=0;path[i];i++) printf("%d",path[i]); //列印輸出
}
else
for(p=G.vertices[u].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l]) Find_All_Path(G,l,v,k+1); //繼續尋找
}
visited[u]=0;
path[k]=0; //回溯
}//Find_All_Path
main()
{
...
Find_All_Path(G,u,v,0); //在主函數中初次調用,k值應為0
...
}//main
7.29
int GetPathNum_Len(ALGraph G,int i,int j,int len)//求鄰接表方式存儲的有向圖G的頂點i到j之間長度為len的簡單路徑條數
{
if(i==j&&len==0) return 1; //找到了一條路徑,且長度符合要求
else if(len>0)
{
sum=0; //sum表示通過本結點的路徑數
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
sum+=GetPathNum_Len(G,l,j,len-1)//剩餘路徑長度減一
}//for
visited[i]=0; //本題允許曾經被訪問過的結點出現在另一條路徑中
}//else
return sum;
}//GetPathNum_Len
7.30
int visited[MAXSIZE];
int path[MAXSIZE]; //暫存當前路徑
int cycles[MAXSIZE][MAXSIZE]; //儲存發現的迴路所包含的結點
int thiscycle[MAXSIZE]; //儲存當前發現的一個迴路
int cycount=0; //已發現的迴路個數
void GetAllCycle(ALGraph G)//求有向圖中所有的簡單迴路
{
for(v=0;v<G.vexnum;v++) visited[v]=0;
for(v=0;v<G.vexnum;v++)
if(!visited[v]) DFS(G,v,0); //深度優先遍歷
}//DFSTraverse
void DFS(ALGraph G,int v,int k)//k表示當前結點在路徑上的序號
{
visited[v]=1;
path[k]=v; //記錄當前路徑
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!visited[w]) DFS(G,w,k+1);
else //發現了一條迴路
{
for(i=0;path[i]!=w;i++); //找到迴路的起點
for(j=0;path[i+j];i++) thiscycle[j]=path[i+j];//把迴路復制下來
if(!exist_cycle()) cycles[cycount++]=thiscycle;//如果該迴路尚未被記錄過,就添加到記錄中
for(i=0;i<G.vexnum;i++) thiscycle[i]=0; //清空目前迴路數組
}//else
}//for
path[k]=0;
visited[k]=0; //注意只有當前路徑上的結點visited為真.因此一旦遍歷中發現當前結點visited為真,即表示發現了一條迴路
}//DFS
int exist_cycle()//判斷thiscycle數組中記錄的迴路在cycles的記錄中是否已經存在
{
int temp[MAXSIZE];
for(i=0;i<cycount;i++) //判斷已有的迴路與thiscycle是否相同
{ //也就是,所有結點和它們的順序都相同
j=0;c=thiscycle�; //例如,142857和857142是相同的迴路
for(k=0;cycles[i][k]!=c&&cycles[i][k]!=0;k++);//在cycles的一個行向量中尋找等於thiscycle第一個結點的元素
if(cycles[i][k]) //有與之相同的一個元素
{
for(m=0;cycles[i][k+m];m++)
temp[m]=cycles[i][k+m];
for(n=0;n<k;n++,m++)
temp[m]=cycles[i][n]; //調整cycles中的當前記錄的循環相位並放入temp數組中
if(!StrCompare(temp,thiscycle)) //與thiscycle比較
return 1; //完全相等
for(m=0;m<G.vexnum;m++) temp[m]=0; //清空這個數組
}
}//for
return 0; //所有現存迴路都不與thiscycle完全相等
}//exist_cycle
分析:這個演算法的思想是,在遍歷中暫存當前路徑,當遇到一個結點已經在路徑之中時就表明存在一條迴路;掃描路徑向量path可以獲得這條迴路上的所有結點.把結點序列(例如,142857)存入thiscycle中;由於這種演算法中,一條迴路會被發現好幾次,所以必須先判斷該迴路是否已經在cycles中被記錄過,如果沒有才能存入cycles的一個行向量中.把cycles的每一個行向量取出來與之比較.由於一條迴路可能有多種存儲順序,比如142857等同於285714和571428,所以還要調整行向量的次序,並存入temp數組,例如,thiscycle為142857第一個結點為1,cycles的當前向量為857142,則找到後者中的1,把1後部分提到1前部分前面,最終在temp中得到142857,與thiscycle比較,發現相同,因此142857和857142是同一條迴路,不予存儲.這個演算法太復雜,很難保證細節的准確性,大家理解思路便可.希望有人給出更加簡捷的演算法.
7.31
int visited[MAXSIZE];
int finished[MAXSIZE];
int count; //count在第一次深度優先遍歷中用於指示finished數組的填充位置
void Get_SGraph(OLGraph G)//求十字鏈表結構儲存的有向圖G的強連通分量
{
count=0;
for(v=0;v<G.vexnum;v++) visited[v]=0;
for(v=0;v<G.vexnum;v++) //第一次深度優先遍歷建立finished數組
if(!visited[v]) DFS1(G,v);
for(v=0;v<G.vexnum;v++) visited[v]=0; //清空visited數組
for(i=G.vexnum-1;i>=0;i--) //第二次逆向的深度優先遍歷
{
v=finished(i);
if(!visited[v])
{
printf("\n"); //不同的強連通分量在不同的行輸出
DFS2(G,v);
}
}//for
}//Get_SGraph
void DFS1(OLGraph G,int v)//第一次深度優先遍歷的演算法
{
visited[v]=1;
for(p=G.xlist[v].firstout;p;p=p->tlink)
{
w=p->headvex;
if(!visited[w]) DFS1(G,w);
}//for
finished[++count]=v; //在第一次遍歷中建立finished數組
}//DFS1
void DFS2(OLGraph G,int v)//第二次逆向的深度優先遍歷的演算法
{
visited[v]=1;
printf("%d",v); //在第二次遍歷中輸出結點序號
for(p=G.xlist[v].firstin;p;p=p->hlink)
{
w=p->tailvex;
if(!visited[w]) DFS2(G,w);
}//for
}//DFS2
分析:求有向圖的強連通分量的演算法的時間復雜度和深度優先遍歷相同,也為O(n+e).
7.32
void Forest_Prim(ALGraph G,int k,CSTree &T)//從頂點k出發,構造鄰接表結構的有向圖G的最小生成森林T,用孩子兄弟鏈表存儲
{
for(j=0;j<G.vexnum;j++) //以下在Prim演算法基礎上稍作改動
if(j!=k)
{
closedge[j]={k,Max_int};
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
if(p->adjvex==k) closedge[j].lowcost=p->cost;
}//if
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=minimum(closedge);
if(closedge[k].lowcost<Max_int)
{
Addto_Forest(T,closedge[k].adjvex,k); //把這條邊加入生成森林中
closedge[k].lowcost=0;
for(p=G.vertices[k].firstarc;p;p=p->nextarc)
if(p->cost<closedge[p->adjvex].lowcost)
closedge[p->adjvex]={k,p->cost};
}//if
else Forest_Prim(G,k); //對另外一個連通分量執行演算法
}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把邊(i,j)添加到孩子兄弟鏈表表示的樹T中
{
p=Locate(T,i); //找到結點i對應的指針p,過程略
q=(CSTNode*)malloc(sizeof(CSTNode));
q->data=j;
if(!p) //起始頂點不屬於森林中已有的任何一棵樹
{
p=(CSTNode*)malloc(sizeof(CSTNode));
p->data=i;
for(r=T;r->nextsib;r=r->nextsib);
r->nextsib=p;
p->firstchild=q;
} //作為新樹插入到最右側
else if(!p->firstchild) //雙親還沒有孩子
p->firstchild=q; //作為雙親的第一個孩子
else //雙親已經有了孩子
{
for(r=p->firstchild;r->nextsib;r=r->nextsib);
r->nextsib=q; //作為雙親最後一個孩子的兄弟
}
}//Addto_Forest
main()
{
...
T=(CSTNode*)malloc(sizeof(CSTNode)); //建立樹根
T->data=1;
Forest_Prim(G,1,T);
...
}//main
分析:這個演算法是在Prim演算法的基礎上添加了非連通圖支持和孩子兄弟鏈表構建模塊而得到的,其時間復雜度為O(n^2).
7.33
typedef struct {
int vex; //結點序號
int ecno; //結點所屬的連通分量號
} VexInfo;
VexInfo vexs[MAXSIZE]; //記錄結點所屬連通分量號的數組
void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化
{
for(i=0;i<vexnum;i++)
vexs[i]={i,i}; //初始狀態:每一個結點都屬於不同的連通分量
}//Init_VexInfo
int is_ec(VexInfo vexs[ ],int i,int j)//判斷頂點i和頂點j是否屬於同一個連通分量
{
if(vexs[i].ecno==vexs[j].ecno) return 1;

『肆』 對圖採用深度優先搜索,採用的數據結構是: 。

廣度優先用隊列,深度優先用棧。把圖的深度優先搜索遍歷過程中所經歷的邊保留,其餘的彼岸進行刪除,生成的樹為深度優先樹。

深度優先搜索法有遞歸以及非遞歸兩種設計方法。一般當搜索深度較小、問題遞歸方式比較明顯時,用遞歸方法設計好,可以使得程序結構更簡捷易懂。當搜索深度較大時,當數據量較大時,由於系統堆棧容量的限制,遞歸容易產生溢出,用非遞歸方法設計比較好。

(4)深度優先遍歷非遞歸演算法擴展閱讀:

注意事項:

在深度優先搜索中,演算法表現得好像要盡快地遠離起始點似的。相反在廣度優先搜索中,演算法好像要盡可能地靠近起始點,首先訪問起始頂點的所有鄰接點,然後再訪問較遠的區域,是用隊列來實現的。

訪問下一個未來訪問的鄰接點,這個頂點必須是當前頂點的鄰接點,標記它,並把它插入到隊列中,如果因為已經沒有未訪問頂點而不能執行規則1時,那麼從隊列頭取一個頂點,並使其成為當前頂點。

『伍』 無向有權的圖的深度、廣度優先遍歷怎麼做的啊,他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1) 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧,廣度優先遍歷的非遞歸的通用做法是採用隊列。

2) 深度優先遍歷:對每一個可能的分支路徑深入到不能再深入為止,而且每個結點只能訪問一次。要特別注意的是,二叉樹的深度優先遍歷比較特殊,可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下:

先序遍歷:對任一子樹,先訪問根,然後遍歷其左子樹,最後遍歷其右子樹。
中序遍歷:對任一子樹,先遍歷其左子樹,然後訪問根,最後遍歷其右子樹。
後序遍歷:對任一子樹,先遍歷其左子樹,然後遍歷其右子樹,最後訪問根。
廣度優先遍歷:又叫層次遍歷,從上往下對每一層依次訪問,在每一層中,從左往右(也可以從右往左)訪問結點,訪問完一層就進入下一層,直到沒有結點可以訪問為止。

3)深度優先搜素演算法:不全部保留結點,佔用空間少;有回溯操作(即有入棧、出棧操作),運行速度慢。

廣度優先搜索演算法:保留全部結點,佔用空間大; 無回溯操作(即無入棧、出棧操作),運行速度快。

閱讀全文

與深度優先遍歷非遞歸演算法相關的資料

熱點內容
shell編譯成功後退出 瀏覽:721
你們用什麼美妝鑒別的app嗎 瀏覽:117
手機設備信息在哪個文件夾 瀏覽:977
安卓應用亂怎麼解決 瀏覽:261
windowssocket網路編程 瀏覽:731
什麼伺服器永遠不關網 瀏覽:592
程序員展銷會 瀏覽:15
天津銳志單片機 瀏覽:149
bestfit演算法 瀏覽:16
通達信能自己編程嗎 瀏覽:768
powlinux 瀏覽:921
什麼app手機鈴音免費 瀏覽:400
玩不壞的解壓器怎麼折 瀏覽:435
文件解壓驗證失敗 瀏覽:453
vivo演算法sp薪資 瀏覽:79
撥號服務是什麼app 瀏覽:429
華為有自己的編譯器 瀏覽:211
程序員退出自媒體 瀏覽:314
電腦加密圖片怎麼顯示沒有預覽 瀏覽:575
印刷加密穩定幣 瀏覽:526