[DOJ练习] 无向图的邻接矩阵表示法验证程序

采用邻接矩阵表示无向图，完成图的创建、图的深度优先遍历、图的广度优先遍历操作。其中图的顶点信息是字符型，图中顶点序号按字符顺序排列。本输入样例中所用的图如下所示：

输入描述

第一行输入两个值，第一个是图中顶点的个数，第二个是图中边的条数
第二行输入各顶点的信息，即输入每个顶点字符
第三行开始输入每条边，每条边的形式为两个顶点的序号，中间以空格隔开，输入完一条边换行

输出描述

首先输出图的顶点信息，输出完毕换行
接着输出图的邻接矩阵，假如图中有n个顶点，则输出形式为n行n列的邻接矩阵，输出完毕换行
接下来一行输出从图的第一个顶点开始进行深度优先遍历的序列，中间以空格隔开，输出完毕换行
最后一行输出从图的第一个顶点开始进行广度优先遍历的序列，中间以空格隔开，输出完毕换行

输入样例

5 7
A B C D E
0 1
0 2
0 3
1 2
1 3
2 4
3 4

输出样例

A B C D E
0 1 1 1 0
1 0 1 1 0 
1 1 0 0 1
1 1 0 0 1
0 0 1 1 0
A B C E D
A B C D E

写法一:

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100;
int n, m;
int g[N][N];
int st[N]; //是否已经访问过 
char ch[N];

void dfs(int u)
{
	st[u] = 1;
	cout << ch[u] << ' ';
	for(int i = 0; i < n; i++)
	{
		if(!st[i] && g[u][i]){
			dfs(i);
		}
	} 
}
void bfs(int u)
{
	int q[N];
	int front = -1, rear = -1;
	q[++rear] = u;
	st[u] = 1;
	cout << ch[u] << ' ';
	while(front != rear)
	{
		int t = q[++front];
		for(int i = 0; i < n; i++)
		{
			if(!st[i] && g[t][i]){
				cout << ch[i] << ' ';
				q[++rear] = i;
				st[i] = 1;
			}
		} 
	}
}
int main()
{
	cin >> n >> m;
	
	for(int i = 0; i < n; i++) cin >> ch[i];
	
	int a, b;
	for(int i = 0; i < m; i++)
	{
		cin >> a >> b;
		g[a][b] = g[b][a] = 1;
	}
	
	for(int i = 0; i < n; i++) cout << ch[i] << ' ';
	//cout << endl;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++){
			cout << g[i][j] << ' ';
		}
		//cout << endl;
	}
	
	for(int i = 0; i < n; i++)
	{
		if(!st[i])
			dfs(i);
	}
	//cout << endl;
	
	memset(st, 0, sizeof st); 
	for(int i = 0; i < n; i++){
		if(!st[i])
			bfs(i);	
	}
	return 0;
}

写法二:

#include<iostream>
#include<cstring>
using namespace std;

const int N = 10;
int visit[N]; // 顶点是否被访问

class MGraph//无向图
{
public:
    MGraph(int n, int e);
    ~MGraph(){
	}
    void DF(int x); //深度优先遍历
    void BF(int x); //广度优先遍历
    void CheckEdge();//输出edge矩阵 
 	void PrintVertex();//输出顶点
private:
    char v[N];  //存放图的顶点数据
    int vNum, edgeNum; //顶点数, 边数
    int edge[N][N]; //存放边, 0/1 无/有
} ;

MGraph::MGraph(int n, int e)
{
    vNum = n, edgeNum = e;
    for(int i = 0; i < n; i++) cin >> v[i];
    
    memset(edge, 0, sizeof edge);
    int j,k;
    for(int i = 0; i < e; i++)
    {
        cin >> j >> k;
        edge[j][k] = edge[k][j] = 1;
    }
}

void MGraph::BF(int x){
    int Q[N];
    int front=-1, rear=-1;
 
    cout << v[x] << ' ';
    visit[x] = 1;
    Q[++rear] = x;
    
    while(front != rear)
    {
        int t = Q[++front];
        for(int i = 0 ;i < vNum; i++)//邻接点全部放入队列中
        {
            if(edge[t][i] && !visit[i]){
                cout << v[i] << ' ';
                visit[i] = 1;
                Q[++rear] = i;
            }
        }
    }
}

void MGraph::DF(int x){
    cout << v[x] << ' ';
    visit[x] = 1;
 
    for(int i = 0; i < vNum; i++)
    {
        if(edge[x][i] && !visit[i])
            DF(i);
    }
}

void MGraph::CheckEdge()
{
	for(int i = 0; i < vNum; i++)
	{
		for(int j = 0; j < vNum; j++)
		{
			cout << edge[i][j] << ' ';
		}
		//cout << endl;
	}
	//cout << endl;
			
} 

void MGraph::PrintVertex()
{
	for(int i = 0; i < vNum; i++) cout << v[i] << ' ';
	//cout << endl;
}

int main()
{
	int n,m;
	cin >> n >> m;

	MGraph g(n, m);
	
	g.PrintVertex();

	g.CheckEdge(); 
	
	
	for(int i = 0; i < n; i ++) 
		if(!visit[i])
			g.DF(i);
	
	//cout << endl;
	
	memset(visit, 0, sizeof visit);
	for(int i = 0; i < n; i ++) 
		if(!visit[i])
			g.BF(i);
	return 0;
}