在之前我們描述了圖的存儲，今天我們來說一下圖的遍歷的操作

對圖的遍歷操作，我會用鄰接矩陣和鄰接表兩種方式分別操作圖的廣度優(yōu)先遍歷和圖的深度優(yōu)先遍歷。

首先，我們先來看比較好寫的深度優(yōu)先遍歷。

圖1.png

圖2.png

上面兩種圖是一個圖和對圖的遍歷操作的示意圖，其中圖2的綠色表示遍歷節(jié)點的順序，黃色的表示與上一個節(jié)點連接的其他節(jié)點。

鄰接矩陣的深度優(yōu)先遍歷

先來說一下思路：
將圖的頂點和邊信息輸入到圖結(jié)構(gòu)中;
創(chuàng)建一個visited 數(shù)組,用來標識頂點是否已經(jīng)被遍歷過.
初始化visited 數(shù)組,將數(shù)組中元素置為FALSE
選擇頂點開始遍歷.(注意非連通圖的情況)
進入遞歸; 打印i 對應的頂點信息. 并將該頂點標識為已遍歷.
循環(huán)遍歷邊表,判斷當前arc[i][j] 是否等于1,并且當前該頂點沒有被遍歷過,則繼續(xù)遞歸 DFS;

思路的核心就是利用一個數(shù)組，記錄標示頂點是否有被遍歷過，然后利用遞歸的思想，將符合條件的節(jié)點值打印出來

鄰接矩陣的結(jié)構(gòu)體的設置

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */

typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 */

#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct {
    VertexType vexs[MAXVEX];//頂點表
    EdgeType arc[MAXVEX][MAXVEX];//鄰接矩陣，可看作邊表
    int numVertexs,numEdges;//圖中當前的頂點數(shù)和邊數(shù)
    
}MGraph;

構(gòu)建一個鄰接矩陣表，這邊不再手動輸入，怕手輸入錯誤，省去一些麻煩

//構(gòu)建一個鄰接矩陣
void CreateMGraph(MGraph *G){
    int i,j;
    //1、確定圖的頂點數(shù)以及邊數(shù)
    G->numEdges = 15;
    G->numVertexs = 9;
    
    //2、讀入頂點信息，建立頂點表
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';
    G->vexs[4] = 'E';
    G->vexs[5] = 'F';
    G->vexs[6] = 'G';
    G->vexs[7] = 'H';
    G->vexs[8] = 'I';
    
    //3、初始化圖中的邊表
    for (i = 0; i<G->numVertexs; i++) {
        for (j = 0; j<G->numVertexs; j++) {
            G->arc[i][j] = 0;
        }
    }
    //4、添加連接信息
    G->arc[0][1]=1;
    G->arc[0][5]=1;
    
    G->arc[1][2]=1;
    G->arc[1][8]=1;
    G->arc[1][6]=1;
    
    G->arc[2][3]=1;
    G->arc[2][8]=1;
    
    G->arc[3][4]=1;
    G->arc[3][7]=1;
    G->arc[3][6]=1;
    G->arc[3][8]=1;
    
    G->arc[4][5]=1;
    G->arc[4][7]=1;
    
    G->arc[5][6]=1;
    
    G->arc[6][7]=1;
    
    //5、無向圖是對稱矩陣，構(gòu)成對稱
    for (i = 0; i<G->numVertexs; i++) {
        for (j = 0; j<G->numVertexs; j++) {
            G->arc[i][j] = G->arc[j][i];
        }
    }
}

遍歷操作

//遍歷

Boolean visited[MAXVEX];//訪問標志的數(shù)組
//1. 標識頂點是否被標記過;
//2. 選擇從某一個頂點開始(注意:非連通圖的情況)
//3. 進入遞歸,打印i點信息,標識; 邊表
//4. [i][j] 是否等于1,沒有變遍歷過visted

void DFS(MGraph G,int i){
    visited[i] = TRUE;
    printf("%c  ",G.vexs[i]);
    for (int j = 0; j<G.numVertexs; j++) {
        if(G.arc[i][j] == 1&& !visited[j]){
            DFS(G, j);
        }
    }
}

void DFSDisplay(MGraph G){
    for (int i = 0; i<G.numVertexs; i++) {
        visited[i] =FALSE;
    }
    for (int i = 0; i<G.numVertexs; i++) {
        if(!visited[i])
            DFS(G, i);
    }
}

