D-OJ刷题日记：有向图的邻接表表示法验证程序题目编号:516

用邻接表表示有向图，完成图的创建、图的深度优先遍历、图的广度优先遍历操作。其中图的顶点信息是字符型，图中顶点序号按字符顺序排列，边的输入按照边的顶点序号从小到大的顺序排列，如下图的边的输入顺序为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>#define MAXSIZE 100using namespace std;int visited[MAXSIZE] = { 0 };//边表结点
struct EdgeNode
{int adjvex;//顶点下标EdgeNode* next;//边表结点指针
};//顶点表结点
struct VertexNode 
{char vertext;//顶点数据EdgeNode* firstEdge;//边表头结点
};class ALGraph {
public:ALGraph(char a[],int n,int e);~ALGraph();
public:void DFTraverse(int v);void BFTraverse(int v);void Pirnt_ALG();
private:VertexNode adjlist[MAXSIZE];//定义顶点表（包含顶点的数据域和指针域）int VertexNum, EdgeNum;//图的顶点数和边数
};
//构造函数
ALGraph::ALGraph(char a[], int n, int e)
{int i, j, k;EdgeNode* s = NULL;//定义顶点表中的边表的头指针VertexNum = n;EdgeNum = e;for (i = 0; i < VertexNum; i++)//顶点表初始化{adjlist[i].vertext = a[i];adjlist[i].firstEdge = NULL;}for (k = 0; k < EdgeNum; k++){cin >> i >> j;s = new EdgeNode;s->adjvex = j;//将顶点下标输入边表s->next = adjlist[i].firstEdge;//将结点s插入表头adjlist[i].firstEdge = s;//使用头插法减少操作数量使程序更高效}
}
//析构函数
ALGraph::~ALGraph()
{EdgeNode* p = NULL, * q = NULL;for (int i = 0; i < VertexNum; i++){p = q = adjlist[i].firstEdge;while (p != NULL){p = p->next;delete q;q = p;//悲惨的小q，永远的替罪羊}}
}
//深度优先
void ALGraph::DFTraverse(int v)
{int j;EdgeNode* p = NULL;cout << adjlist[v].vertext<<' ';visited[v] = 1;p = adjlist[v].firstEdge;while (p != NULL){j = p->adjvex;//将p的下标传给jif (visited[j] == 0)DFTraverse(j);p = p->next;}
}
//广度优先
void ALGraph::BFTraverse(int v)
{int w, j, Q[MAXSIZE];int front = -1,rear = -1;//队列初始化EdgeNode* p = NULL;cout << adjlist[v].vertext<<' ';visited[v] = 1;Q[++rear] = v;//被访问顶点入队while (front != rear){w = Q[++front];p = adjlist[w].firstEdge;//p指向顶点v的边表while (p != NULL){j = p->adjvex;if (visited[j] == 0){cout << adjlist[j].vertext<<' ';visited[j] = 1;Q[++rear] = j;}p = p->next;}}
}
//输出邻接表
void ALGraph::Pirnt_ALG()
{EdgeNode* p = NULL;for (int i = 0; i < VertexNum; i++){p = adjlist[i].firstEdge;cout << adjlist[i].vertext<<' ';while (p != NULL){cout << p->adjvex << ' ';p = p->next;}//cout << endl;}
}int main()
{char ch[MAXSIZE];int i,n,e;cin >> n >> e;for (int i = 0; i < n; i++)cin >> ch[i];ALGraph ALG(ch, n, e);for (i = 0; i < MAXSIZE; i++)visited[i] = 0;for (int i = 0; i < n; i++)cout<< ch[i]<<' ';//cout << endl;ALG.Pirnt_ALG();//cout << endl;//cout <<endl<< "深度优先遍历：" << endl;for (int i = 0; i < n; i++){if (visited[i] == 0){ALG.DFTraverse(i);}}//ALG.DFTraverse(0);//cout <<endl<< "广度优先遍历：" << endl;//cout << endl;for (int i = 0; i < MAXSIZE; i++)visited[i] = 0;for (int i = 0; i < n; i++){if (visited[i] == 0){ALG.BFTraverse(i);}}//ALG.BFTraverse(0);return 0;
}