데이터 구조의 무 방향 도 기본 조작 (인접 행렬 로 저장) - 엄 울 민 데이터 구 조 를 정리 합 니 다.

//                 
#include
using namespace std;
#define MAXVEX 100
typedef char VexType;

typedef struct ArcNode
{
	int adjvex;
	ArcNode *pNextArc;
}ArcNode;

typedef struct VexNode
{
	VexType data;
	ArcNode *pFirstArc;
}VexNode;

typedef struct
{
	VexNode VLnode[MAXVEX];
	int Vnums;
	int Anums;
}ALGraph;

int LocateVex(ALGraph G,VexNode v)
{
	int i;
	for (i = 0; i < G.Vnums; ++i)
	{
		if (G.VLnode[i].data == v.data)
			return i;
	}
	return -1;
}

void CreateGraph(ALGraph &G)
{
	int i, j, k;
	ArcNode *pA;
	cin >> G.Vnums >> G.Anums;
	for (i = 0; i < G.Vnums; ++i)
	{
		cin >> G.VLnode[i].data;
		G.VLnode[i].pFirstArc = NULL;
	}
	for (k = 0; k < G.Anums; ++k)
	{
		cin >> i >> j;//i!=j
		pA = new ArcNode;
		pA->adjvex = i;
		pA->pNextArc = G.VLnode[j].pFirstArc;
		G.VLnode[j].pFirstArc = pA;
		pA = new ArcNode;
		pA->adjvex = j;
		pA->pNextArc = G.VLnode[i].pFirstArc;
		G.VLnode[i].pFirstArc = pA;
	}
}

void DestroyGraph(ALGraph &G)
{
	int i;
	ArcNode *p, *q;
	for (i = 0; i < G.Vnums; ++i)
	{
		p = G.VLnode[i].pFirstArc;
		while (p)
		{
			q = p->pNextArc;
			delete p;
			p = q;
		}
		G.VLnode[i].pFirstArc = NULL;
	}
}

VexNode GetVex(ALGraph G, int i)
{
	if (i<0 || i>G.Vnums)
		exit(-1);
	return G.VLnode[i];
}

bool PutVex(ALGraph &G, int i, VexType value)
{
	int i;
	i = LocateVex(G, G.VLnode[i]);
	if (i > -1)
	{
		G.VLnode[i].data = value;
		return true;
	}
	else
		return false;
}

int FirstAdjVex(ALGraph G, VexNode v)
{
	int i;
	ArcNode *pA;
	i = LocateVex(G, v);
	pA = G.VLnode[i].pFirstArc;
	if (pA)
		return pA->adjvex;
	else
		return -1;
}

int NextAdjVex(ALGraph G, VexNode v, VexNode w)
{
	int i, j;
	i = LocateVex(G, v);
	j = LocateVex(G, w);
	ArcNode *pA = G.VLnode[i].pFirstArc;
	while (pA&&pA->adjvex != j)
		pA = pA->pNextArc;
	pA = pA->pNextArc;
	if (!pA || !(pA->pNextArc))
		return -1;
	else
		return pA->pNextArc->adjvex;
}

void InsertVex(ALGraph &G, VexNode v)
{
	G.VLnode[G.Vnums].data = v.data;
	G.VLnode[G.Vnums].pFirstArc = NULL;
	G.Vnums++;
}

bool InsertArc(ALGraph &G, VexNode v, VexNode w)
{
	int i, j;
	ArcNode *pA;
	i = LocateVex(G, v);
	j = LocateVex(G, w);
	pA = new ArcNode;
	pA->adjvex = i;
	pA = G.VLnode[j].pFirstArc;
	G.VLnode[j].pFirstArc = pA;
	pA->adjvex = j;
	pA = G.VLnode[i].pFirstArc;
	G.VLnode[i].pFirstArc = pA;
	G.Anums++;
}

bool DeleteVex(ALGraph &G, VexNode v)
{
	int i, j;
	ArcNode *p, *q;
	j = LocateVex(G, v); 
	if (j < 0)
		return false;
	p = G.VLnode[j].pFirstArc;
	while (p)
	{
		q = p->pNextArc;
		delete p;
		p = q;
		G.Anums--;
	}
	G.VLnode[j].pFirstArc = NULL;
	G.Vnums--;
	for (i = j; i < G.Vnums; ++i)
	{
		G.VLnode[i].data = G.VLnode[i + 1].data;
		G.VLnode[i].pFirstArc = G.VLnode[i + 1].pFirstArc;
	}
	for (i = 0; i < G.Vnums; ++i)
	{
		p = G.VLnode[i].pFirstArc;
		while (p)
		{
			if (p->adjvex == j)
			{
				if (p == G.VLnode[i].pFirstArc)
				{
					G.VLnode[i].pFirstArc = p->pNextArc;
					delete(p);
				}
				else
				{
					q->pNextArc = p->pNextArc;
					delete p;
					p = q->pNextArc;
				}
			}
			else
			{
				if (p->adjvex>j)
					p->adjvex--;
				q = p;
				p = p->pNextArc;
			}
		}
	}
}

