// Day09.cpp : 图表示及实现

#include "pch.h"
#include <iostream>
using namespace std;

enum Graphkind { DG, DN, UDG, UDN };// 有向图、无向图、有向网、无向网


// 定义图
typedef struct Node
{
	int *vex;			// 顶点数组
	int vexnum;			// 顶点个数
	int edge;			// 图的边数
	int **adjMatrix;	// 图的邻接矩阵
	enum Graphkind kind;// 图的类型
}MGraph;


// 创建图
void CreateGraph(MGraph &G,enum Graphkind kind)
{
	cout << "请输入图的顶点个数：";
	cin >> G.vexnum;
	cout << "请输入图的边的条数：";
	cin >> G.edge;

	G.kind = kind;

	G.vex = new int[G.vexnum];
	G.adjMatrix = new int*[G.vexnum];

	cout << "图的顶点数为：" << G.vexnum << endl;

	for (int i = 0; i < G.vexnum; i++)
	{
		G.adjMatrix[i] = new int[G.vexnum];
	}

	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.kind == DG || G.kind == DN)
			{
				G.adjMatrix[i][j] = 0;
			}
			else
			{
				G.adjMatrix[i][j] = INT_MAX;
			}
		}
	}

	// 用户输入顶点间的关系
	cout << "请输入顶点间的关系(例如1 2代表一号顶点指向二号顶点)：" << endl;
	for (int i = 0; i < G.edge; i++)
	{
		int a,b;
		cin >> a >> b;
		if (G.kind == DN)	// 无向图
		{
			G.adjMatrix[b - 1][a - 1] = 1;
			G.adjMatrix[a - 1][b - 1] = 1;
		}
		else if (G.kind == DG) // 有向图
		{
			G.adjMatrix[a - 1][b - 1] = 1;
		}
		else if (G.kind == UDG)  // 有向网
		{
			int weight;
			cout << "请输入该边的权重：";
			cin >> weight;
			G.adjMatrix[a - 1][b - 1] = weight;
		}
		else
		{
			int weight;
			cout << "请输入该边的权重：";
			cin >> weight;
			G.adjMatrix[b - 1][a - 1] = weight;
			G.adjMatrix[a - 1][b - 1] = weight;		
		}
	}
}

// 图输出
void PrintGraph(MGraph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.adjMatrix[i][j] == INT_MAX)
			{
				cout << "口" <<" ";
			}
			else
			{
				cout << G.adjMatrix[i][j];
			}
		}
		cout << endl;
	}
}


// 清除图
void ClearGraph(MGraph G)
{
	delete G.vex;
	G.vex = NULL;
	for (int i = 0; i < G.vexnum; i++)
	{
		delete G.adjMatrix[i];
		G.adjMatrix[i] = NULL;
	}
	delete G.adjMatrix;
}

int main()
{
	MGraph G;
	cout << "创建有向图" << endl;
	CreateGraph(G, DG);	// 创建一个有向图
	PrintGraph(G);
	ClearGraph(G);
	cout << endl;

	cout << "创建无向图" << endl;
	CreateGraph(G, DN);	// 创建一个无向图
	PrintGraph(G);
	ClearGraph(G);
	cout << endl;

	return 0;
}