queue<node>q
q.push(start)
bool canVisit[][]
node cur
while(!q.empty()){
cur = q.top()
q.pop()
foreach(node is connected by cur){
if(canVisit[node.x][node.y])
{
printf("访问结点(%d,%d)",node.x,node.y)
canVisit[node.x][node.y]=false
q.push(node)
}
}
}
#include <iostream>#include <string>
#include <queue>
using namespace std
int FirstAdjVex(int v)
int NextAdjVex(int v, int w)
void DFS(int v) //从顶点v开始对图做深度优先遍历, v是顶点数组的下标
void BFS(int v) //从顶点v开始对图做广度优先遍历,v是顶点数组的下标
int find(string a,int n)
int visited[10]={0}
int traver[10][10]={0}
string name[10]
int main()
{
int n,m,i,j,k
string a,b
//freopen("Traver.txt","r",stdin)
cin>>n
cin>>m
for(i=0 i<n i++)
{
cin>>a
name[i] = a
}
for(i=0 i<mi++){
cin>>a
cin>>b
j = find(a,n)
k = find(b,n)
traver[j][k] = 1
traver[k][j] = 1
}
for(i=0 i<n i++){
if(visited[i] == 0)
DFS(i)
}
cout<<"\n"
for(i=0 i<n i++){
visited[i] = 0
}
for(i=0 i<n i++){
if(visited[i] == 0)
BFS(i)
}
cout<<"\n"
return 0
}
//寻找函数
int find(string a,int n){
int i
for(i=0 i<n i++){
if(a == name[i])
return i
}
return -1
}
int FirstAdjVex(int v)
{
int i
//从编号大的邻接点开始访问
for (i = 9 i >= 0 i--)
{
if (traver[v][i] == 1)
return i
}
return -1
}
int NextAdjVex(int v, int w)
{
int i
for (i = w - 1 i >= 0 i--)
{
if (traver[v][i] == 1)
return i
}
return -1
}
void DFS(int v)
{
int w
//访问顶点v(输出顶点v的名字)
cout<<name[v]<<" "
visited[v] = 1
//找到顶点v的第一个邻接点w
for (w = FirstAdjVex(v) w >= 0 w = NextAdjVex(v, w))
{
//如果w没有访问过,对顶点w做深度优先搜索
if (visited[w] == 0)
DFS(w)
}
}
void BFS(int v) //从顶点v开始对图做广度优先遍历,v是顶点数组的下标
{
int w, u
queue<int> myqueue //定义一个队列,元素是顶点的下标
//把顶点v入队
myqueue.push(v)
cout<<name[v]<<" "
visited[v] = 1
while (!myqueue.empty())
{//当队列不为空时进入循环
//取队头元素
u = myqueue.front()
//队头元素出队
myqueue.pop()
//把u的所有邻接点入队
w = FirstAdjVex(u)
while (w >= 0)
{
if (visited[w] == 0)
{
//访问w
cout<<name[w]<<" "
visited[w] = 1
//w入队
myqueue.push(w)
}
w = NextAdjVex(u, w)
}
}
}
/*程序1:邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边,如果要无向只需要反过来多加一遍即可。
*/
#include <stdio.h>
#include <string.h>
#define MAXM 100000
#define MAXN 10000
int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail
void input_data()
{
scanf("%d%d",&n,&m)
int i,x,y
for (i=1i<=mi++)
{
int x,y
scanf("%d%d",&x,&y)
next[i]=first[x]
first[x]=i
en[i]=y
}
}
void pre()
{
memset(flag,0,sizeof(flag))
pd=0
}
void dfs(int x)
{
flag[x]=1
if (!pd)
{
pd=1
printf("%d",x)
}else
printf(" %d",x)
int p=first[x]
while (p!=0)
{
int y=en[p]
if (!flag[y]) dfs(y)
p=next[p]
}
}
void bfs(int k)
{
head=0tail=1
flag[k]=1dl[1]=k
while (head<tail)
{
int x=dl[++head]
if (!pd)
{
pd=1
printf("%d",x)
}else printf(" %d",x)
int p=first[x]
while (p!=0)
{
int y=en[p]
if (!flag[y])
{
flag[y]=1
dl[++tail]=y
}
p=next[p]
}
}
}
int main()
{
input_data()//读入图信息。
pre()//初始化
printf("图的深度优先遍历结果:")
int i
for (i=1i<=ni++)//对整张图进行dfs 加这个for主要是为了防止不多个子图的情况
if (!flag[i])
dfs(i)
printf("\n-------------------------------------------------------------\n")
pre()//初始化
printf("图的广度优先遍历结果为:")
for (i=1i<=ni++)
if (!flag[i])
bfs(i)
printf("\n----------------------end------------------------------------\n")
return 0
} /*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include <stdio.h>
#include <string.h>
#define MAXN 1000
int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN]
void input_data()
{
scanf("%d%d",&n,&m)
int i
for (i=1i<=mi++)
{
int x,y
scanf("%d%d",&x,&y)
w[x][0]++
w[x][w[x][0]]=y
}
}
void pre()
{
memset(flag,0,sizeof(flag))
pd=0
}
void dfs(int x)
{
flag[x]=1
if (!pd)
{
pd=1
printf("%d",x)
}else printf(" %d",x)
int i
for (i=1i<=w[x][0]i++)
{
int y=w[x][i]
if (!flag[y]) dfs(y)
}
}
void bfs(int t)
{
int head=0,tail=1
dl[1]=tflag[t]=1
while (head<tail)
{
int x=dl[++head]
if (!pd)
{
pd=1
printf("%d",x)
}else printf(" %d",x)
int i
for (i=1i<=w[x][0]i++)
{
int y=w[x][i]
if (!flag[y])
{
flag[y]=1
dl[++tail]=y
}
}
}
}
int main()
{
input_data()
printf("图的深度优先遍历结果:")
pre()
int i
for (i=1i<=ni++)
if (!flag[i])
dfs(i)
printf("\n---------------------------------------------------------------\n")
printf("图的广度优先遍历结果:")
pre()
for (i=1i<=ni++)
if (!flag[i])
bfs(i)
printf("\n-----------------------------end--------------------------------\n")
return 0
}