# 图的遍历

bfs

#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

#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;
}
{
ArcNode * p=NULL;
VertexNode * List_head = new VertexNode[9];
int count = 0;
p = p->nextarc = InSertArcNode('D');
p = p->nextarc = InSertArcNode('E');
count++;
p = p->nextarc = InSertArcNode('C');
p = p->nextarc = InSertArcNode('E');
count++;
p = p->nextarc = InSertArcNode('F');
count++;
p = p->nextarc = InSertArcNode('G');
count++;
p = p->nextarc = InSertArcNode('B');
p = p->nextarc = InSertArcNode('G');
count++;
count++;
p = p->nextarc = InSertArcNode('E');
p = p->nextarc = InSertArcNode('H');
count++;
p = p->nextarc = InSertArcNode('I');
count++;

}

{
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); //递归
}
}
}
{
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;//回溯到下一个邻接顶点
}
}
{
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);
}
}
{
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 };
}