图的遍历
本文介绍的算导上的图的遍历。。。很基础
bfs
广搜就是广度优先搜索，根据名字可以知道，是通过广度来遍历图，也就是层次遍历。
在这里以及下面的DFS（深搜），都用到了颜色WHITE,GRAY,BLACK，不过作用不同，具体分别再分析。
在BFS中，WHITE,GRAY,BLACK这三色是用来记录一个点是否被搜到，以及是否它的邻接点都是灰色。
#include <iostream>
#include <queue>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 999999
#define NIL 0
using namespace std;
int node;
int G[100][100];
int color[100];
int dist[100];
int prev[100];
void BFS(int source)
{
for(int i=1; i<=node; ++i)
{
color[i] = WHITE;
dist[i] = MAX;
prev[i] = NIL;
}
color[source] = GRAY;
dist[source] = 0;
prev[source] = NIL;
queue<int> que;
que.push(source);
while(!que.empty())
{
int no = que.front();
que.pop();
for(int i=1; i<=node; ++i)
if(G[no][i]==1 && color[i]==WHITE)
{
color[i] = GRAY;
dist[i] = dist[no] + 1;
prev[i] = no;
que.push(i);
}
color[no] = BLACK;
}
}
void printPath(int source, int dest)
{
if(source == dest)
cout << source;
else if(prev[dest] == NIL)
cout << "No path from " << source << " to " << dest << " exist\n";
else
{
printPath(source, prev[dest]);
cout << " " << dest;
}
}
int main()
{
freopen("input.txt", "r", stdin);
memset(G, 0, sizeof(G));
cout << "Input the number of the node:\n";
cin >> node;
cout << "Input the Graph:\n";
for(int i=1; i<=node; ++i)
for(int j=1; j<=node; ++j)
cin >> G[i][j];
BFS(2);
cout << dist[4] << endl;
cout << "The path: ";
printPath(2, 4);
}
数据
8
0 1 0 0 0 0 0 1
1 0 0 0 0 0 1 0
0 0 0 1 0 1 1 0
0 0 1 0 1 1 0 0
0 0 0 1 0 1 1 0
0 0 1 1 1 0 0 0
0 1 1 0 1 0 0 0
1 0 0 0 0 0 0 0
dfs
在DFS中，仍然用到了WHITE, GRAY,BLACK，但是它们的用处和BFS有些不同，这里他们是用来表示时间戳，因为DFS会有回溯，所以也就有第一次和第二次搜到。
#include <iostream>
#include <queue>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL 0
using namespace std;
int node;
int G[100][100];
int color[100];
int fir[100], sec[100]; // 用来记录前后时间戳
int prev[100];
int time; // time用来记录时间戳
void DFS_VISIT(int no)
{
color[no] = GRAY; // 当点no第一次被搜到
++time;
fir[no] = time;
for(int i=1; i<=node; ++i)
{
if(G[no][i]==1 && color[i]==WHITE)
{
prev[i] = no;
DFS_VISIT(i);
}
}
color[no] = BLACK; // 当点no深搜完回溯时再次搜到
sec[no] = ++time;
}
void DFS()
{
for(int i=1; i<=node; ++i)
{
if(color[i] == WHITE)
prev[i] = NIL;
}
time = 0;
for(int i=1; i<=node; ++i)
{
if(color[i] == WHITE)
DFS_VISIT(i);
}
}
int main()
{
freopen("input.txt", "r", stdin);
memset(G, 0, sizeof(G));
cout << "Input the number of the node:\n";
cin >> node;
cout << "Input the Graph:\n";
for(int i=1; i<=node; ++i)
for(int j=1; j<=node; ++j)
cin >> G[i][j];
DFS();
cout << "点v(2号)的first:" << fir[2] << " 和second:" << sec[2] << endl;
}
数据
6
0 1 0 0 0 1
0 0 0 0 1 0
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 0 0 1
0 1 0 0 0 0
全部实现的（来自网络
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
char vextex[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' };
typedef struct VertexNode //链表表头结点
{
char data;
struct ArcNode * firstarc;
}VertexNode;
typedef struct ArcNode //弧结点
{
char data;
struct ArcNode * nextarc;
}ArcNode;
ArcNode * InSertArcNode(char name)
{
ArcNode * p = new ArcNode;
p->data = name;
p->nextarc = NULL;
return p;
}
VertexNode * AdjList()//邻接链表表示法
{
ArcNode * p=NULL;
VertexNode * List_head = new VertexNode[9];
int count = 0;
List_head[count].data = 'A';
p = List_head[count].firstarc = InSertArcNode('B');
p = p->nextarc = InSertArcNode('D');
p = p->nextarc = InSertArcNode('E');
count++;
List_head[count].data = 'B';
p = List_head[count].firstarc = InSertArcNode('A');
p = p->nextarc = InSertArcNode('C');
p = p->nextarc = InSertArcNode('E');
count++;
List_head[count].data = 'C';
p = List_head[count].firstarc = InSertArcNode('B');
p = p->nextarc = InSertArcNode('F');
count++;
List_head[count].data = 'D';
p = List_head[count].firstarc = InSertArcNode('A');
p = p->nextarc = InSertArcNode('G');
count++;
List_head[count].data = 'E';
p = List_head[count].firstarc = InSertArcNode('A');
p = p->nextarc = InSertArcNode('B');
p = p->nextarc = InSertArcNode('G');
count++;
List_head[count].data = 'F';
p = List_head[count].firstarc = InSertArcNode('C');
count++;
List_head[count].data = 'G';
p = List_head[count].firstarc = InSertArcNode('D');
p = p->nextarc = InSertArcNode('E');
p = p->nextarc = InSertArcNode('H');
count++;
List_head[count].data = 'H';
p = List_head[count].firstarc = InSertArcNode('G');
p = p->nextarc = InSertArcNode('I');
count++;
List_head[count].data = 'I';
p = List_head[count].firstarc = InSertArcNode('H');
return List_head;
}
void AdjMatrix(char arc[][9])
{
for (int i = 0; i < 9; i++) //初始化邻接矩阵
for (int j = 0; j < 9; j++)
{
arc[i][j] = 0;
}
arc[0][1] = arc[0][3] = arc[0][4] = 1;
arc[1][0] = arc[1][2] = arc[1][4] = 1;
arc[2][1] = arc[2][5] = 1;
arc[3][0] = arc[3][6] = 1;
arc[4][0] = arc[4][1] = arc[4][6] = 1;
arc[5][2] = 1;
arc[6][3] = arc[6][4] = arc[6][7] = 1;
arc[7][6] = arc[7][8] = 1;
arc[8][7] = 1;
}
void DFS_matrix(char G[][9],int i,bool *visited) //深度优先搜索与结点i相通的所有节点
{
visited[i] = true; //顶点i被访问，标志置为true
for (int j = 0; j < 9; j++)
{
if (!visited[j] && G[i][j]==1)
{
cout << vextex[j] << ",";
DFS_matrix(G, j, visited); //递归
}
}
}
void DFS_AdjMatrix(char G[][9]) //深度优先搜索_邻近矩阵存储
{
bool visited[9] = { 0 }; //初始化访问标志数组
for (int i = 0; i < 9; i++) //检测是否所有节点都被访问过
{
if (!visited[i])//顶点i未被访问过，结点i进行深度优先搜索
{
cout << vextex[i]<<",";
DFS_matrix(G, i, visited);//深度优先搜索顶点i
}
}
}
void DFS_list(VertexNode * GRAPH, int i, bool *visited)
{
visited[i] = true; //顶点i被访问，标志置为true
cout << vextex[i] << ",";
ArcNode * p = GRAPH[i].firstarc; //找到第一个邻接链表结点
while (p!=NULL)
{
int temp = p->data - 'A'; //计算节点的位置
if (!visited[temp]) //检测邻接顶点是否被访问过
DFS_list(GRAPH, temp, visited); //深度优先搜索结点temp
p = p->nextarc;//回溯到下一个邻接顶点
}
}
void DFS_AdjList(VertexNode * GRAPH) //深度优先搜索--邻接链表存储
{
bool visited[9] = { 0 }; //初始化访问标志数组
for (int i = 0; i < 9; i++)//检测是否所有节点都被访问过
{
if (!visited[i])
{
DFS_list(GRAPH, i, visited);//深度优先搜索顶点i
}
}
}
void BFS_list(VertexNode *GRAPH, int i, bool *visited, queue<char> &Q)
{
cout << Q.front() << ",";
Q.pop(); //出队列
/*访问到顶点i的所有邻接点*/
ArcNode *p = GRAPH[i].firstarc; //第一个邻结点
while ( p!=NULL ) //依次访问顶点i的邻接点
{
/*(p->data - 'A')代表顶点的序号*/
if (*(visited + (p->data - 'A')) == 0)//检测邻接点是否被访问过
{
*(visited + (p->data - 'A')) = true;//访问标志置1
Q.push(p->data); //邻接点加入优先队列
}
p = p->nextarc;
}
if (!Q.empty()) //递归遍历队列里的顶点
{
BFS_list(GRAPH, Q.front() - 'A', visited, Q);
}
}
void BFS_AdjList(VertexNode *GRAPH)//广度优先搜索顶点i--邻接表存储
{
bool visited[9] = { 0 }; //访问标志初始化
queue<char> Q; //优先队列
for (int i = 0; i < 9; i++)
{
if (!visited[i])
{
visited[i] = true; //访问标志置1
Q.push(vextex[i]); //进入顶点队列
BFS_list(GRAPH, i, visited, Q); //广度优先搜索顶点i
}
}
}
void BFS_KLevel(VertexNode * GRAPH, int i,int k) //计算距离顶点i为k的所有顶点
{
if (k==0) //如果k=0，输出此顶点
{
cout << GRAPH[i].data << endl;
return;
}
queue<char> Q1; //已访问顶点
queue<unsigned int> Q2; //已访问顶点与顶点i的距离
bool visited[9] = { 0 };//访问标志
visited[i] = true; //顶点i置1
Q1.push(vextex[i]); //进入队列
Q2.push(0); //距离队列
while (!Q1.empty())
{
int index = Q1.front() - 'A'; //顶点的序号
ArcNode *p = GRAPH[index].firstarc;//第一个邻接点
int level = Q2.front();
while (p!=NULL)
{
if (*(visited+(p->data-'A')) == 0) //结点没有被访问过
{
*(visited + (p->data - 'A')) =true;//访问标志置1
Q1.push(p->data);
Q2.push(level + 1); //距离+1
if (level + 1 == k) //判断距离
{
cout << p->data << ",";
}
}
p = p->nextarc;
}
Q1.pop();
Q2.pop();
}
}
int main()
{
VertexNode * GRAPH = AdjList(); //邻接链表
char G[9][9] = { 0 };
AdjMatrix(G); //邻接矩阵
DFS_AdjMatrix(G); //DFS--邻接矩阵
cout <<" DFS--邻接矩阵"<< endl;
DFS_AdjList(GRAPH); //DFS--邻接链表
cout << " DFS--邻接链表" << endl;
BFS_AdjList(GRAPH); //BFS--邻接链表
cout << " BFS--邻接链表" << endl;
cout << "------------" << endl;
BFS_KLevel(GRAPH,1,2);//计算距离顶点B为2的顶点
cout << " 距离顶点B为2的顶点" << endl;
return 0;
}
