// 圖的深度優先搜索（采用鄰接表存儲）.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 100
using namespace std;
struct edgeNode
{
int no; //邊端的序號
char info; //邊端的名稱
struct edgeNode * next; //下一個
};
struct vexNode
{
char info; //節點名稱
struct edgeNode *link; //與之相連的端點
};
//存儲節點信息
vexNode adjlist[MAX];
//訪問標志
bool visited[MAX];
//建立鄰接表存儲
void createGraph(vexNode *adjlist)
{
int n,e;
cout<<"請輸入節點數：";
cin>>n;
cout<<"請輸入邊數：";
cin>>e;
int i;
for(i=1;i<=n;i++)
{
cout<<"請輸入節點"<<i<<"的名稱：";
cin>>adjlist[i].info;
adjlist[i].link = NULL;
}
edgeNode *p1,*p2;
int v1,v2;
for(i=1;i<=e;i++)
{
cout<<"請輸入邊"<<i<<"的二端的節點序號：";
cin>>v1>>v2;
p1 = (edgeNode*)malloc(sizeof(edgeNode));
p2 = (edgeNode*)malloc(sizeof(edgeNode));
p1->no = v1;
p1->info = adjlist[v1].info;
p1->next = adjlist[v2].link;
adjlist[v2].link = p1;
p2->no = v2;
p2->info = adjlist[v2].info;
p2->next = adjlist[v1].link;
adjlist[v1].link = p2;
}
}
//深度優先搜索無向無權圖
void DFS(vexNode *adjlist,bool *visited,int v1)
{
visited[v1] = true;
cout<<"節點"<<v1<<",名稱"<<adjlist[v1].info<<endl;
edgeNode *p;
p = adjlist[v1].link;
while(p!=NULL)
{
if(!visited[p->no])
DFS(adjlist,visited,p->no);
p=p->next;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"請輸入案例的個數：";
cin>>cases;
while(cases--)
{
//訪問標志清空
int i;
for(i=1;i<MAX;i++)
visited[i] = false;
//創建鄰接表
createGraph(adjlist);
//深度優先搜索
int v1;
cout<<"請輸入從哪個序號的點開始搜索：";
cin>>v1;
cout<<"深度優先搜索次序為："<<endl;
DFS(adjlist,visited,v1);
}
system("pause");
return 0;
}
------------------------------------------------------程序測試-------------------------------------------------
請輸入案例的個數：1
請輸入節點數：8
請輸入邊數：10
請輸入節點1的名稱：r
請輸入節點2的名稱：s
請輸入節點3的名稱：t
請輸入節點4的名稱：u
請輸入節點5的名稱：v
請輸入節點6的名稱：w
請輸入節點7的名稱：x
請輸入節點8的名稱：y
請輸入邊1的二端的節點序號：1 2
請輸入邊2的二端的節點序號：1 3
請輸入邊3的二端的節點序號：2 4
請輸入邊4的二端的節點序號：3 5
請輸入邊5的二端的節點序號：3 6
請輸入邊6的二端的節點序號：5 6
請輸入邊7的二端的節點序號：5 8
請輸入邊8的二端的節點序號：6 7
請輸入邊9的二端的節點序號：6 8
請輸入邊10的二端的節點序號：7 8
請輸入從哪個序號的點開始搜索：2
深度優先搜索次序為：
節點2,名稱s
節點4,名稱u
節點1,名稱r
節點3,名稱t
節點6,名稱w
節點8,名稱y
節點7,名稱x
節點5,名稱v
請按任意鍵繼續.
作者 heyongluoyao8
