測試時用的圖是，可以使用其他類型的圖代替。

graph.h #ifndef GRAPH_H_INCLUDED #define GRAPH_H_INCLUDED#define MAXV 100 //最大頂點個數 #define INF 32767 //INF表示∞ typedef int InfoType;//以下定義鄰接矩陣類型 typedef struct {int no; //頂點編號InfoType info; //頂點其他信息，在此存放帶權圖權值 } VertexType; //頂點類型typedef struct //圖的定義 {int edges[MAXV][MAXV]; //鄰接矩陣int n,e; //頂點數，弧數VertexType vexs[MAXV]; //存放頂點信息 } MGraph; //圖的鄰接矩陣類型 //以下定義鄰接表類型 typedef struct ANode //弧的結點結構類型 {int adjvex; //該弧的終點位置struct ANode *nextarc; //指向下一條弧的指針InfoType info; //該弧的相關信息,這里用于存放權值 } ArcNode;typedef int Vertex;typedef struct Vnode //鄰接表頭結點的類型 {Vertex data; //頂點信息int count; //存放頂點入度,只在拓撲排序中用ArcNode *firstarc; //指向第一條弧 } VNode;typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型typedef struct {AdjList adjlist; //鄰接表int n,e; //圖中頂點數n和邊數e } ALGraph; //圖的鄰接表類型 void ArrayToList(int *Arr, int n, ALGraph *&); //用普通數組構造圖的鄰接表 #endif // GRAPH_H_INCLUDEDgraph.cpp #include <stdio.h> #include <malloc.h> #include "graph.h" //功能：由一個反映圖中頂點鄰接關系的二維數組，構造出用鄰接矩陣存儲的圖 //參數：Arr - 數組名，由于形式參數為二維數組時必須給出每行的元素個數，在此將參數Arr聲明為一維數組名（指向int的指針） // n - 矩陣的階數 // g - 要構造出來的鄰接矩陣數據結構 void ArrayToList(int *Arr, int n, ALGraph *&G) {int i,j,count=0; //count用于統計邊數，即矩陣中非0元素個數ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));G->n=n;for (i=0; i<n; i++) //給鄰接表中所有頭節點的指針域置初值G->adjlist[i].firstarc=NULL;for (i=0; i<n; i++) //檢查鄰接矩陣中每個元素for (j=n-1; j>=0; j--)if (Arr[i*n+j]!=0) //存在一條邊，將Arr看作n×n的二維數組，Arr[i*n+j]=Arr[i][j]（n是有多少列）{p=(ArcNode *)malloc(sizeof(ArcNode)); //創建一個節點*pp->adjvex=j;p->info=Arr[i*n+j];p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入*p,和鏈表的操作一樣G->adjlist[i].firstarc=p;}G->e=count; } main.cpp #include <stdio.h> #include <malloc.h> #include "graph.h" int visited[MAXV]; void DFS(ALGraph *G, int v) {ArcNode *p;int w;visited[v]=1;printf("%d ", v);p=G->adjlist[v].firstarc;while (p!=NULL){w=p->adjvex;if (visited[w]==0)DFS(G,w);p=p->nextarc;} } int main() {int i;ALGraph *G;int A[5][5]={{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}};ArrayToList(A[0], 5, G);for(i=0; i<MAXV; i++) visited[i]=0;printf(" 由2開始深度遍歷:");DFS(G, 2);printf("\n");for(i=0; i<MAXV; i++) visited[i]=0;printf(" 由0開始深度遍歷:");DFS(G, 0);printf("\n");return 0; }

總結

以上是生活随笔為你收集整理的第十一周项目实践3 DFS（深度优先搜索）的基本模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。