[DOJ练习] 有向图的邻接表表示法验证程序(两种写法)

用邻接表表示有向图，完成图的创建、图的深度优先遍历、图的广度优先遍历操作。其中图的顶点信息是字符型，图中顶点序号按字符顺序排列，边的输入按照边的顶点序号从小到大的顺序排列，如下图的边的输入顺序为0 1，0 2，0 3，1 2，1 3，2 4，3 4共七条边，邻接表的边结点采用头插法。本输入样例中所用的图如下所示：

输入描述

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

输出描述

首先输出图的顶点信息，输出完毕换行
接着输出图的邻接表，格式为首先输出第一个顶点，接着输出该顶点的所有的临界点的序号，换行，然后输出下一个顶点及邻接点，以此类推
接下来一行输出从图的第一个顶点开始进行深度优先遍历的序列，中间以空格隔开，输出完毕换行
最后一行输出从图的第一个顶点开始进行广度优先遍历的序列，中间以空格隔开，输出完毕换行

输入样例

输出样例

A B C D E
A 3 2 1
B 3 2 
C 4 
D 4 
E 
A D E C B 
A D C B E

写法一:

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

const int N = 1e5;
int n, m;
int h[N], e[N], ne[N], idx;
int st[N]; //是否已经访问过 
char ch[N];

void AddEdge(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u)
{
	st[u] = 1;
	cout << ch[u] << ' ';
	for(int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if(!st[j]){
			dfs(j);
		}
	} 
}
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 = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			if(!st[j]){
				cout << ch[j] << ' ';
				q[++rear] = j;
				st[j] = 1;
			}
		} 
	}
}
int main()
{
	cin >> n >> m;
	
	for(int i = 0; i < n; i++) cin >> ch[i];
	
	memset(h, -1, sizeof h);
	int a, b;
	for(int i = 0; i < m; i++)
	{
		cin >> a >> b;
		AddEdge(a, b);
	}
	
	for(int i = 0; i < n; i++) cout << ch[i] << ' ';
	//cout << endl;
	for(int i = 0; i < n; i++)
	{
		cout << ch[i] << ' ';
		for(int j = h[i]; j != -1; j = ne[j]){
			cout << e[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]; // 顶点是否被访问

struct ConnectNode{
	int site;
	ConnectNode* next;
};

struct HeadNode{
	char value;
	ConnectNode* firstEdge;
};

class MGraph//无向图
{
public:
    MGraph(int n, int e);
    ~MGraph(){
	}
    void DF(int x); //深度优先遍历
    void BF(int x); //广度优先遍历
    void CheckEdge();//输出边表 
 	void PrintVertex();//输出顶点
private:
    HeadNode v[N];
    int vNum, edgeNum; //顶点数, 边数
};

MGraph::MGraph(int n, int e)
{
    vNum = n, edgeNum = e;
    for(int i = 0; i < n; i++){
    	cin >> v[i].value;
        v[i].firstEdge = NULL;
	}
		
    int j,k;
    ConnectNode* p = NULL;
    for(int i = 0; i < e; i++)
    {
        cin >> j >> k;
        p = new ConnectNode;
        p->site = k;
        p->next = v[j].firstEdge;
        v[j].firstEdge = p;
    }
}

void MGraph::BF(int x){
    int Q[N];
    int front=-1, rear=-1;
 
    cout << v[x].value << ' ';
    visit[x] = 1;
    Q[++rear] = x;
    
    while(front != rear)
    {
        int t = Q[++front];
        ConnectNode* p = v[t].firstEdge;
        while(p)//邻接点全部放入队列中
        {
        	int j = p->site;
            if(!visit[j]){
                cout << v[j].value << ' ';
                visit[j] = 1;
                Q[++rear] = j;
            }
            p = p->next;
        }
    }
}

void MGraph::DF(int x){
    cout << v[x].value << ' ';
    visit[x] = 1;
 
 	ConnectNode* p = v[x].firstEdge;
    while(p)
    {
    	int j = p->site;
        if(!visit[j]){
        	DF(j);
		}
        p = p->next;
    }
}

void MGraph::CheckEdge()
{
	ConnectNode* p = NULL;
	for(int i = 0; i < vNum; i++)
	{
		cout << v[i].value << ' ';
		p = v[i].firstEdge;
		while(p)
		{
			cout << p->site << ' ';
			p = p->next;
		}
		//cout << endl;
	}			
} 

void MGraph::PrintVertex()
{
	for(int i = 0; i < vNum; i++) cout << v[i].value << ' ';
	//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;
}