打印結(jié)果:

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("鄰接矩陣的深度優(yōu)先遍歷!\n");
    MGraph G;
    CreateMGraph(&G);
    DFSDisplay(G);
    printf("\n");
    return 0;
}

輸出結(jié)果

鄰接矩陣的深度優(yōu)先遍歷!
A  B  C  D  E  F  G  H  I  
Program ended with exit code: 0

鄰接表的深度優(yōu)先遍歷

截屏2020-04-30 下午4.50.05.png

設計思路：

利用鄰接矩陣將信息存儲到鄰接表中
創(chuàng)建一個visited 數(shù)組,用來標識頂點是否已經(jīng)被遍歷過.
初始化visited 數(shù)組,將數(shù)組中元素置為FALSE
選擇頂點開始遍歷.(注意非連通圖的情況)
進入遞歸; 打印i 對應的頂點信息. 并將該頂點標識為已遍歷.
循環(huán)遍歷邊表,判斷當前頂點 是否等于1,并且當前該頂點沒有被遍歷過,則繼續(xù)遞歸 DFS;

鄰接表的深度優(yōu)先遍歷比鄰接矩陣的深度優(yōu)先遍歷復雜很多
我這邊也是為了避免手動輸入，將鄰接矩陣轉(zhuǎn)化為鄰接表。
鄰接表結(jié)構(gòu)是利用數(shù)組記錄每個節(jié)點所連接的節(jié)點的鏈表，結(jié)構(gòu)比較復雜，具體請看代碼

#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */

typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 */

//鄰接表矩陣結(jié)構(gòu)
typedef struct {
    VertexType vexs[MAXVEX];//頂點表
    EdgeType arc[MAXVEX][MAXVEX];//鄰接矩陣，可看作邊
    int numVertexes,numEdges;//圖中當前的頂點數(shù)和邊數(shù)
}MGraph;

//鄰接表結(jié)構(gòu),邊節(jié)點
typedef struct EdgeNode{
    int adjvex; //鄰接點域，存儲該頂點對應下標
    int weight; //用于存儲權(quán)值，對于非網(wǎng)圖可以不需要
    struct EdgeNode *next;  //鏈域，指向下一個鄰接點
}EdgeNode;

//頂點表節(jié)點
typedef struct VertexNode{
    int in;//頂點入對
    char data; //頂點域，存儲頂點信息
    EdgeNode *firstedge;//邊表頭指針
}VertexNode,AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes,numEdges;//圖中當前頂點數(shù)和邊數(shù)
}graphAdjList,*GraphAdjList;

構(gòu)建鄰接矩陣和之前的鄰接矩陣的構(gòu)造一摸一樣，這邊就不重復寫了

將鄰接矩陣轉(zhuǎn)化為鄰接表

//利用鄰接矩陣構(gòu)建鄰接表
void CreateALGraph(MGraph G,GraphAdjList *L){
    //1、創(chuàng)建鄰接表，并且設計鄰接表的頂點數(shù)以及弧數(shù)
    *L = (GraphAdjList)malloc(sizeof(graphAdjList));
    (*L)->numVertexes = G.numVertexes;
    (*L)->numEdges = G.numEdges;
    //2、從鄰接矩陣中將頂點信息輸入
    for (int i = 0; i<G.numVertexes; i++) {
        //頂點入度為0
        (*L)->adjList[i].in = 0;
        //頂點信息
        (*L)->adjList[i].data = G.vexs[i];
        //頂點邊表置空
        (*L)->adjList[i].firstedge = NULL;
    }
    //3、建立邊表
    EdgeNode *e;
    for (int i = 0; i<G.numVertexes; i++) {
        for (int j = 0; j<G.numVertexes; j++) {
            if(G.arc[i][j] == 1){
                //創(chuàng)建邊表中的鄰近節(jié)點i->j
                e = (EdgeNode *)malloc(sizeof(EdgeNode));
                //鄰接序號為j
                e->adjvex = j;
                //將當前節(jié)點指向adjList[i]的頂點邊表上
                e->next = (*L)->adjList[i].firstedge;
                (*L)->adjList[i].firstedge = e;
                //頂點j上的入度++
                (*L)->adjList[j].in++;
            }
        }
    }
}

