遍歷的定義：

創(chuàng)新互聯(lián)建站專注于企業(yè)成都全網(wǎng)營銷、網(wǎng)站重做改版、來安網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5開發(fā)、商城網(wǎng)站建設(shè)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為來安等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算．

一:深度優(yōu)先遍歷（ＤＦＳ）

１，在訪問圖中某一起始頂點Ｖ后，由Ｖ出發(fā)，訪問它的任一鄰接頂點Ｗ１

２，再從Ｗ１出發(fā)，訪問與Ｗ１鄰接但還未被訪問過的頂點Ｗ２；

３，然后再從Ｗ２出發(fā)，進行類似的訪問．．．．．．

４，如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點Ｕ為止．

５，接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問過的鄰接點

６，如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；

７，如果沒有，就再退回一步進行搜索．重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止．

１，使用鄰接矩陣表示的無向圖深度優(yōu)先遍歷的實現(xiàn)

以上圖為例，以鄰結(jié)矩陣創(chuàng)建無向圖，并且深度優(yōu)先遍歷

#include#include#define MAXSIZE 100 //大頂點數(shù)
#define MAX_INT 32767//設(shè)置大值
typedef struct{
    char vexs[MAXSIZE];//這里的數(shù)據(jù)類型根據(jù)實際情況而定
    int arcs[MAXSIZE][MAXSIZE];//這里的數(shù)據(jù)類型根據(jù)實際情況而定
    int vexnum, arcnum;//圖的當(dāng)前頂點數(shù)和邊數(shù)
}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("請輸入頂點和邊的數(shù)量:>");
    scanf("%d%d",&G->vexnum,&G->arcnum);//把輸入的值保存到圖結(jié)構(gòu)體中
    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();//清除鍵盤緩存區(qū)的回車鍵
        scanf("%c", &G->vexs[i]);//把輸入的值保存到頂點數(shù)組當(dāng)中
    }
    for(i = 0; i< G->arcnum; i++)//有幾條邊，循環(huán)幾次
    {
        char m,n;//用來接收兩個頂點
        int j,k;//接收頂點的下標(biāo)
        printf("請依次輸入每一條邊，格式為:ab >");
        getchar();
        scanf("%c%c",&m,&n);
        j = get_index(G->vexs,m);//得到輸入的m的值，在頂點數(shù)組中的下標(biāo)
        k = get_index(G->vexs,n);//得到輸入的n的值，在頂點數(shù)組中的下標(biāo)
        G->arcs[j][k] = 1;//給鄰接矩陣對應(yīng)的位置賦權(quán)值
        G->arcs[k][j] = 1;//因為是無向網(wǎng)，所以是對稱的，給對稱點賦相同值
    }


}
//深度遍歷創(chuàng)建的無向圖
void DepthSearch(Graph G, int v, int*visited)//參數(shù)為創(chuàng)建的圖，輸入的值在數(shù)組中的下標(biāo)，判斷是否被訪問過的數(shù)組
{
    int i = 0;
    visited[v] = 1;
    printf("%c", G.vexs[v]);
    for(i = 0; i< G.vexnum; i++)//遍歷二維數(shù)組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};//創(chuàng)建數(shù)組，用來判斷某一個頂點是否被訪問過
    printf("請輸入搜索的起始點:>");
    getchar();
    scanf("%c",&input);
    DepthSearch(G, get_index(G.vexs, input),visited);
    return 0;

}

２，使用鄰接表表示的無向圖深度優(yōu)先遍歷的實現(xiàn)

同樣以這個無向圖為例：創(chuàng)建一個visited[]數(shù)組，用來判斷某個頂點是否已經(jīng)被訪問過

代碼與上面鄰接矩陣也差不多，只是在條件判斷時有所不同，這里不需要判斷表結(jié)點是不是頂點的邊，只需要判斷表結(jié)點是不是空．具體代碼如下：

#include#include#define MAXSIZE 100 //大頂點數(shù)
#define MAX_INT 32767//設(shè)置大值
typedef struct TableNode{//表結(jié)點
    int index;//結(jié)點在數(shù)組中的下標(biāo)
    struct TableNode* nextarc;
    int info;//權(quán)值

}TNode;

typedef struct{//頭結(jié)點
    char data;
    TNode* firstarc;
}HNode;

