每日一题——有向网的邻接矩阵、邻接表、逆邻接表创建、打印及深度、广度遍历

有向网的三种创建和深度广度遍历

#include <iostream>
#include <iomanip>
using namespace std;
#define MAX_VERTEX 20  //最大顶点个数
#define INFINITY 0 //表示极大值
int visited[MAX_VERTEX] = { 0 };

//邻接矩阵
typedef struct {
	int vertexnum;
	int arcnum;
	int arcs[MAX_VERTEX][MAX_VERTEX];
	char vertex[MAX_VERTEX];
}AdjMatrix;

//边结构
typedef struct ArcNode{
	int adjvex; //顶点
	int weight;  //权值
	ArcNode *next;
}ArcNode;

//顶点结构
typedef struct VertexNode {
	char vexdata;
	ArcNode *head;
}VertexNode;

//邻接表
typedef struct {
	VertexNode vertex[MAX_VERTEX];
	int vertexnum;
	int arcnum;
}AdjList;

//队列结点
typedef struct qNode {
	int data;
	qNode *next;
}QueueNode;

//队列
typedef struct queue {
	QueueNode *front;
	QueueNode *rear;
}Queue;

//初始化队列
Queue* InitQueue() {
	Queue *Q;
	QueueNode *qNode;
	Q = (Queue*)malloc(sizeof(Queue));
	qNode = (QueueNode*)malloc(sizeof(QueueNode));
	qNode->next = NULL;
	Q->front = Q->rear = qNode;
	return Q;
}

//判空
int isEmpty(Queue *Q) {
	if (Q->front == Q->rear)
		return 1;
	return 0;
}

//入队
void InQueue(Queue *Q, int x) {
	QueueNode *temp;
	if (temp = (QueueNode*)malloc(sizeof(QueueNode)))
	{
		temp->data = x;
		temp->next = NULL;
		Q->rear->next = temp;
		Q->rear = temp;
	}
}

//出队
void OutQueue(Queue *Q, int *x) {
	QueueNode *temp;
	if (!isEmpty(Q))
	{
		temp = Q->front->next;
		Q->front->next = temp->next;
		*x = temp->data;
		free(temp);
		if (Q->front->next == NULL)
			Q->rear = Q->front;
	}

}

//获取顶点对应的位置
int LocateVexByAdjMatrix(AdjMatrix *G, char v)
{
	for (int i = 1; i <= G->vertexnum; i++)
	{
		if (G->vertex[i] == v)
			return i;
	}
	return 0;
}

//创建图   G1-->邻接矩阵  G2-->邻接表  G3-->逆邻接表
void creatGragh(AdjMatrix *G1,AdjList *G2, AdjList *G3)
{
	cout << "输入图的顶点数和边数：" << endl;
	cin >> G1->vertexnum >> G1->arcnum;
	G2->vertexnum = G1->vertexnum;
    G2->arcnum = G1->arcnum;
	G3->vertexnum = G1->vertexnum;
	G3->arcnum = G1->arcnum;

	cout << "输入顶点信息：" << endl;
	for (int i = 1; i <= G1->vertexnum; i++)
	{
		cin >> G1->vertex[i]; 
		G2->vertex[i].vexdata = G1->vertex[i];
		G3->vertex[i].vexdata = G1->vertex[i];
	}

	for (int i = 1; i <= G1->vertexnum; i++)
	{//初始化邻接矩阵
		for (int j = 1; j <= G1->vertexnum; j++)
		{
			G1->arcs[i][j] = INFINITY;
		}
	}
	for (int i = 1; i <= G2->vertexnum; i++)
	{
		G2->vertex[i].head = NULL;
		G3->vertex[i].head = NULL;
	}
	ArcNode *cur1, *cur2, *pre1 = NULL, *pre2 = NULL;
	cout << "输入头和尾结点及权值：" << endl;
	for (int i = 1; i <= G1->arcnum; i++)
	{
		char chead; char ctail; int weight;
		cin >> chead >> ctail >> weight;
		int head = LocateVexByAdjMatrix(G1, chead);
		int tail = LocateVexByAdjMatrix(G1, ctail);

		G1->arcs[head][tail] = weight;

		cur1 = (ArcNode*)malloc(sizeof(ArcNode));
		cur1->adjvex = tail;
		cur1->weight = weight;
		pre1 = G2->vertex[head].head;
		if (G2->vertex[head].head == NULL)
		{
			G2->vertex[head].head = cur1;
			pre1 = cur1;
			pre1->next = NULL;

		}
		else {
			pre1->next = cur1;
			pre1 = cur1;
			pre1->next = NULL;
		}

		cur2 = (ArcNode*)malloc(sizeof(ArcNode));
		cur2->adjvex = head;
		cur2->weight = weight;
		pre2 = G3->vertex[tail].head;
		if (G3->vertex[tail].head == NULL)
		{
			G3->vertex[tail].head = cur2;
			pre2 = cur2;
			pre2->next = NULL;

		}
		else {
			pre2->next = cur2;
			pre2 = cur2;
			pre2->next = NULL;
		}
	}
}