鄰接表的深度遍歷操作,和之前的鄰接矩陣的遍歷操作基本上一摸一樣，

Boolean visited[MAXSIZE];//訪問標志的數(shù)組
//鄰接表的深度優(yōu)先遞歸算法
void DFS(GraphAdjList G,int i){
    EdgeNode *p;
    visited[i] = TRUE;
    //打印頂點
    printf("%c ",G->adjList[i].data);
    
    p = G->adjList[i].firstedge;
    
    while (p) {
        if(!visited[p->adjvex]){
            DFS(G, p->adjvex);
        }
        p = p->next;
    }
    
}
//鄰接表的深度遍歷操作
void DFSDisplay(GraphAdjList G){
    //1、將訪問記錄數(shù)組默認設置為false
    for (int i = 0; i<G->numVertexes; i++) {
        visited[i] = FALSE;
    }
    
    for (int i = 0; i<G->numVertexes; i++) {
        if(!visited[i])
            DFS(G, i);
    }
}

打印結(jié)果

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("鄰接表的深度優(yōu)先遍歷\n");
    MGraph G;
    GraphAdjList GL;
    CreateMGraph(&G);
    CreateALGraph(G, &GL);
    
    DFSDisplay(GL);
    printf("\n");
    return 0;
}

輸出結(jié)果:

鄰接表的深度優(yōu)先遍歷
A F G H E D I C B 
Program ended with exit code: 0

接下來來實現(xiàn)一下圖的廣度優(yōu)先遍歷，還是一樣，對鄰接矩陣和鄰接表都實現(xiàn)廣度優(yōu)先遍歷操作

廣度優(yōu)先遍歷的特點：

1、把根節(jié)點放到隊列的末尾。
2、每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊 列的末尾。并把這個元素記為它下一級元素的前驅(qū)。
3、找到所要找的元素時結(jié)束程序。
4、如果遍歷整個樹還沒有找到，結(jié)束程序.

截屏2020-04-30 下午4.56.53.png

用一個數(shù)組，標記每一個節(jié)點是否有被輸出；再利用隊列的思想，先將第一個節(jié)點打印輸出，將第一個節(jié)點入隊，判斷隊列是否為空，將入隊的節(jié)點出隊，再將與該節(jié)點相連的節(jié)點且未被標記過的節(jié)點入隊，將隊列出隊，打印出隊的那一個節(jié)點，直到最后一個節(jié)點打印結(jié)束

鄰接矩陣的廣度優(yōu)先遍歷

1、矩陣結(jié)構(gòu)設計

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */

typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 */

#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct {
    VertexType vexs[MAXVEX];//頂點表
    EdgeType arc[MAXVEX][MAXVEX];//鄰接矩陣，可看作邊表
    int numVertexes,numEdges;//圖中當前的頂點數(shù)和邊數(shù)
}MGraph;

2、構(gòu)建鄰接矩陣和之前的一摸一樣，這邊就不在寫了

3、隊列的初始化，入隊，出隊，判空操作

//1、需要用到的隊列結(jié)構(gòu)與相關(guān)功能函數(shù)
//循環(huán)隊列的順序存儲結(jié)構(gòu)
typedef struct{
    int data[MAXSIZE];
    int front;
    int rear;
}Queue;
//初始化一個空隊列
Status InitQueue(Queue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}
//若隊列為空，則返回TRUE，否則返回FALSE
Status QueueEmpty(Queue Q){
    if(Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}
//若隊列未滿，則插入元素e為新Q的隊尾元素
Status EnQueue(Queue *Q,int e){
    if((Q->rear+1)%MAXSIZE == Q->front)
        return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->front+1)%MAXSIZE;
    return OK;
}

//若隊列不空，則刪除Q中對頭元素，用e返回
Status DeQueue(Queue *Q,int *e){
    if(Q->front == Q->rear)
        return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MAXSIZE;
    return OK;;
}

4、廣度優(yōu)先遍歷矩陣

