/* 圖的深度優先遍歷 */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
struct node /* 圖頂點結構定義 */
{
int vertex; /* 頂點數據信息 */
struct node *nextnode; /* 指下壹頂點的指標 */
};
typedef struct node *graph; /* 圖形的結構新型態 */
struct node head[9]; /* 圖形頂點數組 更改為實際大小*/
int visited[9]; /* 遍歷標記數組 更改為實際數組大小*/
/********************根據已有的信息建立鄰接表********************/
void creategraph(int node[20][2],int num)/*num指的是圖的邊數*/
{
graph newnode; /*指向新節點的指針定義*/
graph ptr;
int from; /* 邊的起點 */
int to; /* 邊的終點 */
int i;
for ( i = 0; i < num; i++ ) /* 讀取邊線信息，插入鄰接表*/
{
from = node[i][0]; /* 邊線的起點 */
to = node[i][1]; /* 邊線的終點 */
/* 建立新頂點 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立頂點內容 */
newnode->nextnode = NULL; /* 設定指標初值 */
ptr = &(head[from]); /* 頂點位置 */
while ( ptr->nextnode != NULL ) /* 遍歷至鏈表尾 */
ptr = ptr->nextnode; /* 下壹個頂點 */
ptr->nextnode = newnode; /* 插入節點 */
}
}
/********************** 圖的深度優先搜尋法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 記錄已遍歷過 */
printf("vertex[%d]\n",current); /* 輸出遍歷頂點值 */
ptr = head[current].nextnode; /* 頂點位置 */
while ( ptr != NULL ) /* 遍歷至鏈表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如過沒遍歷過 */
dfs(ptr->vertex); /* 遞回遍歷呼叫 */
ptr = ptr->nextnode; /* 下壹個頂點 */
}
}
/****************************** 主程序******************************/
int main()
{
graph ptr; /* 邊線數組 */
int node[20][2] = { {1, 2}, {2, 1}, /*換成自己的頂點數值，下面for循環中 i 的取值範圍相應更改*/
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
system("cls");
for ( i = 1; i <= 8; i++ ) /* 頂點數組初始化 */
{
head[i].vertex = i; /* 設定頂點值 */
head[i].nextnode = NULL; /* 指針為空 */
visited[i] = 0; /* 設定遍歷初始標誌 */
}
creategraph(node,20); /* 建立鄰接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 頂點值 */
ptr = head[i].nextnode; /* 頂點位置 */
while ( ptr != NULL ) /* 遍歷至鏈表尾 */
{
printf(" %d ",ptr->vertex); /* 印出頂點內容 */
ptr = ptr->nextnode; /* 下壹個頂點 */
}
printf("\n"); /* 換行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印輸出遍歷過程 */
printf("\n"); /* 換行 */
puts(" Press any key to quit...");
getch();
return 0;
}