6-1

#include <iostream>
using namespace std;

#define MVNum 20   //¼ÙÉ赱ǰ¶¥µãÊý×î¶àΪ20¸ö
int visited[MVNum];//ÓÃÀ´´æ·Åµ±Ç°¶¥µãÊÇ·ñ±éÀú¹ý

//*****¶¨ÒåÁÚ½Ó¾ØÕó****
typedef char VerTexType;
typedef int ArcType;
typedef struct
{
	VerTexType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum,arcnum;
}AMGraph;

//Êä³öͼµÄÁÚ½Ó¾ØÕó
void PrintAMGraph(AMGraph MG){
	int i,j;
	if(MG.vexnum<=0)
		return;
	for(i=0; i<MG.vexnum; i++)
		cout<<MG.vexs[i];
	cout<<endl;

	for(i=0; i<MG.vexnum; i++){
		for(j=0; j<MG.vexnum; j++)
			cout<<MG.arcs[i][j];
		cout<<endl;
	}	
}

//ÈôGÖдæÔÚv,Ôò·µ»Ø¸Ã¶¥µãÔÚͼÖÐλÖÃ,·ñÔò·µ»Ø-1
int LocateVex(AMGraph G, char v)
{
	int i;
	for(i=0; i<G.vexnum; i++)
	{
    	if(G.vexs[i]==v)
       		return i;
	}
	return -1;
}

//·µ»Ø¶¥µãvµÄµÚÒ»¸öÁÙ½ÓµãλÖÃ,·ñÔò·µ»Ø-1
int FisrtAdjVertex(AMGraph G, int v)
{
	//--------²¹³ä´úÂë--Start------
	for (int i = 0; i < G.vexnum; i ++) {
		if (G.arcs[v][i] != 0) {
			return i;
		}
	}
	return -1;
	//--------²¹³ä´úÂë--End-------
}

//·µ»Ø¶¥µãvÏà¶ÔÓÚwµÄÏÂÒ»¸öÁÙ½ÓµãλÖÃ,·ñÔò·µ»Ø-1
int NextAdjVertex(AMGraph G, int v, int w)
{
	//--------²¹³ä´úÂë--Start------
	for (int i = w + 1; i < G.vexnum; i ++) {
		if (G.arcs[v][i] != 0) {
			return i;
		}
	}
	return -1;
	//--------²¹³ä´úÂë--End-------
}

//ÁÚ½Ó¾ØÕó´æ´¢·½Ê½½¨Á¢ÎÞÏòͼ
void CreateAMGraph(AMGraph &G)
{	
	/*
	step 1.ÊäÈëͼÖж¥µã×ÜÊýÓë±ßµÄ×ÜÊý
	step 2.ÊäÈëͼÖж¥µãÐÅÏ¢£¬´æ·Åµ½G.vexs[i]Êý×éÖÐ
	step 3.³õʼ»¯ÁÚ½Ó¾ØÕóÖÐËùÓÐֵΪ0
	step 4.ÊäÈë±ßµÄÐÅÏ¢£¬ÐÞ¸ÄÁÚ½Ó¾ØÕóÖÐÏà¶ÔÓ¦µÄÔªËØÖµ
	*/
	//--------²¹³ä´úÂë--Start------
	cin >> G.vexnum >> G.arcnum;
	for (int i = 0; i < G.vexnum; i ++) {
		cin >> G.vexs[i];
	}
	for (int i = 0; i < G.vexnum; i ++) {
		for (int j = 0; j < G.vexnum; j ++) {
			G.arcs[i][j] = 0;
		}
	}
	char a, b;
	int x, y;
	for (int i = 0; i < G.arcnum; i ++) {
		cin >> a >> b;
		x = LocateVex(G, a);
		y = LocateVex(G, b);
		if (x != -1 && y != -1) {
			G.arcs[x][y] = G.arcs[y][x] = 1;
		}
	}
	//--------²¹³ä´úÂë--End-------
}

