DFS(深度優(yōu)先遍歷）算法實現(xiàn)與邏輯講解 計算機考研 數(shù)據(jù)結(jié)構(gòu)（408）
#include <stdio.h>
#define self2 0
#define VexNum 100
typedef char VerType;
typedef int ArcType;
typedef struct?
{
VerType vex[VexNum];//圖的頂點名，如v1,v2 ...
ArcType arc[VexNum][VexNum];//圖的邊
int vexnum, arcnum;//圖的頂點數(shù)和邊數(shù)
}MGraph;
//定義函數(shù)，輸入頂點名，獲得頂點下標
int VexName(MGraph G, char v);
//創(chuàng)建圖
void CreateUD(MGraph& G)
{
//8個頂點、9條邊
G.vexnum = 8;
G.arcnum = 9;
G.vex[0] = 'v1';
G.vex[1] = 'v2';
G.vex[2] = 'v3';
G.vex[3] = 'v4';
G.vex[4] = 'v5';
G.vex[5] = 'v6';
G.vex[6] = 'v7';
G.vex[7] = 'v8';
//初始化鄰接矩陣，即頂點的邊，初始值為0
for (int i =0; i< G.vexnum;i++)
{
for (int j =0 ;j <G.vexnum;j++)
{
G.arc[i][j] = self2;
}
}
//如果兩個頂點有連接，把對應(yīng)的邊設(shè)置為1?
int i, j;
i = VexName(G,'v1');
j = VexName(G, 'v2');
//兩個頂點有邊的話，雙向都設(shè)置為1
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v1');
j = VexName(G, 'v3');
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v2');
j = VexName(G, 'v4');
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v2');
j = VexName(G, 'v5');
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v5');
j = VexName(G, 'v8');
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v4');
j = VexName(G, 'v8');
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v3');
j = VexName(G, 'v6');
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v3');
j = VexName(G, 'v7');
G.arc[i][j] = G.arc[j][i] = 1;
i = VexName(G, 'v6');
j = VexName(G, 'v7');
G.arc[i][j] = G.arc[j][i] = 1;
}
// 輸入頂點名，輸出頂點對應(yīng)的下標
int VexName(MGraph G, char v)
{
for (int i = 0; i < G.vexnum; i++)
{
if (G.vex[i] == v)
{
return i;
}
}
}
bool visited[VexNum];
//遞歸遍歷圖
void Prints(MGraph G, int v)
{
printf("v%c->", G.vex[v]);
visited[v] = true;
for (int w =0 ; w<G.vexnum;w++)
{
//該w點和v點之間有邊，且該w點沒有被訪問過
//則訪問該點
if (G.arc[v][w]!= 0 && !visited[w])
{
Prints(G, w);
}
}
}
int main()
{
MGraph G;
CreateUD(G);
int v = 0;
Prints(G, v);
return 0;
}
