引入

樹的遍歷方式可分為深搜和廣搜，這同樣適用于圖，不過有些地方會有出入。

樹的節點結構從根到葉子節點都是1：n,到葉子節點后就沒有了。而對于圖來說，如果到了最底下的節點，它可能除了連接已經記錄過的上層節點，還連接著上一層的其他未被記錄的節點（比如下圖的V8)，那對于第三層的節點（V4、V5）來說,再往下順延就成了2:1(n:m)了。

圖的深搜

與樹的深搜類似，一直沿著一個方向走到底就是深搜。從V1遍歷到V8之后，因為V8連接著兩個節點，遍歷節點時如何準確遍歷到還未被訪問的節點，這時候可以通過數組來做標記（標記已遍歷的），防止重復遍歷。
之后就精準的遍歷到了V5，那下一步應該怎么辦？對于V5來說它連接了V8和V2，而此時兩者都已經訪問過了。與樹的遍歷相似，訪問到底了就回退到根節點繼續遍歷另外一邊，直到所有節點都被標記。

圖的廣搜

深搜和廣搜都需要用數組存儲標記信息防止重復便利，除此之外：
在之前的二叉樹的廣搜和深搜這篇文章里利用隊列來實現記憶功能從而完成廣搜的方法同樣適用于圖的廣搜,這里不再附圖了,想更直觀的了解過程可以點進去看一下。

遍歷過V1之后就將V1連接的的下一層節點都入隊（先左后右，先進先出）,之后將入隊的節點逐個出隊,每出隊一個節點就將此節點連接的下一層節點都入隊,直到所有節點出隊。
需要注意的是廣搜中標記的是已進入隊列的節點,不是訪問過的節點,防止重復入隊。

在寫代碼之前先到上一篇回顧一下圖的鄰接矩陣的存儲特點：
示意圖， 鄰接矩陣！本篇沒有鄰接表的代碼。

頭文件

在代碼中,1E4 是科學計數法的表示形式,它表示的是 10^4 ,也就是十進制的 10000 。
在圖的鄰接矩陣表示中，常常會用一個很大的值（比如這里的 1E4 ）來表示兩個頂點之間沒有邊相連（即不可達），這類似于無窮大的概念，在后續涉及到圖的路徑、權重等相關算法（如最短路徑算法）時，方便進行計算和判斷。

#pragma once
#define INF 1E4
#define MaxNodeNum 20typedef struct {int no;       //頂點編號char* show;   //顯示指向的數組的對應內容（如A、B）
}MatrixVertex;    //矩陣頂點typedef int MatrixEdge; 
//圖的鄰接矩陣表示法
typedef struct {                MatrixVertex vex[MaxNodeNum];  //頂點集int nodeNum;                   //約束實際的頂點個數MatrixEdge edge[MaxNodeNum][MaxNodeNum]; //邊集int edgeNum;                   //邊的數量int directed;                  //是否有向
}MGraph; //表示鄰接矩陣（鄰接圖的縮寫）void initMGraph(MGraph* graph, char* names[], int num, int directed, int edgeValue);
void addMGraphEdge(MGraph* graph, int x, int y, int w);
void visitMGraphNode(MatrixVertex* node);
void initVisited();void DFS_MGraph(MGraph* graph, int v);
void BFS_MGraph(MGraph* graph, int v);

功能實現

判斷是否有邊

static int isEdge(int weight) {if (weight > 0 && weight < INF) {return 1;}return 0;
}

初始化

void initMGraph(MGraph* graph, const char* names[], int num, int ditected, int edgeValue) {graph->directed = ditected;graph->nodeNum = num;graph->edgeNum = 0;   //初始邊的權值為0，代表沒有邊memset(graph->vex, 0, sizeof(graph->vex));memset(graph->edge, 0, sizeof(MatrixEdge)*MaxNodeNum*MaxNodeNum);for (int i = 0; i < num; ++i) {//頂點（一維數組）填充graph->vex[i].no = i;graph->vex[i].show =(char*) names[i];for (int j = 0; j < num; ++j) {//邊（矩陣）的填充graph->edge[i][j] = edgeValue; }}
}

添加邊

void addMGraphEdge(MGraph* graph, int x, int y, int w) {if (x<0 || x>graph->nodeNum) {return;}if (y<0 || y>graph->nodeNum) {return;}if (!isEdge(graph->edge[x][y])) { //如果沒有邊再執行graph->edge[x][y] = w;if (graph->directed == 0) {  //如果是無向則同時標記對向路徑的權值graph->edge[y][x] = w; //矩陣的轉置}graph->edgeNum++;  //同時更新路徑數目}
}

訪問當前頂點

void visitMGraphNode(MatrixVertex* node) {printf("\t%s", node->show);    //訪問當前頂點的展示內容（如A、B）
}

標記與初始化標記

static int MGraphVisited[MaxNodeNum]; //用來標記已遍歷的頂點void initVisited() {    //初始化已標記的頂點，防止多次遍歷時受干擾memset(MGraphVisited, 0, sizeof(MGraphVisited));
}

深搜

void DFS_MGraph(MGraph* graph, int v) { //v是起始頂點的索引visitMGraphNode(&graph->vex[v]);  //先訪問MGraphVisited[v]=1;               //訪問后做標記for (int i = 0; i < graph->nodeNum; ++i){ //訪問v的所有鄰接頂點
if( isEdge(graph->edge[v][i]) && MGraphVisited[i] == 0){ //若鄰接且未訪問DFS_MGraph(graph, i);  //再重復操作}}
}

廣搜

void BFS_MGraph(MGraph* graph, int v) { //起始頂點下標vint que[MaxNodeNum];    //隊列存儲待訪問的頂點下標int rear = 0, front = 0, cur;rear = (rear + 1) % MaxNodeNum; //形成循環數組防止溢出（后移一格）que[rear] = v;          //下標v入隊MGraphVisited[v] = 1;   //標記下標為v的頂點(廣度遍歷標記的是入隊的頂點)while (front != rear) { //隊列不為空時front = (front + 1) % MaxNodeNum; //訪問隊頭（front后移一格，這里此時front與rear相同）cur = que[front];   //cur現為隊頭，同時也為剛入隊在隊尾的頂點標號vvisitMGraphNode(&graph->vex[cur]); //訪問v標號存儲的頂點for (int i = 0; i < graph->nodeNum; ++i) { //訪問v的所有鄰接且未被標記的頂點if (isEdge(graph->edge[cur][i]) && !MGraphVisited[i]) {rear = (rear + 1) % MaxNodeNum; //找到后將尾指針后移que[rear] = i;                  //將該頂點入隊并放在隊尾MGraphVisited[i] = 1;           //入隊后做標記}}}
}

功能調用

void testMatrixGraph(MGraph* grap) {  const char* nodeName[] = { "V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8" };  initMGraph(grap, nodeName, sizeof(nodeName) / sizeof(nodeName[0]), 0, 0);  addMGraphEdge(grap, 0, 1, 1);  addMGraphEdge(grap, 0, 2, 1);  addMGraphEdge(grap, 1, 3, 1);  addMGraphEdge(grap, 1, 4, 1);  addMGraphEdge(grap, 2, 5, 1);  addMGraphEdge(grap, 2, 6, 1);  addMGraphEdge(grap, 3, 7, 1);  addMGraphEdge(grap, 4, 7, 1);  addMGraphEdge(grap, 5, 6, 1);  
}
int main() {MGraph g1;testMatrixGraph(&g1);printf("graph have %d edge!\n", g1.edgeNum);DFS_MGraph(&g1, 0);initVisited();printf("\n");BFS_MGraph(&g1, 0);return 0;
}