(데이터 구조) 그림 을 만 들 거나 인접 표 저장 소 는 정점 의 도 (입도, 출 도) 를 계산 하고 깊이 우선 또는 광 도 를 우선 으로 그림 을 옮 겨 다 니 는 것 을 나타 낸다.(컴 파일 러: VS)

#include 
#include 
#include 
#include 
#define TRUE  1
#define FALSE 0
#define ERROR 0
typedef int Status;
using namespace std;

#include "1.h"
#define  MAX_VERTEX 20
typedef  char  VertexType;
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
	VertexType data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX];
typedef struct
{
	AdjList vertices;
	int vexnum, arcnum;
	int kind;
}ALGraph;

//  
typedef int QElemtype;
#define MAXQSIZE 100
typedef struct
{
	QElemtype *base;
	int front;
	int rear;
}SqQueue;

#pragma once
#include "2.h"


Status LovateVex(ALGraph &G, VertexType v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vertices[i].data == v)
			return i;
	}
	
}
Status CreatDG(ALGraph &G)//     
{
	VertexType v1, v2;
	int j, k;
	ArcNode *p;
	cout << "         ：";
	cin >> G.vexnum >> G.arcnum;
	int i;
	cout << "         ：";
	for (i = 0; i < G.vexnum; i++)
	{
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc =NULL;
	}
	cout << "   ，      ：";
	for (i = 0; i < G.arcnum; i++)
	{
		cin >> v1 >> v2;
		j=LovateVex(G, v1);
		k = LovateVex(G, v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = k;
		p->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p;

	}
	return OK;


}
Status  CreatUDG(ALGraph &G)//     
{
	VertexType v1, v2;
	int j, k;
	ArcNode *p,*q;
	cout << "         ：";
	cin >> G.vexnum >> G.arcnum;
	int i;
	cout << "    ：";
	for (i = 0; i < G.vexnum; i++)
	{
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	cout << "   ，      ：";
	for (i = 0; i < G.arcnum; i++)
	{
		cin >> v1 >> v2;
		j = LovateVex(G, v1);
		k = LovateVex(G, v2);
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = k;
		p->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p;

		q= (ArcNode*)malloc(sizeof(ArcNode));
		q->adjvex = j;
		q->nextarc = G.vertices[k].firstarc;
		G.vertices[k].firstarc = q;


	}
	return OK;


}
Status GreatGraph(ALGraph &G)//           
{
	cout << "     :" << "0-DG,1-UDG" << endl;
	cin >> G.kind;
	switch (G.kind)
	{
	case 0:return CreatDG(G); break;
	case 1:return  CreatUDG(G); break;

	}

}
void PrintGraph(ALGraph G)//        
{
	ArcNode *p;
	cout << endl << "       ：" << G.vexnum << " " << G.arcnum;
	cout << endl << "     ：";
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		cout << " " << G.vertices[i].data;
	}
	cout << endl << "     ：";
	int j;//        
	for (i = 0; i < G.vexnum; i++)
	{
		cout << endl<< G.vertices[i].data << "    ：";
		p = G.vertices[i].firstarc;
		while (p)
		{
			j = p->adjvex;
			cout << " " << G.vertices[j].data;
			p = p->nextarc;
		}
		cout << endl;
	}
}
void FindOUTDegree(ALGraph G)//    
{
	int i;
	ArcNode *p;
	int count;
	cout << "        ：" << endl;
	for (i = 0; i < G.vexnum; i++)
	{
		count = 0;
		p = G.vertices[i].firstarc;
		while (p)
		{
			count++;
			p = p->nextarc;
		}
		cout << G.vertices[i].data << "：" << count;
		cout <adjvex];
			p = p->nextarc;
		}
	}
	int j;
	for (j = 0; j < G.vexnum; j++)
	{
		cout << G.vertices[j].data << " :" << indegree[j] << endl;
	}

	
}
bool visited[MAX_VERTEX];
void DFS(ALGraph G, int i)
{
	visited[i] =true;
	cout << G.vertices[i].data << endl;
	ArcNode *p;
	int w;
	p = G.vertices[i].firstarc;
	while (p)
	{
		w = p->adjvex;
		if (!visited[w])
			DFS(G, w);
		p = p->nextarc;
	}
}


void DFSTraverse(ALGraph G)//    
{
	int i;
	for (i = 0; i < G.vexnum; i++)
		visited[i] = false;
	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
			DFS(G, i);
	}
}
//    
#pragma once

Status InitQueue(SqQueue &Q)
{
	Q.base = (QElemtype*)malloc(MAXQSIZE * sizeof(QElemtype));
	if (!Q.base) return OVERFLOW;
	Q.front = Q.rear = 0;
	return OK;
}
Status EnQueue(SqQueue &Q, QElemtype e)
{
	if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;

}
Status DeQueue(SqQueue &Q, QElemtype &e)
{
	if (Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}
Status QueueEmpty(SqQueue Q)
{
	return Q.front == Q.rear;
}

void BFSTraverse(ALGraph G)//    
{
	bool visited[MAX_VERTEX];
	int i;
	int w;
	QElemtype e;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++)
		visited[i] = false;
	SqQueue Q;
	InitQueue(Q);
	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			cout << G.vertices[i].data << endl;
			EnQueue(Q, i);
			while (!QueueEmpty(Q))
			{
				DeQueue(Q, e);
				for (p = G.vertices[i].firstarc; p; p = p->nextarc)
				{
					w = p->adjvex;
					if (!visited[w])
					{
						visited[w] = true;
						cout << G.vertices[w].data << endl;
						EnQueue(Q,w);
					}
				}
			}

		}
	}
}

#include "3.h"
int main()
{
	ALGraph G;
	GreatGraph(G);
	PrintGraph(G);
	FindOUTDegree(G);
	FindINDegree(G);
	cout << "      ：" << endl;
	DFSTraverse(G);
	cout << "        ：" << endl;
	BFSTraverse(G);

	system("pause");

}