数据结构-------图（最通俗易懂的文章）（一）图的数据结构及其遍历
簡要
圖的結構類似于樹，都是一個又一個結點（頂點）連接而成，如下圖：
因此樹其實也是一種特殊的圖結構，樹的每個節點只能有一個入度，而圖可以有多個，圖的知識點在這里解不講解了，例如弧，入度，出度等可以查閱書籍或者網上查閱。這里主要講解圖的存儲結構。
圖的存儲結構
圖有多種存儲結構，例如鄰接矩陣，鄰接表或者十字鏈表等，那么它是如何用結構體來實現上面圖這種抽象結構的？
之前文章所說，數據結構一般都有兩種表示方法，一種是數組，一種是鏈式，由于圖的結構比較復雜，任意兩個點之間都有可能存在聯系，因此無法以數據元素放到數組這種來表示它的關系。但是換個思路，當遇到簡單的圖（有向和無向）或者網（有向和無向，帶有路徑，權就稱為網）表示的時候，你可以用兩個數組來存儲圖的數據信息和頂點之間的關系。那么就引出了鄰接矩陣。
鄰接矩陣
上面說用兩個數組來表示圖的關系，具體什么意思，首先拿最簡單的有向圖來舉例：
以上關系簡單理解，V1可以到V2，V2可以到V3等等這里就不細說。這里所說的用矩陣來表示該圖關系，其實是用一個二維數組來表示該矩陣。用下面圖來解釋什么意思：
二維數組都有序號，有幾個頂點就有幾行幾列，比如V1可以到V2，那么在數組上的第一行第二列的值就應該為 1 ， V1無法到達V3
，那么數組中第一行的第三列的值就為0，那么自然就懂了， 圖中頂點的序號對應數組中的位置 (當然數組中也是從0開始算起的，這里只是幫助理解)，有路徑，可以到達，那么對應數組的值就為1，如果沒有路徑那么對應的值就為0，
那么這里就用了一個二維數組來表示了圖中各頂點之間的關系。自然可以發現，第一行為1 的個數就是頂點序號為1 的出度數，列就是頂點總的入度數。
上面這個是有向圖的二維數組定義，那么無向圖的二維數組自然就懂了，無向圖的定義是兩個頂點可以互相到達，那么二維數組就自然成了對稱矩陣了，可以自己畫畫，這里就不說了。
然后再定義一個數組來存放各個頂點的數據關系，那么就完成了圖結構的創建，也可以抽象的想成，定義一個儲存圖頂點的數組，再定義一個二維數組來存儲頂點的關系。
上圖就已經完全解釋了鄰接矩陣如何實現了存儲，就是定義一個圖的結構體，然后其中定義倆數組一個放頂點（包括頂點的信息），一個放頂點的位置關系。
那么定義的結構體為：
這里假設有個例子
要來實現上面的圖，頂點信息就存它們頂點的名稱。
那么就輸出上面的例圖：
先輸入圖結構的信息，幾個頂點幾條弧（ 幾條邊 ）然后輸入三個頂點的信息，執行三次輸入操作，然后頂點信息輸入完成后，輸入弧的信息，你要連接的點，按照頂點在數組中的位置（頂點在頂點數組的位置要和在鄰接矩陣對應好），然后輸出鄰接矩陣，如圖，那么可以看出第一行第二個第三個為 1 說明V0可以通到V1和V2 。可以慢慢理解
上面是有向圖，那么有向網（帶權值的圖，帶路徑的）自然就懂了。那么初始化定義就可以在原來的基礎上加上：
void init(Graph &G) //初始化函數和上面的一樣，就是在后面加上權值賦值的操作 {int i,j;printf("請輸入圖的節點數和弧數");scanf("%d",&i);scanf("%d",&j);G.vexnum=i;G.arcnum=j;for(int x=0;x<G.vexnum;x++){for(int y=0;y<G.vexnum;y++){G.arcs[x][y]=99; //先將鄰接矩陣每個值定義為99，因為無法到達，那么它的權值就是無窮大，這里用99代替無窮大}}for(int x=0;x<i;x++){printf("請輸入頂點的數據信息");scanf("%s",&G.vex[x]);}for(int x=0;x<j;x++){printf("請輸入要連接的點"); int a,b,c;scanf("%d",&a);scanf("%d",&b);printf("請輸入它的權值");scanf("%d",&c); //主要在這里修改即可，將原來的 1改為輸入權值即可G.arcs[a][b]=c; } }那么實現下面這個例子：
上面標有了權值那么如何實現：
輸出結果可以從鄰接矩陣看出頂點的位置和權值信息。根據矩陣中的序號來推斷各頂點之間的信息。（99代表沒有路徑，無窮大）
鄰接矩陣比較簡單。
鄰接表
鄰接表表示法有點類似前面數結構中的孩子表示法，可以看之前的樹結構文章。
總而言之，鄰接表的功能是找出與其連接的點以及權值，但是你要找它的入度之類卻比較麻煩，需要遍歷所有頂點，不如鄰接矩陣的。
鄰接表是如何定義的？
將每個頂點用結構體定義，但是還是要放在那個圖結構體的數組中，但是每個頂點結構體中有一個鏈式表來存放弧的信息，（其連接的下一個點和它的權值）。
上面是框架圖，下面為解釋圖：
每個頂點中有一個鏈式表來存放它指向的頂點的位置（在數組中的位置）或者也可以存弧的權值，這里的鏈式表里信息只存放它指向頂點的位置，并不存儲指向頂點的數據信息，相當于一個索引。只需要遍歷頂點的線性表就可以獲得它所指向的有哪些頂點了。這里也可以將該鏈式表理解為一個存儲弧信息的表。
首先定義圖的結構體框架：（這個例子是帶有權值的，應該叫做網，但是為了大家方便理解，就先叫做圖吧）
typedef struct ArcNode //定義圖中的表結構，鏈式表 {int adjvex; //要連接點在數組中的位置int arc; //定義頂點與該連接點之間的權值struct ArcNode *next; //定義下一個節點,鏈式表之間的鏈，實現鏈式表之間的連接 }ArcNode;typedef struct VNode //定義圖頂點結構 {ArcNode *first; //每個頂點中的表頭的頭指針，可根據上面的圖像理解char vex[10]; //圖信息(數據)的存儲，這里也可以存儲頂點的多個數據，都由自己定，這里就假設存儲的是頂點名稱 }VNode; //定義圖頂點結構 typedef struct {VNode NodeList[10]; //定義頂點數組，存放圖的頂點，和上面的道理一樣int vexnum,arcnum; //定義圖的屬性，幾個頂點幾條弧}Graph; //定義圖總框架，c語言調用的時候要遵從先后定義順序，所以該圖結構定義在最后面對鏈式表不太了解的可以看下面文章
線性表------最通俗易懂的文章
然后我們將該中圖結構進行一下實例化：
void initGraph(Graph &G) {int x,y;printf("輸入圖的節點個數");scanf("%d",&x);G.vexnum=x; //定義圖的頂點數目for(int i=0;i<G.vexnum;i++) //對頂點的信息進行初始化，輸入，因為這里定義的是頂點數組，所以用循環來定義頂點的信息{ scanf("%s",&G.NodeList[i].vex); //輸入頂點的數據信息G.NodeList[i].first=(ArcNode*)malloc(sizeof(ArcNode)); //對每個頂點的鏈表頭指針進行初始化，不懂可以看線性表文章G.NodeList[i].first->next=NULL; }for(int i=0;i<G.vexnum;i++) //按照頂點在數組中的位置進行循環對頂點的相關弧來對點的弧進行初始化信息{printf("這是%s節點，輸入它的弧的個數為：",G.NodeList[i].vex);int n;scanf("%d",&n); //輸入當前頂點的弧數ArcNode *p; //定義一個頭指針來綁定每個頂點中的鏈式表，號方便進行對其的操作p=G.NodeList[i].first; for(int j=0;j<n;j++) //對你定義的弧數進行初始化{ArcNode *q;q=(ArcNode*)malloc(sizeof(ArcNode)); //來為鏈式表的每一個節點來開辟空間（創建一個臨時節點來實現鏈式表的連接）printf("要連接的節點:"); scanf("%d",&q->adjvex); //要連接頂點在數組中的位置printf("弧的長度為:");scanf("%d",&q->arc); //要連接頂點與當前頂點的權值q->next=NULL; //實現鏈式表的連接，這里是從尾部進行連接的，上面文章中是從表頭后進行連接的，連接原理可以看上面文章p->next=q;p=q; //將p指針綁定成下一個節點，方便進行下一次的連接}} }再定義一個輸出函數，當輸入頂點的位置后，就可以輸出它所連接的點了，這里是有向圖，可以輸出它所出度的點。
void printfG(Graph &G,int n) {ArcNode *p=G.NodeList[n].first->next; //綁定需要輸出的頂點的next指針printf("這是%s頂點",G.NodeList[n].vex); //while(p!=NULL) //對鏈式表進行循環遍歷，若為空，說明以及到了鏈式表的結尾{ printf("它連接的頂點有%d,",p->adjvex); //對其連接點信息的輸出printf("它倆之間的權值為%d\n",p->arc);p=p->next; //進行綁定鏈式表的下一個節點} }具體實現
那么就實現一下上面的圖，比較簡單，方便理解。可見V0的出度弧有兩個，那么該頂點的鏈式表就有兩個節點，同理V1和V2。
簡介明了，輸入節點數后，對這幾個節點進行初始化：頂點數據，所連接的有那些頂點和之間的權值等等，當然唯一缺點就是不能看頂點的入度，需要遍歷所有的頂點。否則你可以設置一個逆鄰表，就是鏈式表所存的信息都是入度的信息，上面例子中鏈式表所存的信息都是出度的信息。
上面的鄰接表只是方便來看頂點所連接的有哪些點和之間的權值，但是想遍歷圖中頂點的所有信息和關系，比較麻煩，所以出現了十字鏈表。
十字鏈表
由于受篇幅長度影響，這里就大概說一下原理，大家可以研究。上面兩種圖結構中的弧只是一個抽象的意義，你并沒有定義弧這個對象吧，所以說的頂點的連接是用一種關系來代替弧的存在，那么十字鏈表是將弧也進行結構體封裝定義，每有一條弧就定義一個結構體，里面存弧所連倆頂點在數組中的位置，然后兩個指針域，一個指向相同入度的點，一個指向相同出度的點，（指針所指向的還是弧的結構體）那么你隨便查詢一個頂點的出入信息，那么就可以使用它的弧節點的指針域，直到為NULL為止。
可以看下面文章：
十字鏈表法
圖的遍歷
圖的兩種常用遍歷方法：深度優先搜索和廣度優先搜索
深度遍歷
深度遍歷算法是使用了遞歸的思想，隨便找到一個頂點，然后找到它連接的第一個頂點，一直找連接的第一個頂點，直到找到沒有連接的頂點，然后返回到上一級遞歸找他的另一個子頂點，然后再開始深度搜索，就是一直往下突，直到沒有連接的頂點為止(遍歷過的節點不能再遍歷一次，也相當于是不能連接的點)，然后再返回去，重復遞歸操作就可以遍歷完圖中所有頂點。下面給出深度遍歷圖的流程:
紅色數字表示遍歷頂點的順序。
可以看上圖慢慢理解，十分簡單。這里可以根據樹結構的遍歷來理解，當你遍歷到最后面的節點無處可走的時候，返回到它的上一個節點，看看有沒有第二個子節點，如果有就開始遍歷它的第二個子節點，如果沒有第二個子節點了了，再返回上一個節點，重復此步驟。只不過在圖結構中，只要有連接的可遍歷點就一口氣捅到最后面，然后回溯（一個一個的回溯，仔細檢查是否有第二個子頂點），有點貪心法的味道。
實現
那么它是如何實現這種遍歷方法？上面說了主要使用遞歸的方法來實現，首先遞歸函數的使用和原理得理解，就是定義一個函數，在這個函數里面使用該函數，具體使用這里就不講解了。
咱們就拿上圖做例子
這里創建過程就不寫了，首先你遍歷的時候，是如何判定頂點是否已經遍歷過了，使你不會再進行第二次遍歷？就是設置一個布爾（bool）類型的數組，數組的大小就是你頂點的數目，來存放每個點是否遍歷過，初始化為false表示未遍歷過，當遍歷過后就將相應頂點的 bool 設置為true。
舉個例子，有三個點需要遍歷：
bool visited[3]; //因為三個頂點，所以布爾數組的容量設置為3for(int i=0;i<3;i++){visited[i]=false; //將每個頂點進行初始化為false，表示每個點都沒有遍歷過}visited[1]=true; //表示第二個頂點遍歷過了，所以將其bool值設置為了true那么需要在程序中設置一個全局變量布爾數組，用來監控圖遍歷的情況，那么為什么要定義全局變量，而不是直接在圖創建的時候，在圖結構里面定義？因為該種遍歷方法使用了遞歸的方法，會導致布爾數組結果回溯。導致遍歷過的頂點再遍歷一次，程序錯誤。
bool visited[MAX_SIZE]; //全局變量定義需要在函數外然后定義兩個查找子頂點函數
int findFirst(Graph G,int w) //定義一個找第一個子頂點的函數，w表示要找哪個頂點的子頂點 {for(int n=0;n<G.vexnum;n++){if(G.arcs[w][n]==1&&visited[n]==false) return n; //根據矩陣的特點找第一個頂點，第幾個頂點就是在矩陣的第幾行，從第一列開始循環，當為1的時候說明相應的頂點相連，第一個1說明就是其第一個頂點//并且返回第一個頂點是哪個頂點（在數組中的位置）}return 0; //若該頂點沒有任何相連的點后返回0 }int findNext(Graph G,int w,int t) //找下一個子頂點函數，w表示要找哪個頂點的子頂點，t表示查找的開始點 {for(t=t+1;t<G.vexnum;t++) //因為這是找next頂點，所以要t=t+1,原因可以看下面的遍歷來理解為什么{if(G.arcs[w][t]==1&&visited[t]==false) return t; //和上面的一樣，當為矩陣中的值為1 的時候說明兩點相連，并且返回是哪個頂點}return 0; //當沒有相鄰的頂點后函數就會返回 0 }Tip:根據矩陣的性質，給你一個點，可以從矩陣找它的第一個子頂點和下一個子頂點，自己慢慢理解，但是對于無向圖大家都知道，是對稱矩陣，那么在深度遍歷或者廣度遍歷無向圖的時候，找子頂點會有重復現象，已經遍歷過了的頂點，再用兩個找子頂點函數就會重復，重復遍歷，那么就要在找子頂點函數的判斷中加上 visited[n]==false 條件，在找到子頂點的同時并且判斷該子頂點是否已經遍歷過了，如果沒有再返回子頂點。
定義深度遍歷函數：
void DeepTraverse(Graph G) //深度遍歷函數 {for(int v=0;v<G.vexnum;v++) visited[v]=false; //初始化布爾數組，將每個頂點都設置為false，表示都沒有遍歷過for(int v=0;v<G.vexnum;v++) //這步是開始進行遍歷，使用下面DFS函數，這里為什么還要對所有頂點進行一次循環？//深度遍歷，只要是相連的頂點，從其中一個點遍歷，就可以全部一連串都遍歷出來，但是圖中可能有不連通的兩部分，導致其中不相連，那么有些點就遍歷不上了，所以為了防止這種情況，將所有頂點的visited數組遍歷一下{if(visited[v]==false) DFS(G,v); //根據布爾數組，若為false則開始遍歷，調用下面的遞歸函數，v就是上面開始遍歷的點 }void DFS(Graph G,int v) //遍歷遞歸函數 {visited[v]=true; //遍歷的時候，將其對應布爾數組設置為true，表示已經遍歷過了printf("%s",G.vex[v]); //將遍歷的點數據處理，這里就簡單的輸出作為數據處理for(int w=findFirst(G,v);w>0;w=findNext(G,v,w)) //開始遞歸操作，進行一個循環先找當前遍歷點的第一個子頂點作為 w 的初始值//若有第一個子頂點，那么findFirst函數返回的就不是0，開始進行DFS函數遞歸，若沒有子頂點，那么返回0，直接退出該循環，表示該點后面的子頂點遍歷完了。{if(visited[w]==false) DFS(G,w); //若當前點未遍歷過，那么進入DFS函數進行遞歸} }上面就是深度遍歷的過程，主要是由遞歸函數來實現的，所以比較麻煩，可以進行debug操作來一步一步看其過程，下面舉個簡單的例子來解釋一下代碼流程
如何創建圖結構上篇文章已經講了，這里就不多說了，下面是創建的結果：
那么代碼執行流程 :
橙色文字表示DFS遞歸級別，就是DFS1是在DFS 0中調用的，DFS 2實在DFS 1 中調用的，這里想要理解其使用，必須先理解遞歸函數怎么用和它的原理。
那么會得出其結果為：
因為咱們代碼為邊遍歷邊輸出它的信息，所以就會得出其遍歷順序為： V0 V1 V3 V2，符合深度遍歷的特點。
那么再看之前的例子：
輸出的順序在片頭已經給出，那么用程序試一下：
那么輸出結果符合，深度遍歷實現。
總結
深度遍歷你先理解其含義和運行流程，就是隨便找到一個頂點一個勁的往下突，突到頭后，開始回溯，但是還要將所有頂點再進行一次審查，防止不連通的圖，導致頂點遺漏，因為只要開始深度遍歷，那么只要其是相連的頂點，那么都可以一次性遍歷完，那么這個實現的步驟就是使用遞歸函數來實現，有點類似8皇后問題。
廣度遍歷
廣度遍歷顧名思義，遍歷方式是一層一層的，就是只要與當前遍歷點距離為1的點先開始遍歷，，因此也可以稱為廣度優先遍歷，和深度優先遍歷不同的是，深度遍歷是一個勁的往下突，而廣度像是一種橫掃的方式。其實用一張圖來演示一下流程就懂了。
紅色數字表示遍歷點的順序，有點像擴散，就是尋找當前點距離為1的點，但是它是一層一層的，然后再找與上一次所找的頂點距離為1的點，但它并不是同時遍歷的，還是有順序的遍歷。
上面的數組其實是一個輔助理解作用，但是它可以方便理解代碼是如何實現的 。
實現
廣度優先遍歷代碼實現需要用隊列做基礎，從上面圖看出，可以假設這里有一個數組（當然不是具體的數組，只是一個抽象的集合），存放需要找距離為1的頂點。當你開始的時候，數組中先存放V0，起始點。然后從數組中取出V0（這時候數組為空），尋找與V0距離為1的點，就是緊挨的點，找到了V1和V2，再放到數組中，然后再按存放的順序，拿出V1，找與它距離為1的頂點，找到V3，放到數組中，按照順序，是不是該找V2了，然后找與V2距離為1的點，找到V4和V5，那么這回數組中就為 { V3，V4，V5 }，同理，再開始找V3，顯然沒有頂點了，然后按順序找V4，V5.這就是大概流程，就是先取出一個，找到相關頂點再放到數組中，按順序找下一個，再取，再放。其實這個思想是代碼實現的思想，那么上面說的好像是一層同時遍歷是算法的思想。
其實總結一下就是你找到一個點，找與它相連的幾個點，放到數組里，然后依次找這幾個點相關的點，再次放到數組里，然后在去找上一次找出的點的相關點放進去，好像是一層一層的。
那么這里就用了隊列做輔助工具，如果不理解隊列結構創建和使用的看下面文章
數據結構-----------隊列（最通俗易懂的文章）
那么我們用一張圖來表示隊列存儲的流程：
那么要用隊列數據結構做工具，肯定有隊列數據結構的創建和使用：
那么隊列數據結構創建好后，并且也理解了廣度遍歷算法那么代碼是如何實現的：
void BFSTraverse(Graph &G) {Queue Q; //創建隊列，因為廣度遍歷要用initQueue(Q); //初始化隊列for(int v=0;v<G.vexnum;v++) visited[v]=false; //這個和深度遍歷一樣，你要遍歷圖，首先對圖中所有頂點用bool數組進行初始化，表示都還未遍歷，當然該數組要用全局變量定義原因上面有for(int v=0;v<G.vexnum;v++) //和深度遍歷一樣作用，可能圖中有些點之間不連通，可能會遺忘遍歷//所以要對所有頂點最后進行一次審查，但是如果聯通，只要從一個頂點進去了就一連串可以遍歷出來{if(visited[v]==false) //開始遍歷{visited[v]=true; //表示該點已經遍歷printf("%s",G.vex[v]); //對該點數據處理，這里就用輸出語句代替復雜的處理語句EnQueue(Q,v); //將該點入隊列，每個點是先遍歷再入隊列while(Q.head!=Q.tail) //開始廣度遍歷精髓，當隊列不為空時候表示還沒有遍歷完，可以看上圖理解，當隊列為空時候，說明已經遍歷完{int u=GetQueue(Q); //彈出隊列中的第一個點，就是要找子頂點的點，看上圖，隊列中存儲的是頂點在數組中的位置for(int w=findFirst(G,u);w>0;w=findNext(G,u,w)) //開始找其子頂點，和深度一樣（調用的倆函數和深度一樣，不重復寫定義了）{visited[w]=true; //遍歷子頂點printf("%s",G.vex[w]); //對子頂點數據處理EnQueue(Q,w); //將子頂點入隊列，看上圖演示}}}} }那么對一開始的圖進行實例：
下面就為輸出的結果，符合廣度遍歷，但是可能大家覺得有點偶然性，那么再舉個例子：
這個是從網上隨便找的例子，根據廣度遍歷，起始點為V0，根據廣度遍歷點的順序大家可以先想一下，很簡單，首先遍歷的點肯定為V1 V2 V5，然后就是 V3 V4
那么就符合了廣度遍歷。
最近發現了一個國外挺牛的網站，將所有數據結構都實現了可視化。你可以調節演示速度，有各種算法演示，比如什么查找之類，紅黑樹，什么都有。可能就是全英文，看不懂的可以用瀏覽器的翻譯軟件。地址如下：
數據結構可視化
總結
以上是生活随笔為你收集整理的数据结构-------图（最通俗易懂的文章）（一）图的数据结构及其遍历的全部內容，希望文章能夠幫你解決所遇到的問題。
