그림 - 인접 표 표시 (깊이 우선, 넓이 우선)

#include
#include
#include
#include
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_VERTEX_NUM 20//      

typedef int Status;
typedef int InfoType;
typedef char VertexType;

bool visited[MAX_VERTEX_NUM];

typedef struct ArcNode {
	int adjvex;//          
	struct ArcNode *nextarc;//         
	InfoType info;//         
}ArcNode;


typedef struct VNode {
	VertexType data;//    
	ArcNode *firstarc;//               
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {
	AdjList vertices;
	int vexnum, arcnum;//          
	int kind;//      
}ALGraph;

int LocateVex(ALGraph G, char v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.vertices[i].data == v)
			return i;
	}
	return -1;
}
/*
            ，     G
*/
Status CreateUDG(ALGraph &G)
{
	int i, j, k, IncInfo;
	ArcNode *pi, *pj;
	char v1, v2;
	cout << "     G.vexnum:";
	cin >> G.vexnum;
	cout << "    G.arcnum:";
	cin >> G.arcnum;
	getchar();
	for (i = 0; i < G.vexnum; ++i)
	{
		cout << "    G.vertices[" << i << "].data:";
		cin >> G.vertices[i].data;
		getchar();
		//          
		G.vertices[i].firstarc = NULL;
	}
	/*
	             
	*/
	for (k = 0; k < G.arcnum; ++k)
	{
		cout << "    " << k + 1 << "       :"<> v1;
		cin >> v2;
		getchar();
		//  V1 V2 G    
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		if (!(pi = (ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		//        "  "  
		pi->adjvex = j;
		pi->info = 0;
		//    G.vertices[i]
		pi->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = pi;
		
		if (!(pj = (ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		//        "  "  
		//    G.vertices[j]
		pj->adjvex = i;
		pj->info = 0;
		pj->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = pj;
	}//for
	return OK;
}//CreateUDG

//   
Status CreateDG(ALGraph &G)
{
	int i, j, k, IncInfo;
	ArcNode *pi, *pj;
	char v1, v2;
	cout << "     G.vexnum:";
	cin >> G.vexnum;
	cout << "    G.arcnum:";
	cin >> G.arcnum;
	getchar();
	for (i = 0; i < G.vexnum; ++i)
	{
		cout << "    G.vertices[" << i << "].data:";
		cin >> G.vertices[i].data;
		getchar();
		//          
		G.vertices[i].firstarc = NULL;
	}
	/*
	          
	*/
	for (k = 0; k < G.arcnum; ++k)
	{
		cout << "    " << k + 1 << "       :" << endl;
		//           
		cin >> v1;
		cin >> v2;
		getchar();
		//  V1 V2 G    
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		if (!(pi = (ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		//        "  "  
		pi->adjvex = j;
		pi->info = 0;
		//    G.vertices[i]
		pi->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = pi;
	}//for
	return OK;
}//CreateDG
//   
Status CreateDN(ALGraph &G)
{
	int i, j, k, IncInfo;
	ArcNode *pi, *pj;
	char v1, v2;
	cout << "     G.vexnum:";
	cin >> G.vexnum;
	cout << "    G.arcnum:";
	cin >> G.arcnum;
	cout << "     Info  （0、  ，1、 ）";
	cin >> IncInfo;
	getchar();
	for (i = 0; i < G.vexnum; ++i)
	{
		cout << "    G.vertices[" << i << "].data:";
		cin >> G.vertices[i].data;
		getchar();
		//          
		G.vertices[i].firstarc = NULL;
	}
	/*
	          
	*/
	for (k = 0; k < G.arcnum; ++k)
	{
		cout << "    " << k + 1 << "              :" << endl;
		//           
		cin >> v1;
		cin >> v2;
		cin >> IncInfo;
		getchar();
		//  V1 V2 G    
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		if (!(pi = (ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		//        "  "  
		pi->adjvex = j;
		//    G.vertices[i]
		pi->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = pi;
		
		pi->info = IncInfo;
	}//for
	return OK;
}//CreateDN
//   
Status CreateUDN(ALGraph &G)
{
	int i, j, k, IncInfo;
	ArcNode *pi, *pj;
	char v1, v2;
	cout << "     G.vexnum:";
	cin >> G.vexnum;
	cout << "    G.arcnum:";
	cin >> G.arcnum;
	cout << "     Info  （0、  ，1、 ）";
	cin >> IncInfo;
	getchar();
	for (i = 0; i < G.vexnum; ++i)
	{
		cout << "    G.vertices[" << i << "].data:";
		cin >> G.vertices[i].data;
		getchar();
		//          
		G.vertices[i].firstarc = NULL;
	}
	/*
	          
	*/
	for (k = 0; k < G.arcnum; ++k)
	{
		cout << "    " << k + 1 << "              :" << endl;
		//           
		cin >> v1;
		cin >> v2;
		cin >> IncInfo;
		getchar();
		//  V1 V2 G    
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		if (!(pi = (ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		//        "  "  
		pi->adjvex = j;
		//    G.vertices[i]
		pi->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = pi;
		pi->info = IncInfo;
		if (!(pj = (ArcNode *)malloc(sizeof(ArcNode))))
			exit(OVERFLOW);
		//        "  "  
		pj->adjvex = i;
		//    G.vertices[i]
		pj->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = pi;
		pj->info = IncInfo;
	}//for
	return OK;
}//CreateUDN


Status CreateGraph(ALGraph &G)
{
	cout << "       ：0  DG，1  DN，2  UDG，3  UDN" << endl;
	cin >> G.kind;
	switch (G.kind)
	{
	case 0:
		return CreateDG(G);
	case 1:
		return CreateDN(G);
	case 2:
		return CreateUDG(G);
	case 3:
		return CreateUDN(G);
	default:
		return ERROR;
	}
}

void list(ALGraph G)
{
	int i;
	ArcNode *p;
	cout << "     （（0）     ）：" << endl;
	for (i = 0; i < G.vexnum; ++i)
	{
		cout << i << "：" << G.vertices[i].data;
		p = G.vertices[i].firstarc;
		while (p)
		{
			cout << setw(3) << p->adjvex;
			cout << "(" <info<< ")";
			p = p->nextarc;
		}
		cout << endl;
	}
}


void DFS(ALGraph G, int v)
{
	ArcNode *p;
	int w;
	visited[v] = TRUE;
	cout << G.vertices[v].data << " ";
	
	for (p = G.vertices[v].firstarc; p; p = p->nextarc)
	{
		w = p->adjvex;
		if (!visited[w])// v          w    DFS
			DFS(G, w);
	}
}
//      
void DFSTraverse(ALGraph G)
{
	int v;
	for (v = 0; v < G.vexnum; ++v)
	{
		visited[v] = FALSE;
	}
	for (v = 0; v < G.vexnum; ++v)
	{
		if (!visited[v])
		{
			DFS(G, v);
			cout << endl;
		}
	}
}

void BFSTraverse(ALGraph G)
{
	int v,w;
	//    
	int front=0, rear = 0;
	VNode Queue[MAX_VERTEX_NUM];
	ArcNode *p;

	//       
	for (v = 0; v < G.vexnum; ++v)
	{
		visited[v] = FALSE;
	}
	for (v = 0; v < G.vexnum; ++v)
	{
		if (!visited[v])//v    
		{
			visited[v] =true;
			cout << G.vertices[v].data<nextarc)
				{
					w = p->adjvex;
					if (!visited[w])
					{
						visited[w] = true;
						cout << G.vertices[w].data << " ";
						Queue[++rear] = G.vertices[w];
					}//if
				}//for
			}//while
		}//if
	}//for
}//BFSTraverse

void main()
{
	ALGraph G;
	CreateGraph(G);
	list(G);
	//       
	cout << "      ：";
	DFSTraverse(G);
	cout << endl;
	//      
	cout << "      ：";
	BFSTraverse(G);
	system("pause");
}