哪些演算法可遍歷網路圖

① 二叉樹遍歷

遍歷概念

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。
遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。

遍歷方案

1．遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，
（2）遍歷該結點的左子樹(L)，
（3）遍歷該結點的右子樹(R)。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。

2．三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。

遍歷演算法

1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。

2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。

3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。

4．中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder

遍歷序列

1．遍歷二叉樹的執行蹤跡
三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。
具體線路為：
從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。

2．遍歷序列
（1） 中序序列
中序遍歷二叉樹時，對結點的訪問次序為中序序列
【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為：
D B A E C F
（2） 先序序列
先序遍歷二叉樹時，對結點的訪問次序為先序序列
【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為：
A B D C E F
（3） 後序序列
後序遍歷二叉樹時，對結點的訪問次序為後序序列
【例】後序遍歷上圖所示的二叉樹時，得到的後序序列為：
D B E F C A
注意：
（1） 在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次(或第三次)經過結點時進行的，則是中序遍歷(或後序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
（2） 上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前趨結點和一個後繼結點。為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念，對上述三種線性序列，要在某結點的前趨和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前趨結點是D，前序後繼結點是E；中序前趨結點是E，中序後繼結點是F；後序前趨結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前趨結點是A，後繼結點是E和F。

二叉鏈表的構造

1． 基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮CE∮∮F∮∮。

2． 構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree *T)
{ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參(根指針)本身
char ch；
if((ch=getchar())=='') *T=NULL； //讀人空格，將相應指針置空
else{ //讀人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成結點
(*T)->data=ch；
CreateBinTree(&(*T)->lchild)； //構造左子樹
CreateBinTree(&(*T)->rchild)； //構造右子樹
}
}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
【例】設root是一根指針(即它的類型是BinTree)，則調用CreateBinTree(&root)後root就指向了已構造好的二叉鏈表的根結點。

② 圖遍歷的演算法

圖的遍歷方法目前有深度優先搜索法和廣度（寬度）優先搜索法兩種演算法。 深度優先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //訪問標志數組初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //對尚未訪問的頂點調用DFS
}
void DFS(Graph G, int v){ //從第v個頂點出發遞歸地深度優先遍歷圖G
visited[v]=TRUE; VisitFunc(v); //訪問第v個頂點
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空（0）。
//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
//若w是v的最後一個鄰接點，則返回空（0）。
if(!visited[w])
DFS(G, w); //對v的尚未訪問的鄰接頂點w調用DFS
} 圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…, vi t，並均標記已訪問過，然後再按照vi1,vi2,…, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空輔助隊列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入隊列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //隊頭元素出隊並置為u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}

③ 圖的圖的遍歷

常見的圖遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，這兩種遍歷方式對有向圖和無向圖均適用。 深度優先遍歷的思想類似於樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發，訪問該頂點，然後依次從v的未被訪問的鄰接點出發繼續深度優先遍歷圖中的其餘頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。
深度優先遍歷演算法實現：
為了便於在演算法中區分頂點是否已被訪問過，需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來設置訪問標志，其初始值visited（0≤i≤n-1）為"0"，表示鄰接表中下標值為i的頂點沒有被訪問過，一旦該頂點被訪問，將visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍歷起始點的在鄰接表中的下標值，其下標從0開始
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
對於無向圖，這個演算法可以遍歷到v頂點所在的連通分量中的所有頂點，而與v頂點不在一個連通分量中的所有頂點遍歷不到；而對於有向圖可以遍歷到起始頂點v能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優先遍歷演算法的基礎上，增加對每個頂點訪問狀態的檢測： intvisited[0..n-1]={0,0,...0};voidDFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);} 對圖的廣度優先遍歷方法描述為：從圖中某個頂點v出發，在訪問該頂點v之後，依次訪問v的所有未被訪問過的鄰接點，然後再訪問每個鄰接點的鄰接點，且訪問順序應保持先被訪問的頂點其鄰接點也優先被訪問，直到圖中的所有頂點都被訪問為止。下面是對一個無向圖進行廣度優先遍歷的過程。
下面我們討論一下實現廣度優先遍歷演算法需要考慮的幾個問題：
（1）在廣度優先遍歷中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便後面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點訪問順序，就可以利用隊列結構的操作特點，將訪問的每個頂點入隊，然後，再依次出隊，並訪問它們的鄰接點；
（2）在廣度優先遍歷過程中同深度優先遍歷一樣，為了避免重復訪問某個頂點，也需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來記錄每個頂點是否已經被訪問過。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍歷起始點在鄰接表中的下標，鄰接表中下標從0開始
InitQueue(Q); //Q是隊列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}

④ 以下哪些演算法可用於遍歷網路圖

1、Word 文檔就可以做，裡面有網路圖製作功能！2、網路圖一般呈金字塔形，最上面是企業負責人（安全生產第一責任人），然後是並列的生產負責人、安全負責人、技術負責人，在向下就是各職能部門負責人，直至一線作業職工。

⑤ 圖的遍歷