bool DeleteArc(ALGraph &G, VexNode v, VexNode w)
{
	int i, j;
	ArcNode *p, *q;
	i = LocateVex(G, v);
	j = LocateVex(G, w);
	if (i < 0 || j < 0 || i == j)
		return false;
	p = G.VLnode[i].pFirstArc;
	while (p&&p->adjvex!=j)
	{				
		q = p;
		p = p->pNextArc;
	}
	if (p&&p->adjvex == j)
	{
		if (p == G.VLnode[i].pFirstArc)		
			G.VLnode[i].pFirstArc = p->pNextArc;			
		else		
			q->pNextArc = p->pNextArc;		
		delete p;
		G.Anums--;
	}
	p = G.VLnode[j].pFirstArc;
	while (p&&p->adjvex != i)
	{
		q = p;
		p = p->pNextArc;
	}
	if (p&&p->adjvex == i)
	{
		if (p == G.VLnode[j].pFirstArc)
			G.VLnode[j].pFirstArc = p->pNextArc;
		else
			q->pNextArc = p->pNextArc;	
			delete p;
	}
	return true;
}

void VisitVex(VexNode v)
{
	cout << v.data << " ";
}

void VisitArc(VexNode v, VexNode w)
{
	cout << "(" << v.data << "->" << w.data << ")" << " ";
}

void PrintGraph(ALGraph G)
{
	int i;
	ArcNode *pA;
	for (i = 0; i < G.Vnums; ++i)
		VisitVex(G.VLnode[i]);
	cout << endl;
	for (i = 0; i < G.Vnums; ++i)
	{
		pA = G.VLnode[i].pFirstArc;
		while (pA)
		{
			if (i < pA->adjvex)
				VisitArc(G.VLnode[i], G.VLnode[pA->adjvex]);
			pA = pA->pNextArc;
		}
	}
	cout << endl;
}

bool VisitTag[MAXVEX];

void DFS(ALGraph G, int i)
{
	int j;
	VisitTag[i] = true;
	VisitVex(G.VLnode[i]);
	for (j = FirstAdjVex(G, G.VLnode[i]); j >= 0;j=NextAdjVex(G,G.VLnode[i],G.VLnode[j]))
		if (!VisitTag[j])
			DFS(G, j);
}//      

void DFSEqual(ALGraph G, int i)//    
{
	ArcNode *pA;
	VisitTag[i] = true;
	VisitVex(G.VLnode[i]);
	pA = G.VLnode[i].pFirstArc;
	while (pA)
	{
		if (!VisitTag[pA->adjvex])
			DFSEqual(G, pA->adjvex);
		pA = pA->pNextArc;
	}
}

void DFST(ALGraph G)
{
	int i;
	for (i = 0; i < G.Vnums; ++i)
		VisitTag[i]=false;
	for (i = 0; i < G.Vnums; ++i)
		if (!VisitTag[i])
			DFS(G, i);
}

/****************BFS***************************/
#define QSIZE MAXVEX
typedef struct Queue
{
	int *pBase;
	int Front;
	int Rear;
}Queue;

void InitQueue(Queue &Q)
{
	Q.pBase = new int[QSIZE];
	Q.Front = 0;
	Q.Rear = 0;
}

void DestroyQueue(Queue &Q)
{
	delete[]Q.pBase;

	Q.pBase = NULL;
}

void ClearQueue(Queue &Q)
{
	Q.Front = 0;
	Q.Rear = 0;
}

bool QueueEmpty(Queue Q)
{
	if (Q.Rear == Q.Front)
		return true;
	else
		return false;
}

bool QueueFull(Queue Q)
{
	if ((Q.Rear + 1) % QSIZE == Q.Front)
		return true;
	else
		return false;
}

void EnQueue(Queue &Q, int i)
{
	if (QueueFull(Q))
		return;
	Q.pBase[Q.Rear] = i;
	Q.Rear = (Q.Rear + 1) % QSIZE;
}

void DeQueue(Queue &Q, int &i)
{
	if (QueueEmpty(Q))
		return;
	i = Q.pBase[Q.Front];
	Q.Front = (Q.Front + 1) % QSIZE;
}

void BFST(ALGraph G)
{
	int i;
	Queue Q;
	ArcNode *pA;
	for (i = 0; i < G.Vnums; ++i)
		VisitTag[i] = false;
	InitQueue(Q);
	for (i = 0; i < G.Vnums; ++i)
	{
		if (!VisitTag[i])
		{
			VisitTag[i] = true;
			VisitVex(G.VLnode[i]);
			EnQueue(Q, i);
			while (!QueueEmpty(Q))
			{
				DeQueue(Q, i);
				pA = G.VLnode[i].pFirstArc;
				while (pA)
				{
					if (!VisitTag[pA->adjvex])
					{
						VisitTag[pA->adjvex]=true;
						VisitVex(G.VLnode[pA->adjvex]);
						EnQueue(Q, pA->adjvex);
					}
					pA=pA->pNextArc;
				}				
			}
		}
	}
	DestroyQueue(Q);
}

/*********************************************/
int main(void)
{
	ALGraph G;
	CreateGraph(G);
	PrintGraph(G);
/*	DFST(G);
	cout << endl;
	BFST(G);
	cout << endl;
*/	return(0);
}