圖的深度優先周遊DFS(鄰接矩陣表示法)

1.前言

期末複習算法，第三章講到了圖，是以想将課本中的算法實作。當寫完代碼的時候才發現這樣的複習效率太低了，看書複習是複習，寫代碼是寫代碼。不過寫完以後還是有點成就感的。

2.參考文獻

3.代碼實作

 #include<iostream>

#include<malloc.h>

using namespace std;

#define maxNum 100 //定義鄰接舉證的最大定點數

int visited[maxNum];//通過visited數組來标記這個頂點是否被通路過，0表示未被通路，1表示被通路

//圖的鄰接矩陣表示結構

typedef struct

{

char v[maxNum];//圖的頂點資訊

int e[maxNum][maxNum];//圖的頂點資訊

int vNum;//頂點個數

int eNum;//邊的個數

}graph;

void createGraph(graph *g);//建立圖g

void DFS(graph *g);//深度優先周遊圖g

void dfs(graph *g,int i)

//cout<<"頂點"<<g->v[i]<<"已經被通路"<<endl;

cout<<"頂點"<<i<<"已經被通路"<<endl;

visited[i]=1;//标記頂點i被通路

for(int j=0;j<g->vNum;j++)

{

 if(g->e[i][j]!=0&&visited[j]==0)

  dfs(g,j);

}

}

void DFS(graph *g)

int i;

//初始化visited數組，表示一開始所有頂點都未被通路過

for(i=0;i<g->vNum;i++)

 visited[i]=0;

//深度優先搜尋

 if(visited[i]==0)//如果這個頂點為被通路過，則從i頂點出發進行深度優先周遊

  dfs(g,i);

void createGraph(graph *g)//建立圖g

cout<<"正在建立無向圖..."<<endl;

cout<<"請輸入頂點個數vNum:";

cin>>g->vNum;

cout<<"請輸入邊的個數eNum:";

cin>>g->eNum;

int i,j;

//輸入頂點資訊

//cout<<"請輸入頂點資訊："<<endl;

//for(i=0;i<g->vNum;i++)

// cin>>g->v[i];

//初始畫圖g

 for(j=0;j<g->vNum;j++)

  g->e[i][j]=0;

//輸入邊的情況

cout<<"請輸入邊的頭和尾"<<endl;

for(int k=0;k<g->eNum;k++)

 cin>>i>>j;

 g->e[i][j]=1;

 g->e[j][i]=1;

int main()

graph *g;

g=(graph*)malloc(sizeof(graph));

createGraph(g);

DFS(g);

cin>>i;

return 0;

/*

輸入：

正在建立無向圖...

請輸入頂點個數vNum:10

請輸入邊的個數eNum:9

請輸入邊的頭和尾

0 1

0 3

1 4

1 5

3 6

4 8

5 2

6 7

8 9

*/

作者：xwdreamer