和樹的遍歷相似，若從圖中某頂點出發訪遍圖中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷(TraversingGraph)。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。圖的遍歷順序有兩種：深度優先搜索（DFS）和廣度優先搜索（BFS）。對每種搜索順序，訪問各頂點的順序也不是唯一的。
1、鄰接表及逆鄰接表的存儲方法
（1）定義
鄰接表是圖的一種鏈式存儲結構。類似于樹的孩子鏈表表示法。在鄰接表中為圖中每個頂點建立一個單鏈表，用單鏈表中的一個結點表示依附于該頂點的一條邊（或表示以該頂點為弧尾的一條弧），稱為邊（或弧）結點。特征如下：
1) 為每個頂點建立一個單鏈表，
2) 第i個單鏈表中包含頂點Vi的所有鄰接頂點。
把同一個頂點發出的邊鏈接在同一個邊鏈表中，鏈表的每一個結點代表一條邊，叫做表結點（邊結點），鄰接點域adjvex保存與該邊相關聯的另一頂點的頂點下標 ， 鏈域nextarc存放指向同一鏈表中下一個表結點的指針，數據域info存放邊的權。邊鏈表的表頭指針存放在頭結點中。頭結點以順序結構存儲，其數據域da
帶權圖的邊結點中info保存該邊上的權值。
頂點 Vi 的邊鏈表的頭結點存放在下標為 i 的頂點數組中。
在鄰接表的邊鏈表中，各個邊結點的鏈入順序任意，視邊結點輸入次序而定。
設圖中有 n 個頂點，e 條邊，則用鄰接表表示無向圖時，需要 n 個頂點結點，2e 個邊結點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需 n 個頂點結點，e 個邊結點。
建立鄰接表的時間復雜度為O(n*e)。若頂點信息即為頂點的下標，則時間復雜度為O(n+e)。
（2）鄰接表的示例及逆鄰接表
在有向圖的鄰接表中，第 i 個鏈表中結點的個數是頂點Vi的出度，表結點的adjvex存儲的是以當前頭結點為弧尾的弦。在所有鏈表中其鄰接點域的值為i的結點的個數是頂點vi的入度。
在有向圖的逆鄰接表中，第 i 個鏈表中結點的個數是頂點Vi 的入度，表結點的adjvex存儲的是以當前頭結點為弧首的弦。
如下為帶權圖的鄰接表：
2、深度優先算法思想
深度優先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態是所有頂點均未被訪問過，在G中任選一個頂點i作為遍歷的初始點，則深度優先搜索遞歸調用包含以下操作：
（1）訪問搜索到的未被訪問的鄰接點；
（2）將此頂點的visited數組元素值置1；
（3）搜索該頂點的未被訪問的鄰接點，若該鄰接點存在，則從此鄰接點開始進行同樣的訪問和搜索。
深度優先搜索DFS可描述為：
（1）訪問v0頂點；
（2）置 visited[v0]=1；
（3）搜索v0未被訪問的鄰接點w，若存在鄰接點w，則DFS(w)。
遍歷過程：
DFS 在訪問圖中某一起始頂點 v 后，由 v 出發，訪問它的任一鄰接頂點 w1；再從 w1 出發，訪問與 w1鄰 接但還沒有訪問過的頂點 w2；然后再從 w2 出發，進行類似的訪問，… 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。
接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。如下圖所示：
3、深度優先算法C語言描述
4、深度優先算法C語言實現
#include "stdio.h"
#define MAX_VERTEX_NUM 10
#include "conio.h"
#include "stdlib.h"
typedef char VertexType;
typedef struct ArcNode{
intadjvex;
structArcNode *nextarc;
intinfo;
}ArcNode; //表結點類型
typedef struct VNode{
VertexTypeda
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]; //頭結點
typedef struct{
AdjListvertices; //鄰接表
intvexnum,arcnum;
}ALGraph;
int visited[MAX_VERTEX_NUM];
int LocateVex(ALGraph G,char u)
{
inti;
for(i=0;i<G.vexnum;i++)
{ if(u==G.vertices[i].da
if(i==G.vexnum) {printf("Error u!\n");exit(1);}
return0;
}
void CreateALGraph_adjlist(ALGraph &G)
{
int i,j,k,w;
char v1,v2,enter;
ArcNode *p;
printf("Input vexnum &arcnum:\n");
scanf("%d",&G.vexnum);
scanf("%d",&G.arcnum);
printf("InputVertices:\n");
for(i=0;i<G.vexnum;i++)
{ scanf("%c%c",&enter,&G.vertices[i].da
G.vertices[i].firstarc=NULL;
}//for
printf("Input Arcs(v1,v2,w)以回車分開各個數據:\n");
for (k=0;k<G.arcnum;k++)
{
scanf("%c%c",&enter,&v1);
scanf("%c%c",&enter,&v2);
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info= w;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}//for
return;
}//CreateALGraph_adjlist
voidDFS(ALGraph &G, int v)
{
ArcNode *p;
printf("%c",G.vertices[v].da
visited[v]=1;
p=G.vertices[v].firstarc;
while (p)
{ if (!visited[p->adjvex])DFS(G,p->adjvex);
p=p->nextarc;
}
} //從第v個頂點出發DFS
void DFSTraverse(ALGraph &G)
{
for (int v=0;v<G.vexnum;++v)
visited[v]=0;
for (int v=0;v<G.vexnum;++v)
if(!visited[v]) DFS(G,v);
}//DFSTraverse
int main()
{
ALGraph G;
CreateALGraph_adjlist(G);
DFSTraverse(G);
}
5、注意點
（1）強制轉換：p=(char*)&a;
（2）字符輸入中，賦值順序和緩存的聯系
scanf是從標準輸入緩沖區中讀取輸入的數據，如果連續輸入兩個%c格式的字符，而中間又要涉及回車，那么第二個字符將被賦予回車。
解決辦法：
1、清空輸入緩沖區
第一個scanf后加入語句：fflush(stdin); //C語言清空輸入緩沖區函數
2、格式控制中加入空格
將第二個scanf改為：scanf("%c",&ch2);//在%號前面加一個空格
scanf格式輸入時要求輸入格式與格式控制符中的完全一樣(如：scanf("abcd%c",&ch);輸入時必須輸入abcde,ch得到的值為e)空格可以抵消前面輸入的回車符。
3、直接用ch=getche()吸收回車
4、當輸入完整數或字符時，后面還需要輸入字符時，為了避免輸入的字符變成回車符，可以在輸入字符前多加一條scanf語句來吃掉前面的回車符。此時用來吃掉回車符的scanf輸入可以用%c方式，也可以用%d方式。當用%c方式來吃掉回車符時，回車符被讀進了char類型變量中，當用%d方式來吃掉回車符時，回車符并沒有被送進int類型變量中，而是在異常的字符輸入后，被自動清除了。
（3）我們這里，對圖中各個頂點以單個字符來處理，當然也可以字符串來進行。對各個節點的訪問，也僅僅是輸出他們的節點名，當然還可以進一步的操作。
