//图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，程序如下：
#include <iostream>
//#include <malloc.h>
#define INFINITY 32767
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std
bool *visited //访问标志数组
//图的邻接矩阵存储结构
typedef struct{
char *vexs//顶点向量
int arcs[MAX_VEX][MAX_VEX]//邻接矩阵
int vexnum,arcnum//图的当前顶点数和弧数
}Graph
//队列类
class Queue{
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int))
front=rear=0
}
void EnQueue(int e){
base[rear]=e
rear=(rear+1)%QUEUE_SIZE
}
void DeQueue(int &e){
e=base[front]
front=(front+1)%QUEUE_SIZE
}
public:
int *base
int front
int rear
}
//图G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0i<G.vexnumi++)
if(G.vexs[i]==c) return i
return -1
}
//创建无向网
void CreateUDN(Graph &G){
int i,j,w,s1,s2
char a,b,temp
printf("输入顶点数和弧数:")
scanf("%d%d",&G.vexnum,&G.arcnum)
temp=getchar()//接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char))//分配顶点数目
printf("输入%d个顶点.\n",G.vexnum)
for(i=0i<G.vexnumi++){ //初始化顶点
printf("输入顶点%d:",i)
scanf("%c",&G.vexs[i])
temp=getchar()//接收回车
}
for(i=0i<G.vexnumi++) //初始化邻接矩阵
for(j=0j<G.vexnumj++)
G.arcs[i][j]=INFINITY
printf("输入%d条弧.\n",G.arcnum)
for(i=0i<G.arcnumi++){ //初始化弧
printf("输入弧%d:",i)
scanf("%c %c %d",&a,&b,&w)//输入一条边依附的顶点和权值
temp=getchar()//接收回车
s1=Locate(G,a)
s2=Locate(G,b)
G.arcs[s1][s2]=G.arcs[s2][s1]=w
}
}
//图G中顶点k的第一个邻接顶点
int FirstVex(Graph G,int k){
if(k>=0 &&k<G.vexnum){ //k合理
for(int i=0i<G.vexnumi++)
if(G.arcs[k][i]!=INFINITY) return i
}
return -1
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G,int i,int j){
if(i>=0 &&i<G.vexnum &&j>=0 &&j<G.vexnum){ //i,j合理
for(int k=j+1k<G.vexnumk++)
if(G.arcs[i][k]!=INFINITY) return k
}
return -1
}
//深度优先遍历
void DFS(Graph G,int k){
int i
if(k==-1){ //第一次执行DFS时,k为-1
for(i=0i<G.vexnumi++)
if(!visited[i]) DFS(G,i)//对尚未访问的顶点调用DFS
}
else{
visited[k]=true
printf("%c ",G.vexs[k])//访问第k个顶点
for(i=FirstVex(G,k)i>=0i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i)//对k的尚未访问的邻接顶点i递归调用DFS
}
}
//广度优先遍历
void BFS(Graph G){
int k
Queue Q//辅助队列Q
Q.InitQueue()
for(int i=0i<G.vexnumi++)
if(!visited[i]){ //i尚未访问
visited[i]=true
printf("%c ",G.vexs[i])
Q.EnQueue(i)//i入列
while(Q.front!=Q.rear){
Q.DeQueue(k)//队头元素出列并置为k
for(int w=FirstVex(G,k)w>=0w=NextVex(G,k,w))
if(!visited[w]){ //w为k的尚未访问的邻接顶点
visited[w]=true
printf("%c ",G.vexs[w])
Q.EnQueue(w)
}
}
}
}
//主函数
void main(){
int i
Graph G
CreateUDN(G)
visited=(bool *)malloc(G.vexnum*sizeof(bool))
printf("\n广度优先遍历: ")
for(i=0i<G.vexnumi++)
visited[i]=false
DFS(G,-1)
printf("\n深度优先遍历: ")
for(i=0i<G.vexnumi++)
visited[i]=false
BFS(G)
printf("\n程序结束.\n")
}
输出结果为（红色为键盘输入的数据，权值都置为1）：
输入顶点数和弧数:8 9
输入8个顶点.
输入顶点0:a
输入顶点1:b
输入顶点2:c
输入顶点3:d
输入顶点4:e
输入顶点5:f
输入顶点6:g
输入顶点7:h
输入9条弧.
输入弧0:a b 1
输入弧1:b d 1
输入弧2:b e 1
输入弧3:d h 1
输入弧4:e h 1
输入弧5:a c 1
输入弧6:c f 1
输入弧7:c g 1
输入弧8:f g 1
广度优先遍历: a b d h e c f g
深度优先遍历: a b c d e f g h
程序结束.
已经在vc++内运行通过，这个程序已经达到要求了呀~
楼主你好，下面是源程序！
/*/////////////////////////////////////////////////////////////*/
/* 图的深度优先遍历 */
/*/////////////////////////////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.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 = 0i <numi++ )/* 读取边线信息，插入邻接表*/
{
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 /* 下一个顶点 */
}
}
/****************************** 主程序******************************/
void main()
{
graph ptr
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{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
clrscr()
for ( i = 1i <= 8i++ ) /* 顶点数组初始化 */
{
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 = 1i <= 8i++ )
{
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()
}
/*//////////////////////////////////////////*/
/*图形的广度优先搜寻法 */
/* ///////////////////////////////////////*/
#include <stdlib.h>
#include <stdio.h>
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex
struct node *nextnode
}
typedef struct node *graph /* 图的结构指针*/
struct node head[9] /* 图的顶点数组 */
int visited[9] /* 遍历标记数组 */
int queue[MAXQUEUE] /* 定义序列数组 */
int front = -1 /* 序列前端*/
int rear = -1 /* 序列后端*/
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode/* 顶点指针 */
graph ptr
int from /* 边起点 */
int to /* 边终点 */
int i
for ( i = 0i <numi++ )/* 第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 /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
int enqueue(int value)
{
if ( rear >= MAXQUEUE )/* 检查伫列是否全满 */
return -1 /* 无法存入 */
rear++ /* 后端指标往前移 */
queue[rear] = value /* 存入伫列 */
}
/************************* 数值出队列*********************************/
int dequeue()
{
if ( front == rear ) /* 队列是否为空 */
return -1 /* 为空，无法取出 */
front++ /* 前端指标往前移 */
return queue[front] /* 从队列中取出信息 */
}
/*********************** 图形的广度优先遍历************************/
void bfs(int current)
{
graph ptr
/* 处理第一个顶点 */
enqueue(current) /* 将顶点存入队列 */
visited[current] = 1 /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current) /* 打印输出遍历顶点值 */
while ( front != rear )/* 队列是否为空 */
{
current = dequeue() /* 将顶点从队列列取出 */
ptr = head[current].nextnode /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex)/* 奖定点放入队列 */
visited[ptr->vertex] = 1/* 置遍历标记为1*/
printf(" Vertex[%d]\n",ptr->vertex)/* 印出遍历顶点值 */
}
ptr = ptr->nextnode/* 下一个顶点 */
}
}
}
/*********************** 主程序 ************************************/
/*********************************************************************/
void main()
{
graph ptr
int node[20][2] = { {1, 2}, {2, 1}, /* 边信息数组 */
{6, 3}, {3, 6},
{2, 4}, {4, 2},
{1, 5}, {5, 1},
{3, 7}, {7, 3},
{1, 7}, {7, 1},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{2, 8}, {8, 2},
{7, 8}, {8, 7} }
int i
clrscr()
puts("This is an example of Width Preferred Traverse of Gragh.\n")
for ( i = 1i <= 8i++ )/*顶点结构数组初始化*/
{
head[i].vertex = i
head[i].nextnode = NULL
visited[i] = 0
}
creategraph(node,20) /* 图信息转换，邻接表的建立 */
printf("The content of the graph's allist is:\n")
for ( i = 1i <= 8i++ )
{
printf(" vertex%d =>",head[i].vertex)/* 顶点值 */
ptr = head[i].nextnode/* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex) /* 打印输出顶点内容 */
ptr = ptr->nextnode/* 下一个顶点 */
}
printf("\n") /* 换行 */
}
printf("The contents of BFS are:\n")
bfs(1) /* 打印输出遍历过程 */
printf("\n") /* 换行 */
puts(" Press any key to quit...")
getch()
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）