typedef struct{//整個無向網(wǎng)的結(jié)構(gòu)體
    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("請輸入頂點和邊的數(shù)量:>");
    scanf("%d%d",&G->vexnum,&G->arcnum);//把輸入的值保存到圖結(jié)構(gòu)體中


    for(i = 0; i< G->vexnum; i++)
    {
        printf("請輸入每個頂點的值:>");
        getchar();//清除鍵盤緩存區(qū)的回車鍵
        scanf("%c", &G->head[i].data);//把輸入的值保存到頂點數(shù)組當(dāng)中
        G->head[i].firstarc = NULL;
    }
    for(i = 0; i< G->arcnum; i++)//有幾條邊，循環(huán)幾次
    {
        char m,n;//用來接收兩個頂點
        int j,k;//接收頂點的下標(biāo)
        printf("請依次輸入每一條邊，格式為:ab >");
        getchar();
        scanf("%c%c",&m,&n);
        j = get_index(G->head,m);//得到輸入的m的值，在頂點數(shù)組中的下標(biāo)
        k = get_index(G->head,n);//得到輸入的n的值，在頂點數(shù)組中的下標(biāo)
        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;
    }


}
//深度遍歷創(chuàng)建的無向圖
void DepthSearch(Gragh G, int v, int*visited)//參數(shù)為創(chuàng)建的圖，輸入的值在數(shù)組中的下標(biāo)，判斷是否被訪問過的數(shù)組
{
    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);//如果表結(jié)點不為空且判斷數(shù)組值不為１，則遞歸搜索該結(jié)點
        P = P->nextarc;//指針指向該結(jié)點的下一個結(jié)點
    }

}
int main()
{
    Gragh G;
    CreatGraph(&G);
    char input;
    int visited[MAXSIZE] = {0};//創(chuàng)建數(shù)組，用來判斷某一個頂點是否被訪問過
    printf("請輸入搜索的起始點:>");
    getchar();
    scanf("%c",&input);
    DepthSearch(G, get_index(G.head, input),visited);
    return 0;

}

二:廣度優(yōu)先遍歷（ＢＦＳ）?

方法：從圖的某一結(jié)點出發(fā)，首先依次訪問該結(jié)點的所有鄰接點，再按這些頂點被訪問的先后次序依次訪問與他們相鄰接的所有未被訪問的頂點，重復(fù)此過程，直至所有頂點均被訪問為止．

根據(jù)廣度優(yōu)先的特點，和以前樹的層次遍歷比較相似，這里我們也采用隊列的方式，把要訪問的頂點先入隊，訪問完后，再出隊，這樣不停的循環(huán)，直到隊列為空，就表示遍歷完成了．

１，使用鄰接矩陣表示的無向圖廣度優(yōu)先遍歷的實現(xiàn)

這里為了代碼的簡潔和可讀性，我把常用的一些代碼，創(chuàng)建無向圖和隊列，都放到頭文件中去了

如果有需要，可以私信．創(chuàng)建無向圖和隊列的代碼在前面的文章里都有．這里只是重點講廣度優(yōu)先遍歷的算法

#include#include#define MAXSIZE 10 //大頂點數(shù)
#include "gragh.h"
//廣度優(yōu)先遍歷創(chuàng)建的無向圖
void BreadthSearch(Gragh G, int v, int*visited, SQ* Q)//參數(shù)為創(chuàng)建的圖，輸入的值在數(shù)組中的下標(biāo)，判斷是否被訪問過的數(shù)組，以及隊列
{
    visited[v] = 1;//把傳入的起點，設(shè)置為１
    push_sq(Q, G.head[v]);//把傳入的頂點入隊

    while(Q->back != Q->front)//如果隊不為空，則循環(huán)
    {
        printf("%c", Q->arr[Q->front].data);//訪問隊列最前面的數(shù)據(jù)
        TNode* P = Q->arr[Q->front].firstarc;//把指針指向頂點對應(yīng)的第一個表結(jié)點
        while(P)//只要表結(jié)點不為空就循環(huán)
        {
            if(!visited[P->index])push_sq(Q, G.head[P->index]);//把沒有訪問過的頂點入隊列
            visited[P->index] = 1;//把入了隊列的頂點，在visited數(shù)組中設(shè)置為１
            P = P->nextarc;//指針指向下一條邊
        }
        pop_sq(Q);
    }
}
int main()
{
    SQ Q;//隊列類型變量
    Gragh G;//圖類型變量
    CreatGraph(&G);//創(chuàng)建一個無向圖
    InitSQ(&Q);//創(chuàng)建并初始化一個順序隊列
    char input;
    int visited[MAXSIZE] = {0};//創(chuàng)建數(shù)組，用來判斷某一個頂點是否被訪問過
    printf("請輸入搜索的起始點:>");
    getchar();
    scanf("%c",&input);
    BreadthSearch(G, get_index(G.head, input),visited,&Q);//廣度優(yōu)先遍歷無向圖
    return 0;

}