//´ÓµÚi¸ö¶¥µã¿ªÊ¼Éî¶È±éÀú
void DFSAMGraph(AMGraph G,int i)
{	
	//--------²¹³ä´úÂë--Start------
	cout << G.vexs[i];
	visited[i] = 1;
	for (int w = FisrtAdjVertex(G, i); w != -1; w = NextAdjVertex(G, i, w)) {
		if (!visited[w]) {
			DFSAMGraph(G, w);
		}
	}
	//--------²¹³ä´úÂë--End-------
}

//´ÓµÚi¸ö¶¥µã¿ªÊ¼¹ã¶È±éÀú
void BFSAMGraph(AMGraph G,int i)
{
	//--------²¹³ä´úÂë--Start------
	int q[30], f = 1, r = 0;
	cout << G.vexs[i];
	visited[i] = 1;
	q[++ r] = i;
	while (f <= r) {
		int v = f;
		f ++;
		for (int w = FisrtAdjVertex(G, v); w != -1; w = NextAdjVertex(G, v, w)) {
			if (!visited[w]) {
				cout << G.vexs[w];
				visited[w] = 1;
				q[++ r] = w;
			}
		}
	}
	//--------²¹³ä´úÂë--End-------
}
/*
4 4
a b c d
a b
a c
b c
c d
*/
//Ö÷º¯Êý
int main()
{
	int i,select,vex;
	char start;
	AMGraph MG;
	MG.vexnum=MG.arcnum=0;
	
	while(cin>>select)
	{
		if(select==1){//Êä³öͼ
			PrintAMGraph(MG);
		}
		else if(select==2){//½¨Á¢ÎÞÏòͼ
			CreateAMGraph(MG);
		}
		else if(select==3){//Éî¶È±éÀú
			getchar();
			cin>>start;//±éÀúµÄÆðʼ¶¥µã
			vex = LocateVex(MG, start);
			for(i=0; i<MG.vexnum; i++)
				visited[i] = 0;
			DFSAMGraph(MG,vex);
			cout<<endl;
		}
		else if(select==4){//¹ã¶È±éÀú
			getchar();
			cin>>start;//±éÀúµÄÆðʼ¶¥µã
			vex = LocateVex(MG, start);
			for(i=0; i<MG.vexnum; i++)
				visited[i] = 0;
			BFSAMGraph(MG,vex);
			cout<<endl;
		}
	}
	return 0;
}

6-2

#include <iostream>
using namespace std;

#define MaxInt 32767		//´ú±íÎÞÇî´ó
#define MVNum 10			//¼ÙÉ赱ǰ¶¥µãÊý×î¶àΪ10¸ö
typedef char VerTexType;	//½áµãÊý¾ÝÀàÐÍ
int visited[MVNum];			//ÓÃÀ´´æ·Åµ±Ç°¶¥µãÊÇ·ñ±éÀú¹ý

//******¶¨ÒåÁÚ½Ó±í******
typedef struct ArcNode{			//±ß½áµã
	int adjvex;					//ÁÚ½ÓµãÔÚÊý×éÖеÄλÖÃ
	struct ArcNode *nextarc;	//Ö¸ÏòÏÂÒ»¸ö±ß½áµãµÄÖ¸Õë
	int weight;					//±ßµÄȨÖØ(>0)	
}ArcNode;
typedef struct VNode{			//±íÍ·½áµã
	VerTexType data;
	ArcNode *firstarc;
}VNode, AdjList[MVNum];
typedef struct{					//ÁÚ½Ó±í
	AdjList vexs; 
	int vexnum,arcnum;
}ALGraph; 

//ÈôGÖдæÔÚv,Ôò·µ»Ø¸Ã¶¥µãÔÚͼÖÐλÖÃ,·ñÔò·µ»Ø-1
int LocateVex(ALGraph G, char v){
	int i;
	for(i=0; i<G.vexnum; i++)
	{
    	if(G.vexs[i].data==v)
       		return i;
	}
	return -1;
}