Boolean visited[MAXVEX];
void BFSDisplay(MGraph G){
    Queue q;
    InitQueue(&q);
    for (int i = 0; i<G.numVertexes; i++) {
        visited[i] = FALSE;
    }
    for (int i = 0; i<G.numVertexes; i++) {
        if(!visited[i]){
            visited[i] = TRUE;
            printf("%c ",G.vexs[i]);
            //入隊
            EnQueue(&q, i);
            while (!QueueEmpty(q)) {
                //出隊
                DeQueue(&q, &i);
                for (int j = 0; j<G.numVertexes; j++) {
                    if(G.arc[i][j] == 1&& !visited[j]){
                        visited[j] = TRUE;
                        printf("%c ",G.vexs[j]);
                        EnQueue(&q, j);
                    }
                }
            }
        }
    }
}

打印結(jié)果

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("鄰接矩陣的廣度優(yōu)先遍歷!\n");
    MGraph G;
    CreateMGraph(&G);
    BFSDisplay(G);
    printf("\n");
    return 0;
}

輸出結(jié)果:

鄰接矩陣的廣度優(yōu)先遍歷!
A B F C G I D E H 
Program ended with exit code: 0

鄰接表的廣度優(yōu)先遍歷

鄰接表的廣度遍歷和鄰接矩陣的廣度優(yōu)先遍歷一樣，同樣利用隊列的思想，只是兩種方式結(jié)構(gòu)不同

1、鄰接表的結(jié)構(gòu)設計

#define MAXSIZE 9 /* 存儲空間初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITYC 65535

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */
typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */

typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權(quán)值類型應由用戶定義 */

//鄰接矩陣結(jié)構(gòu)
typedef struct {
    VertexType vexs[MAXVEX];//頂點表
    EdgeType arc[MAXVEX][MAXVEX];//鄰接矩陣，邊表
    int numVertexes,numEdges;//圖中當前的頂點數(shù)和邊數(shù)
}MGraph;

//鄰接表結(jié)構(gòu)
typedef struct EdgeNode{
    int adjvex;//鄰接點域
    int weight;//用于存儲權(quán)值
    struct EdgeNode *next;//鏈域，指向下一個鄰接點
}EdgeNode;

typedef struct VertexNode{
    int in;
    int data;
    EdgeNode *firstedge;
}VertexNode,AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes,numEdges;
}GraphAdjList ,*graphAdjList;

2、構(gòu)建鄰接矩陣在上面有，且一摸一樣，不重復寫了。

3、將鄰接矩陣轉(zhuǎn)換成鄰接表，在之前也寫過，且一摸一樣，不重復寫了

4、隊列的初始化，判空，入隊，出隊不再重復編寫

5、鄰接表的廣度優(yōu)先遍歷，部分操作與之前的描述也一樣，因此不再多余贅述

//鄰接表廣度優(yōu)先遍歷
Boolean visited[MAXSIZE];
void BFSDisplay(graphAdjList G){
    EdgeNode *p;
    Queue Q;
    InitQueue(&Q);
    for (int i = 0; i<G->numVertexes; i++) {
        visited[i] = FALSE;
    }
    for (int i = 0; i<G->numVertexes; i++) {
        if(!visited[i]){
            visited[i] = TRUE;
            printf("%c ",G->adjList[i].data);
        }
        EnQueue(&Q, i);
        while (!QueueEmpty(Q)) {
            DeQueue(&Q, &i);
            p = G->adjList[i].firstedge;
            while (p) {
                if(!visited[p->adjvex]){
                    visited[p->adjvex] = TRUE;
                    printf("%c ",G->adjList[p->adjvex].data);
                    EnQueue(&Q, p->adjvex);
                }
                p = p->next;
            }
        }
    }
}

打印結(jié)果

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("鄰接表的廣度優(yōu)先遍歷!\n");
    MGraph G;
    graphAdjList L;
    createMGraph(&G);
    CreateALMGraph(G, &L);
    BFSDisplay(L);
    printf("\n");
    return 0;
}

輸出結(jié)果:

鄰接表的廣度優(yōu)先遍歷!
A F B G E H D I C 
Program ended with exit code: 0

設圖G有n個頂點和e條邊
則對用鄰接矩陣表示的圖進行深度或廣度優(yōu)先搜索遍歷時的時間復雜度為O(n^2)
而對用鄰接表表示的圖進行深度或廣度優(yōu)先搜索遍歷時的時間復雜度為O(e)
圖的深度或廣度優(yōu)先搜索遍歷時的空間復雜度均為O(n)。