鄰接表不唯一，根據(jù)你創(chuàng)建算法，頭插法，尾插法不同，而不同

鄰接矩陣是唯一的，所以用鄰接矩陣創(chuàng)建的圖，遍歷出來的結(jié)果都一樣．?

鄰接矩陣的廣度遍歷，和鄰接表的差不多，這里就不詳細說了！

_____________________________________

最近老是有人問我上面代碼里.h和.c文件的內(nèi)容，我現(xiàn)在發(fā)出來

gragh.h:

#include#include#define MAXSIZE 10 //大頂點數(shù)
typedef struct TableNode{//表結(jié)點
    int index;//結(jié)點在數(shù)組中的下標(biāo)
    struct TableNode* nextarc;
    int info;//權(quán)值
}TNode;

typedef struct{//頭結(jié)點
    char data;
    TNode* firstarc;
}HNode;

typedef struct{//整個無向網(wǎng)的結(jié)構(gòu)體
    HNode* head;
    int vexnum,arcnum;
}Gragh;
typedef struct SequenceQueue//定義一個隊列類型結(jié)構(gòu)體
{
    HNode* arr;//定義一個數(shù)組，類型自己決定
    int front;//隊列頭指針（下標(biāo)）
    int back;//隊列尾指針（下標(biāo)）
}SQ;
int get_index(HNode* arr,char m);
void CreatGraph(Gragh* G);
void InitSQ(SQ* Q);//創(chuàng)建并初始化一個隊列
void push_sq(SQ* Q, HNode e);//插入規(guī)則，從隊尾插入
void pop_sq(SQ* Q);//刪除規(guī)則，從隊頭刪除
int length_sq(SQ* Q);

gragh.c:

#include#include#define MAXSIZE 10 //大頂點數(shù)
#define MAX_INT 32767//設(shè)置大值
#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("請輸入頂點和邊的數(shù)量:>");
    scanf("%d%d",&G->vexnum,&G->arcnum);//把輸入的值保存到圖結(jié)構(gòu)體中


    for(i = 0; i< G->vexnum; i++)
    {
        printf("請輸入每個頂點的值:>");
        getchar();//清除鍵盤緩存區(qū)的回車鍵
        scanf("%c", &G->head[i].data);//把輸入的值保存到頂點數(shù)組當(dāng)中
        G->head[i].firstarc = NULL;
    }
    for(i = 0; i< G->arcnum; i++)//有幾條邊，循環(huán)幾次
    {
        char m,n;//用來接收兩個頂點
        int j,k;//接收頂點的下標(biāo)
        printf("請依次輸入每一條邊，格式為:ab >");
        getchar();
        scanf("%c%c",&m,&n);
        j = get_index(G->head,m);//得到輸入的m的值，在頂點數(shù)組中的下標(biāo)
        k = get_index(G->head,n);//得到輸入的n的值，在頂點數(shù)組中的下標(biāo)
        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)//創(chuàng)建并初始化一個隊列
{
    Q->arr = (TNode*)malloc(sizeof(TNode)*MAXSIZE);//定義一個10個整型大小空間的數(shù)組
    Q->front = Q->back = 0;//隊列置空

}
void push_sq(SQ* Q, HNode e)//插入規(guī)則，從隊尾插入
{
    if((Q->back+1)%MAXSIZE == Q->front)//判斷隊列是否滿
    {
        printf("error!,隊列已經(jīng)滿了！");
    }
    else
    {
        Q->arr[Q->back] = e;
        Q->back = (Q->back + 1)%MAXSIZE;
    }
}
void pop_sq(SQ* Q)//刪除規(guī)則，從隊頭刪除
{
    if(Q->front == Q->back)//判斷隊列是否空
    {
        printf("error!,隊列已經(jīng)空了！");
    }
    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;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：圖的遍歷（深度優(yōu)先遍歷DFS，廣度優(yōu)先遍歷BFS）以及Ｃ語言的實現(xiàn)-創(chuàng)新互聯(lián)
本文URL：http://jinyejixie.com/article12/cccjgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、App設(shè)計、云服務(wù)器、網(wǎng)站內(nèi)鏈、電子商務(wù)、網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)