//½¨Á¢ÁÚ½Ó±í´æ´¢·½Ê½µÄÓÐÏòÍø
void CreateALGraph(ALGraph &G)
{
	/*	1.ÊäÈëͼÖж¥µã×ÜÊýÓë±ßµÄ×ÜÊý
		2.ÊäÈëͼÖж¥µãÐÅÏ¢
		3.ÊäÈë±ßµÄÐÅÏ¢£¬½¨Á¢±ß½áµã£¬²åÈëµ½Ïà¶ÔÓ¦Êý×éÔªËغóµÄ±ß±íÖУ¨×¢£ºÓÐÏòÍøÖÐÿÌõ±ßÐèÒª²åÈëÁ½¸ö±ß½áµã£©¡£*/
	int i,j,k;
	char v1,v2;
	ArcNode *p, *q;
	int w;

	cin>>G.vexnum>>G.arcnum;
	for(i=0; i<G.vexnum; i++)
	{
		cin>>G.vexs[i].data;
		G.vexs[i].firstarc=NULL;
	}	
	//--------²¹³ä´úÂë--Start------
    for (int i = 0; i < G.arcnum; i ++) {
    	cin >> v1 >> v2 >> w;
    	int v1idx = LocateVex(G, v1);
    	int v2idx = LocateVex(G, v2);
    	p = new ArcNode;
    	p->adjvex = v2idx;
    	p->weight = w;
    	p->nextarc = G.vexs[v1idx].firstarc;
    	G.vexs[v1idx].firstarc = p;
	}

	//--------²¹³ä´úÂë--End------
}

//Éî¶È±éÀúÁÚ½Ó±í
void DFSALGraph(ALGraph G,int i)
{
	//--------²¹³ä´úÂë--Start------
	visited[i] = 1;
	cout << G.vexs[i].data;
	for (ArcNode *p = G.vexs[i].firstarc; p != NULL; p = p->nextarc) {
		if (!visited[p->adjvex]) {
			DFSALGraph(G, p->adjvex);
		}
	}
	//--------²¹³ä´úÂë--End------
}

//¼ÆËãͼÖÐËùÓбߵÄȨֵ֮ºÍ
int GetGraphWeight(ALGraph G)
{
	//--------²¹³ä´úÂë--Start------
	int ans = 0;
	for (int i = 0; i < G.vexnum; i ++) {
		for (ArcNode *p = G.vexs[i].firstarc; p != NULL; p = p->nextarc) {
			ans += p->weight;
		}
	}
	return ans;
	//--------²¹³ä´úÂë--End------
}

//¼ÆËãͼÖгö¶È´óÓÚÈë¶ÈµÄ½áµã¸öÊý
int GetNode(ALGraph G)
{
	//--------²¹³ä´úÂë--Start------
	int outNode[MVNum];
	int inNode[MVNum];
	int ans = 0;
	for (int i = 0; i < G.vexnum; i ++) {
		outNode[i] = inNode[i] = 0;
	}
	for (int i = 0; i < G.vexnum; i ++) {
		for (ArcNode *p = G.vexs[i].firstarc; p != NULL; p = p->nextarc) {
			outNode[i] ++;
			inNode[p->adjvex] ++;
		}
	}
	for (int i = 0; i < G.vexnum; i ++) {
		if (outNode[i] > inNode[i]) {
			ans ++;
		}
	}
	return ans;
	//--------²¹³ä´úÂë--End------
}

//Ö÷º¯Êý
int main()
{
	int i,select,vex;
	char start;
	ALGraph G;
	G.vexnum=G.arcnum=0;
	
	while(cin>>select)
	{
		if(select==1){//½¨Á¢ÓÐÏòÍø
			CreateALGraph(G);
		}
		else if(select==2){//Éî¶È±éÀú
			cin>>start;//±éÀúµÄÆðʼ¶¥µã
			vex = LocateVex(G, start);
			for(i=0; i<G.vexnum; i++)
				visited[i] = 0;
			DFSALGraph(G,vex);
			cout<<endl;
		}
		else if(select==3)//ÇóȨºÍ
			cout<<GetGraphWeight(G)<<endl;		
		else if(select==4)//Çó½áµãÊý
			cout<<GetNode(G)<<endl;		
	}
	return 0;
}