//打印邻接表
void showGraghByAdjList(AdjList *G)
{
	for (int i = 1; i <= G->vertexnum; i++)
	{//打印顶点信息
		ArcNode *p = G->vertex[i].head;
		cout << G->vertex[i].vexdata << "->";
		while (p)
		{
			cout << G->vertex[p->adjvex].vexdata << " ";
			p = p->next;
		}
		cout << endl;
	}
}

//打印矩阵图
void showGraghByAdjMatrix(AdjMatrix *G)
{
	cout << setw(8) << endl;
	for (int i = 1; i <= G->vertexnum; i++)
	{//打印顶点信息
		cout << G->vertex[i] << setw(4);
	}
	cout << endl;
	for (int i = 1; i <= G->vertexnum; i++)
	{//打印邻接矩阵
		cout << G->vertex[i] << setw(4);
		for (int j = 1; j <= G->vertexnum; j++)
		{
			cout << G->arcs[i][j] << setw(4);
		}
		cout << endl;
	}
}

//各顶点的入度、出度和度
void degree(AdjMatrix *G)
{
	for (int i = 1; i <= G->vertexnum; i++)
	{
		int count = 0, out_count = 0, in_count = 0;
		for (int j = 1; j <= G->vertexnum; j++)
		{
			if (G->arcs[i][j] != INFINITY)
				out_count++;
			if (G->arcs[j][i] != INFINITY)
				in_count++;
			count = out_count + in_count;
		}
		cout << G->vertex[i] << " " << out_count << " " << in_count <<
			" " << count << endl;
	}
}

//一次深度优先遍历
void DFS(AdjMatrix *G, int start)
{
	cout << G->vertex[start];
	visited[start] = 1;
	for (int i = 1; i <= G->vertexnum; i++)
	{
		if (G->arcs[start][i] != INFINITY && visited[i] == 0) {
			DFS(G, i);
		}
	}
}

//深度遍历
void DFSTraverse(AdjMatrix *G)
{
	int count = 0;
	for (int i = 1; i <= G->vertexnum; i++)
		visited[i] = 0;
	for (int i = 1; i <= G->vertexnum; i++)
	{
		if(!visited[i]) {
			count++;
			DFS(G, i);
		}
	}
}


//一次广度遍历
void BFS(AdjMatrix *G, int start)
{
	cout << G->vertex[start];
	visited[start] = 1;
	Queue *q = InitQueue();
	InQueue(q, start);
	while (!isEmpty(q))
	{
		int top = q->front->data;
		OutQueue(q, &top);
		for (int i = 1; i <= G->vertexnum; i++)
		{
			if (G->arcs[start][i] != INFINITY && visited[i] == 0)
			{
				cout << G->vertex[i];
				visited[i] = 1;
				InQueue(q, i);
			}
		}
	}
}

//广度遍历
void BFSTraverse(AdjMatrix *G)
{
	for (int i = 1; i <= G->vertexnum; i++)
		visited[i] = 0;
	for (int i = 1; i <= G->vertexnum; i++)
		if (!visited[i]) BFS(G, i);
}

//主函数
int main() {
	AdjMatrix *G1;
	G1 = (AdjMatrix*)malloc(sizeof(AdjMatrix));
	AdjList *G2;
	G2 = (AdjList*)malloc(sizeof(AdjList));
	AdjList *G3;
	G3 = (AdjList*)malloc(sizeof(AdjList));
	//创建图
	creatGragh(G1, G2, G3);
	
	cout << "打印邻接矩阵：" << endl;
	showGraghByAdjMatrix(G1);
	
	cout << "打印邻接表：" << endl;
	showGraghByAdjList(G2);
	
	cout << "打印逆邻接表：" << endl;
	showGraghByAdjList(G3);

	//打印度
	cout << "打印出度、入度、度：" << endl;
	degree(G1);

	//深度遍历
	cout << "深度遍历：" << endl;
	DFSTraverse(G1);
	cout << endl;

	//广度遍历
	cout << "广度遍历：" << endl;
	BFSTraverse(G1);
	cout << endl;

	free(G1);
	free(G2);
	free(G3);

	system("pause");
	return 0;
}