/*圖的深度優先遍歷與樹的廣度優先遍歷*/
#include<stdio.h>
#include<stdlib.h>
#define k 100
int visited[k]={0},visitedd[k]={0};
typedef struct node{int adjvex;
struct node *next;
}node;
typedef struct {char a;
node *first;
}list;
typedef struct {list vextes[k];
int n,e;
}adjgraph;
void creat(adjgraph *g)
{int i,j,w;node *p;
printf("input n,e;\n");
scanf("%d%d",&g->n,&g->e);
getchar();
for(i=0;i<g->n;i++)
{scanf("%c",&g->vextes[i].a);
g->vextes[i].first=NULL;
}
for(i=0;i<g->e;i++)
{scanf("%d%d",&j,&w);
p=(node*)malloc(sizeof(node));
p->adjvex=j;
p->next=g->vextes[w].first;
g->vextes[w].first=p;
p=(node*)malloc(sizeof(node));
p->adjvex=w;
p->next=g->vextes[j].first;
g->vextes[j].first=p;
}
}
void print(adjgraph g)
{int i;node *p;
for(i=0;i<g.n;i++)
{printf("%c",g.vextes[i].a);
p=g.vextes[i].first;
while(p)
{printf("->%d",p->adjvex);
p=p->next;
}
printf("\n");
}
}
void visit1(adjgraph g,int i) /*深度優先*/
{node *p;
p=g.vextes[i].first;
visited[i]=1;printf("%c",g.vextes[i]);
while(p)
{if(visited[g.vextes[i].first->adjvex]!=1)visit1(g,g.vextes[i].first->adjvex);
p=p->next;
}
}
void dfs(adjgraph g)
{int i;

for(i=0;i<g.n;i++)
if(!visited[i])visit1(g,i);
}
void visit2(adjgraph g,int i)/*廣度優先*/
{node *p;int stack[k];int top=-1;
visitedd[i]=1;printf("%c",g.vextes[i]);
p=g.vextes[i].first;
while(p||top>-1)
{while(p)
{if(visitedd[p->adjvex]!=1){stack[++top]=p->adjvex;
visitedd[p->adjvex]=1;
printf("%c",g.vextes[p->adjvex]);
}
p=p->next;
}
if(top>-1)
p=g.vextes[stack[top--]].first;
}
}
void bfs(adjgraph g)
{int i;
for(i=0;i<g.n;i++)
if(!visitedd[i])visit2(g,i);
}
void main()
{adjgraph g;
creat(&g);
printf("the adjgraph is ;\n");
print(g);
printf("\n");
dfs(g);
printf("\n");
bfs(g);
getch();
}
以前寫的兩個
先粘把
我可一分也沒了

⑥ java Map 怎麼遍歷

java Map 遍歷一般有四種方式

方式一: 這是最常見的並且在大多數情況下也是最可取的遍歷方式。在鍵值都需要時使用。

作為方法一的替代，這個代碼看上去更加干凈；但實際上它相當慢且無效率。

因為從鍵取值是耗時的操作（與方法一相比，在不同的Map實現中該方法慢了20%~200%）。如果安裝了FindBugs，它會做出檢查並警告你關於哪些是低效率的遍歷。所以盡量避免使用。

總結:

如果僅需要鍵(keys)或值(values)使用方法二。

如果所使用的語言版本低於java 5，或是打算在遍歷時刪除entries，必須使用方法三。

否則使用方法一(鍵值都要)。

(6)哪些演算法可遍歷網路圖擴展閱讀：

類似的遍歷演算法：

二叉樹的遍歷演算法

1、先（根）序遍歷的遞歸演算法定義：

若二叉樹非空，則依次執行如下操作：

⑴ 訪問根結點；

⑵ 遍歷左子樹；

⑶ 遍歷右子樹。

2、中（根）序遍歷的遞歸演算法定義：

若二叉樹非空，則依次執行如下操作：

⑴遍歷左子樹；

⑵訪問根結點；

⑶遍歷右子樹。

3、後（根）序遍歷得遞歸演算法定義：

若二叉樹非空，則依次執行如下操作：

⑴遍歷左子樹；

⑵遍歷右子樹；

⑶訪問根結點。

⑦ 對連通圖進行一次先深遍歷可訪問圖的全部頂點，對嗎

如果是無向的連通圖或者有向的強連通圖,是對的,對於無向的非連通圖就不可能一次遍歷訪問到所有頂點了,對於有向的非強連通圖則有可能對,有可能不對

⑧ 數據結構中的常用演算法有哪些呀，對於初學者應該怎樣把它學好呀

基本：
線性表，鏈表，棧，隊列
排序：
快速排序，堆排序，歸並排序，希爾排序，插入排序，選擇排序
二叉樹：
前序，中序，後序遍歷，層次遍歷，包括遞歸演算法和非遞歸演算法兩種
AVL樹，Huffman編碼
二叉樹和樹，森林之間的轉換，穿線樹
圖演算法：
深度優先遍歷演算法，廣度優先遍歷演算法，最小生成樹，最短路徑
字元串：
查找子串，KMP演算法等。

初學者一定要弄懂這些基本的演算法。還有，要多動手練習書上的演算法，代碼是敲出來的。對於考試而言，多看看老師劃的重點足矣。