인접 행렬 - 데이터 구조

3123 단어 데이터 구조
인접 행렬
#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "stdlib.h"
#include "windows.h"
#define OK  1
#define MVNum 100
#define MaxInt 32767
using namespace std;

typedef char VerType;
typedef int ArcType;

typedef struct {
	VerType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum, arcnum;
}AMGraph;

int visited[MaxInt] = { 0 };

void InitGraph(AMGraph &G);
int LocateVex(AMGraph G, VerType V);//    u   
void InsertVex(AMGraph &G, VerType V);//        v   
void InsertArc(AMGraph &G, VerType V, VerType U, ArcType W);//       
void DeleteArc(AMGraph &G, VerType V, VerType U);//     
void DeleteVex(AMGraph &G, VerType V);//      
void CreateUDN(AMGraph &G);//       
void DFS_AM(AMGraph G, VerType V);//       
void BFS_AM(AMGraph G, VerType V);//       

int main() {
	AMGraph G;
	InitGraph(G);
	CreateUDN(G);
	DFS_AM(G, 'a');
	system("pause");
	return 0;
}

void InitGraph(AMGraph & G)
{
	int i, j;
	G.vexnum = G.arcnum = 0;
	for (i = 0; i < MVNum; i++)
		for (j = 0; j < MVNum; j++)
			G.arcs[i][j] = MaxInt;
}

int LocateVex(AMGraph G, VerType V)
{
	for (int i = 0; i < G.vexnum; i++)
		if (G.vexs[i] == V)
			return i;
	return -1;
}

void InsertVex(AMGraph & G, VerType V)
{
	G.vexs[G.vexnum] = V;
	G.vexnum++;
}

void InsertArc(AMGraph & G, VerType V, VerType U, ArcType W)
{
	int i = LocateVex(G, V);
	int j = LocateVex(G, U);
	if (i == -1 || j == -1)
		return;
	G.arcs[i][j] = G.arcs[j][i] = W;
	G.arcnum++;
}

void DeleteArc(AMGraph & G, VerType V, VerType U)
{
	int i = LocateVex(G, V);
	int j = LocateVex(G, V);
	if (i == -1 || j == -1)
		return;
	G.arcs[i][j] = G.arcs[j][i] = MaxInt;
	G.arcnum--;
}

void DeleteVex(AMGraph & G, VerType V)
{
	int i, j, w, s = 0;
	i = LocateVex(G, V);
	if (i == ERROR)
		return;
	//     v     
	//   v         
	for (w = i; w < G.vexnum - 1; w++) {
		for (j = 0; j < G.vexnum; j++)
			if (G.arcs[w][j] < MaxInt)
				s++;
		G.arcs[w][j] = G.arcs[w + 1][j];
	}
	for (w = i; w < G.vexnum - 1; w++) {
		for (j = 0; j < G.vexnum; j++)
			G.arcs[j][w] = G.arcs[j][w + 1];
	}
	//           
	for (j = i; j < G.vexnum - 1; j++)
		G.vexs[j] = G.vexs[j + 1];
	G.vexnum--;
	G.arcnum -= s;
}

void CreateUDN(AMGraph & G)
{ //       
	int vexnum, arcnum, i;
	VerType V, U;
	ArcType W;
	cout << "             :" << endl;
	cin >> vexnum >> arcnum;
	cout << "   " << vexnum << "      :" << endl;
	for (i = 0; i < vexnum; i++) {
		cin >> V;
		InsertVex(G, V);
	}
	for (i = 0; i < arcnum; i++) {
		cout << "    " << i + 1 << "          :" << endl;
		cin >> V >> U >> W;
		InsertArc(G, V,U,W);
	}
}

void DFS_AM(AMGraph G, VerType V)
{//      
	int w, i = LocateVex(G, V);
	cout << V << " ";
	visited[i] = 1;
	for (w = 0; w < G.vexnum; w++) {
		if ((G.arcs[i][w] < MaxInt) && (visited[w] == 0))
			DFS_AM(G, G.vexs[w]);
	}
}

void BFS_AM(AMGraph G, VerType V)
{
}

좋은 웹페이지 즐겨찾기