// 圖的深度優先搜索(采用鄰接表存儲).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