圖的遍歷（深度優先遍歷DFS，廣度優先遍歷BFS）以及Ｃ語言的實現-創新互聯
遍歷的定義：
創新互聯建站專注于企業成都全網營銷、網站重做改版、來安網站定制設計、自適應品牌網站建設、H5開發、商城網站建設、集團公司官網建設、成都外貿網站建設公司、高端網站制作、響應式網頁設計等建站業務，價格優惠性價比高，為來安等各大城市提供網站開發制作服務。從已給的連通圖中某一頂點出發，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算．
一:深度優先遍歷（ＤＦＳ）１，在訪問圖中某一起始頂點Ｖ后，由Ｖ出發，訪問它的任一鄰接頂點Ｗ１
２，再從Ｗ１出發，訪問與Ｗ１鄰接但還未被訪問過的頂點Ｗ２；
３，然后再從Ｗ２出發，進行類似的訪問．．．．．．
４，如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點Ｕ為止．
５，接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問過的鄰接點
６，如果有，則訪問此頂點，之后再從此頂點出發，進行與前述類似的訪問；
７，如果沒有，就再退回一步進行搜索．重復上述過程，直到連通圖中所有頂點都被訪問過為止．
１，使用鄰接矩陣表示的無向圖深度優先遍歷的實現
以上圖為例，以鄰結矩陣創建無向圖，并且深度優先遍歷
#include#include#define MAXSIZE 100 //大頂點數
#define MAX_INT 32767//設置大值
typedef struct{
char vexs[MAXSIZE];//這里的數據類型根據實際情況而定
int arcs[MAXSIZE][MAXSIZE];//這里的數據類型根據實際情況而定
int vexnum, arcnum;//圖的當前頂點數和邊數
}Graph;
int get_index(char* arr,char m)
{
int i = 0;
for(i = 0; i< MAXSIZE; i++)
{
if(arr[i] == m)return i;
}
return -1;
}
void CreatGraph(Graph* G)
{
int i,j = 0;
printf("請輸入頂點和邊的數量:>");
scanf("%d%d",&G->vexnum,&G->arcnum);//把輸入的值保存到圖結構體中
for(i = 0; i< G->vexnum; i++)//初始化鄰接矩陣
{
for(j = 0; j< G->vexnum; j++)
{
G->arcs[i][j] = 0;
}
}
for(i = 0; i< G->vexnum; i++)
{
printf("請輸入每個頂點的值:>");
getchar();//清除鍵盤緩存區的回車鍵
scanf("%c", &G->vexs[i]);//把輸入的值保存到頂點數組當中
}
for(i = 0; i< G->arcnum; i++)//有幾條邊，循環幾次
{
char m,n;//用來接收兩個頂點
int j,k;//接收頂點的下標
printf("請依次輸入每一條邊，格式為:ab >");
getchar();
scanf("%c%c",&m,&n);
j = get_index(G->vexs,m);//得到輸入的m的值，在頂點數組中的下標
k = get_index(G->vexs,n);//得到輸入的n的值，在頂點數組中的下標
G->arcs[j][k] = 1;//給鄰接矩陣對應的位置賦權值
G->arcs[k][j] = 1;//因為是無向網，所以是對稱的，給對稱點賦相同值
}
}
//深度遍歷創建的無向圖
void DepthSearch(Graph G, int v, int*visited)//參數為創建的圖，輸入的值在數組中的下標，判斷是否被訪問過的數組
{
int i = 0;
visited[v] = 1;
printf("%c", G.vexs[v]);
for(i = 0; i< G.vexnum; i++)//遍歷二維數組v行的每一列
{
if((G.arcs[v][i] == 1)&&(visited[i]!=1))//如果有邊相連，而且該頂點還沒有被訪問過
DepthSearch(G, i,visited);//遞歸搜索該頂點
}
}
int main()
{
Graph G;
CreatGraph(&G);
char input;
int visited[MAXSIZE] = {0};//創建數組，用來判斷某一個頂點是否被訪問過
printf("請輸入搜索的起始點:>");
getchar();
scanf("%c",&input);
DepthSearch(G, get_index(G.vexs, input),visited);
return 0;
} 
２，使用鄰接表表示的無向圖深度優先遍歷的實現
同樣以這個無向圖為例：創建一個visited[]數組，用來判斷某個頂點是否已經被訪問過
代碼與上面鄰接矩陣也差不多，只是在條件判斷時有所不同，這里不需要判斷表結點是不是頂點的邊，只需要判斷表結點是不是空．具體代碼如下：
#include#include#define MAXSIZE 100 //大頂點數
#define MAX_INT 32767//設置大值
typedef struct TableNode{//表結點
int index;//結點在數組中的下標
struct TableNode* nextarc;
int info;//權值
}TNode;
typedef struct{//頭結點
char data;
TNode* firstarc;
}HNode;
typedef struct{//整個無向網的結構體
HNode* head;
int vexnum,arcnum;
}Gragh;
int get_index(HNode* arr,char m)
{
int i = 0;
for(i = 0; i< MAXSIZE; i++)
{
if(arr[i].data == m)return i;
}
return -1;
}
void CreatGraph(Gragh* G)
{
int i = 0;
printf("請輸入頂點和邊的數量:>");
scanf("%d%d",&G->vexnum,&G->arcnum);//把輸入的值保存到圖結構體中
for(i = 0; i< G->vexnum; i++)
{
printf("請輸入每個頂點的值:>");
getchar();//清除鍵盤緩存區的回車鍵
scanf("%c", &G->head[i].data);//把輸入的值保存到頂點數組當中
G->head[i].firstarc = NULL;
}
for(i = 0; i< G->arcnum; i++)//有幾條邊，循環幾次
{
char m,n;//用來接收兩個頂點
int j,k;//接收頂點的下標
printf("請依次輸入每一條邊，格式為:ab >");
getchar();
scanf("%c%c",&m,&n);
j = get_index(G->head,m);//得到輸入的m的值，在頂點數組中的下標
k = get_index(G->head,n);//得到輸入的n的值，在頂點數組中的下標
TNode* P1 = malloc(sizeof(TNode));
P1->index = k;
P1->nextarc = G->head[j].firstarc;
G->head[j].firstarc = P1;
//因為是無向圖，所以還要建立一條反向的邊
TNode* P2 = malloc(sizeof(TNode));
P2->index = j;
P2->nextarc = G->head[k].firstarc;
G->head[k].firstarc = P2;
}
}
//深度遍歷創建的無向圖
void DepthSearch(Gragh G, int v, int*visited)//參數為創建的圖，輸入的值在數組中的下標，判斷是否被訪問過的數組
{
visited[v] = 1;
printf("%c", G.head[v].data);
TNode* P = G.head[v].firstarc;
while(P)
{
if(!visited[P->index])DepthSearch(G, P->index, visited);//如果表結點不為空且判斷數組值不為１，則遞歸搜索該結點
P = P->nextarc;//指針指向該結點的下一個結點
}
}
int main()
{
Gragh G;
CreatGraph(&G);
char input;
int visited[MAXSIZE] = {0};//創建數組，用來判斷某一個頂點是否被訪問過
printf("請輸入搜索的起始點:>");
getchar();
scanf("%c",&input);
DepthSearch(G, get_index(G.head, input),visited);
return 0;
} 
方法：從圖的某一結點出發，首先依次訪問該結點的所有鄰接點，再按這些頂點被訪問的先后次序依次訪問與他們相鄰接的所有未被訪問的頂點，重復此過程，直至所有頂點均被訪問為止．
根據廣度優先的特點，和以前樹的層次遍歷比較相似，這里我們也采用隊列的方式，把要訪問的頂點先入隊，訪問完后，再出隊，這樣不停的循環，直到隊列為空，就表示遍歷完成了．
１，使用鄰接矩陣表示的無向圖廣度優先遍歷的實現
這里為了代碼的簡潔和可讀性，我把常用的一些代碼，創建無向圖和隊列，都放到頭文件中去了
如果有需要，可以私信．創建無向圖和隊列的代碼在前面的文章里都有．這里只是重點講廣度優先遍歷的算法
#include#include#define MAXSIZE 10 //大頂點數
#include "gragh.h"
//廣度優先遍歷創建的無向圖
void BreadthSearch(Gragh G, int v, int*visited, SQ* Q)//參數為創建的圖，輸入的值在數組中的下標，判斷是否被訪問過的數組，以及隊列
{
visited[v] = 1;//把傳入的起點，設置為１
push_sq(Q, G.head[v]);//把傳入的頂點入隊
while(Q->back != Q->front)//如果隊不為空，則循環
{
printf("%c", Q->arr[Q->front].data);//訪問隊列最前面的數據
TNode* P = Q->arr[Q->front].firstarc;//把指針指向頂點對應的第一個表結點
while(P)//只要表結點不為空就循環
{
if(!visited[P->index])push_sq(Q, G.head[P->index]);//把沒有訪問過的頂點入隊列
visited[P->index] = 1;//把入了隊列的頂點，在visited數組中設置為１
P = P->nextarc;//指針指向下一條邊
}
pop_sq(Q);
}
}
int main()
{
SQ Q;//隊列類型變量
Gragh G;//圖類型變量
CreatGraph(&G);//創建一個無向圖
InitSQ(&Q);//創建并初始化一個順序隊列
char input;
int visited[MAXSIZE] = {0};//創建數組，用來判斷某一個頂點是否被訪問過
printf("請輸入搜索的起始點:>");
getchar();
scanf("%c",&input);
BreadthSearch(G, get_index(G.head, input),visited,&Q);//廣度優先遍歷無向圖
return 0;
} 
鄰接表不唯一，根據你創建算法，頭插法，尾插法不同，而不同
鄰接矩陣是唯一的，所以用鄰接矩陣創建的圖，遍歷出來的結果都一樣．?
鄰接矩陣的廣度遍歷，和鄰接表的差不多，這里就不詳細說了！
_____________________________________
最近老是有人問我上面代碼里.h和.c文件的內容，我現在發出來
gragh.h:
#include#include#define MAXSIZE 10 //大頂點數
typedef struct TableNode{//表結點
int index;//結點在數組中的下標
struct TableNode* nextarc;
int info;//權值
}TNode;
typedef struct{//頭結點
char data;
TNode* firstarc;
}HNode;
typedef struct{//整個無向網的結構體
HNode* head;
int vexnum,arcnum;
}Gragh;
typedef struct SequenceQueue//定義一個隊列類型結構體
{
HNode* arr;//定義一個數組，類型自己決定
int front;//隊列頭指針（下標）
int back;//隊列尾指針（下標）
}SQ;
int get_index(HNode* arr,char m);
void CreatGraph(Gragh* G);
void InitSQ(SQ* Q);//創建并初始化一個隊列
void push_sq(SQ* Q, HNode e);//插入規則，從隊尾插入
void pop_sq(SQ* Q);//刪除規則，從隊頭刪除
int length_sq(SQ* Q); gragh.c:
#include#include#define MAXSIZE 10 //大頂點數
#define MAX_INT 32767//設置大值
#include "gragh.h"
int get_index(HNode* arr,char m)
{
int i = 0;
for(i = 0; i< MAXSIZE; i++)
{
if(arr[i].data == m)return i;
}
return -1;
}
void CreatGraph(Gragh* G)
{
int i = 0;
printf("請輸入頂點和邊的數量:>");
scanf("%d%d",&G->vexnum,&G->arcnum);//把輸入的值保存到圖結構體中
for(i = 0; i< G->vexnum; i++)
{
printf("請輸入每個頂點的值:>");
getchar();//清除鍵盤緩存區的回車鍵
scanf("%c", &G->head[i].data);//把輸入的值保存到頂點數組當中
G->head[i].firstarc = NULL;
}
for(i = 0; i< G->arcnum; i++)//有幾條邊，循環幾次
{
char m,n;//用來接收兩個頂點
int j,k;//接收頂點的下標
printf("請依次輸入每一條邊，格式為:ab >");
getchar();
scanf("%c%c",&m,&n);
j = get_index(G->head,m);//得到輸入的m的值，在頂點數組中的下標
k = get_index(G->head,n);//得到輸入的n的值，在頂點數組中的下標
TNode* P1 = malloc(sizeof(TNode));
P1->index = k;
P1->nextarc = G->head[j].firstarc;
G->head[j].firstarc = P1;
//因為是無向圖，所以還要建立一條反向的邊
TNode* P2 = malloc(sizeof(TNode));
P2->index = j;
P2->nextarc = G->head[k].firstarc;
G->head[k].firstarc = P2;
}
}
void InitSQ(SQ* Q)//創建并初始化一個隊列
{
Q->arr = (TNode*)malloc(sizeof(TNode)*MAXSIZE);//定義一個10個整型大小空間的數組
Q->front = Q->back = 0;//隊列置空
}
void push_sq(SQ* Q, HNode e)//插入規則，從隊尾插入
{
if((Q->back+1)%MAXSIZE == Q->front)//判斷隊列是否滿
{
printf("error!,隊列已經滿了！");
}
else
{
Q->arr[Q->back] = e;
Q->back = (Q->back + 1)%MAXSIZE;
}
}
void pop_sq(SQ* Q)//刪除規則，從隊頭刪除
{
if(Q->front == Q->back)//判斷隊列是否空
{
printf("error!,隊列已經空了！");
}
else
{
HNode tmp = Q->arr[Q->front];
Q->front = (Q->front + 1)%MAXSIZE;
return;
}
}
int length_sq(SQ* Q)
{
return (Q->back - Q->front + MAXSIZE)%MAXSIZE;
}
你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
文章標題：圖的遍歷（深度優先遍歷DFS，廣度優先遍歷BFS）以及Ｃ語言的實現-創新互聯
本文URL：http://vcdvsql.cn/article12/cccjgc.html
成都網站建設公司_創新互聯，為您提供響應式網站、App設計、云服務器、網站內鏈、電子商務、網站設計
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯
- 網站改版常見的模式有哪些？ 2021-09-29
- 網站改版如何確保新網站排名保持良好狀態？ 2020-11-30
- 網站改版SEO優化需注意事項？ 2022-08-12
- seo優化網站改版后需要注意的幾個方面？ 2013-06-30
- 網站改版的8大注意事項 2021-12-01
- 網站改版為什么比建新站花更花時間？ 2020-12-20
- 網站改版時很容易犯的幾種錯誤 2021-06-27
- 網站改版應該注意的問題 2016-11-02
- 北京網站建設之網站改版會影響到網站的排名嗎？ 2021-06-06
- 成都網站改版有哪些好處 2016-12-18
- 網站改版應注意的事項 2022-07-04
- 網站改版時，應該要注意的幾個常見問題 2016-08-24