基于邻结表的图的DFS、BFS遍历

#include "StdAfx.h"

#include "Graphlist.h"

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <queue>

//邻结表的遍历

using namespace std;

#define MAXNODE 1000 //图中顶点的最大数

typedef int infotype;

typedef char vertype;

struct ArcNode  //边界点类型

{

int adjvex; //该边的终点编号

ArcNode *next; //指向下一条边的指针

// infotype *info; //该边的相关信息

};

struct VerNode//表头节点

{

vertype vertex; //顶点信息

ArcNode *firstarc; //指向第一个邻接点的指针

};

struct AlGraph//邻接表

{

VerNode vertices[MAXNODE];//邻接表

int vexnum,arcnum; //顶点和边的数目

};

AlGraph CreateAdjList(AlGraph g)//建立有向图的邻接表存储结构

{

int n;

cin>>n;

for(int i = 1;i <= n; i++)

{

cin>>g.vertices[i].vertex;//输入顶点信息

g.vertices[i].firstarc=NULL;//初始化每个链表为空

}

int v1, v2;

cin>>v1>>v2; //输入一条边依附的两个顶点序号

int e = 0; //图的边数

while(v1 != 0&&v2!=0) //题目要求两顶点之一为0结束

{

ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));

//用头插法插入节点以建立链表

p->adjvex = v2;

p->next = g.vertices[v1].firstarc;

g.vertices[v1].firstarc=p;

e++;

cin>>v1>>v2;

}

g.vexnum = n;

g.arcnum = e;

return g;

}

int visited[MAXNODE]; //访问标志数组

void VisitFunc(AlGraph g, int v)//访问v

{

cout<<g.vertices[v].vertex <<endl;

}

int GraphFirstAdj(AlGraph g , int v)//得到v的第一个邻结点

{

if(g.vertices[v].firstarc!=NULL)

return g.vertices[v].firstarc->adjvex;

else return 0;

}

int GraphNextAdj(AlGraph g,int v, int w)//返回v的下一个邻结点，若w是v的最后一个邻结点则返回0

{

ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));

p = g.vertices[v].firstarc;

while(p)

{

if(p->adjvex == w && p->next != NULL)

return p->next->adjvex;

p = p->next;

}

return 0;

}

void DFS(AlGraph g, int v)//dfs

{

visited[v] = 1; VisitFunc(g,v);//访问v顶点(输出v)

for(int w = GraphFirstAdj(g,v); w!= 0; w = GraphNextAdj(g,v,w))

{

if(!visited[w])DFS(g,w);//对v的尚未访问的邻接顶点w递归调用

}

}

void DFSTraverse(AlGraph g) //图的dfs遍历

{

for(int i = 1; i <= g.vexnum; i++) visited[i] = 0;//初始访问数组置未访问标志

for(int i = 1; i <= g.vexnum; i++)

{

if(!visited[i])DFS(g,i);//对未访问的顶点调用DFS

}

}

void BFSTraverse(AlGraph g)// 图的bfs遍历

{

for(int i = 1; i <= g.vexnum;i++) visited[i] = 0;//初始访问数组

queue<int> q;

for(int i = 1;i <= g.vexnum;i++)

{

if(!visited[i])

{

q.push(i);

visited[i] = 1;

VisitFunc(g,i);

while(!q.empty())

{

int v = q.front();//对头元素出队列并置为v

q.pop();

for(int w = GraphFirstAdj(g,v); w!=0; w = GraphNextAdj(g,v,w))//遍历v的邻结点

{

if(!visited[w])

{

q.push(w);//v的尚未访问的邻结顶点w入队列Q

visited[w] = 1;

VisitFunc(g,w);

}

}

}

}

}

}