数据结构作业—图
本文最后更新于13 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com

第一题

已知一个无向图如下图所示,试给出该图的邻接矩阵和邻接表存储示意图(画图,分别用矩阵和数组链表图表示),并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写两种表示方法的存储结构、相关基本操作,并在主函数中创建该图。

#include<iostream>
using namespace std;

//定点类型 
typedef char VertexType;
//边上权值类型
typedef int EdgeType;
//最大顶点数
#define MAXVEX 100

//邻接矩阵表示法 
typedef struct {
	VertexType vexs[MAXVEX];	//顶点表
	EdgeType arc[MAXVEX][MAXVEX];	//邻接矩阵
	int numNodes;	//顶点数
	int numEdges;	//边数 
	
}MGraph;


//

//无向网图邻接矩阵表示法
void CreateMGraph(MGraph &G){
	int i,j,k,w;
	
	cout<<"请输入顶点数和边数:"<<endl;
	cin>>G.numNodes>>G.numEdges;
	
	//输入顶点信息,建立顶点表
	cout<<"请输入顶点信息:"<<endl;
	
	for(i=0;i<G.numNodes;i++){
		
		cin>>G.vexs[i];
		
	} 
	
	//初始化邻接矩阵
	for(k=0;k<G.numEdges;k++){
		cout<<"输入边(vi,vj)上的下表i,下表j:"<<endl;
		cin>>i>>j;
		G.arc[i-1][j-1]=1;
		G.arc[j-1][i-1] = G.arc[i-1][j-1];
	} 
} 

//输出该图 
void PrintMGraph(MGraph G){
	for(int i=0;i<G.numNodes;i++){
		for(int j=0;j<G.numNodes;j++){
			cout<<G.arc[i][j]<<" ";
		}
		cout<<endl;
	}
} 


int main(){
	MGraph G;
	CreateMGraph(G);
	PrintMGraph(G);
	
	return 0;
}
#include<iostream>
#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"
using namespace std;

typedef char VertexType;
typedef int EdgeType;

#define MAXVEX 100

//边表结点 
typedef struct EdgeNode{
	int adjvex;		//邻接点域,存储该顶点对应的下表
	EdgeType info;	//存储权值
	struct EdgeNode *next;	//链域,指向下一个邻接点 
}EdgeNode;

//顶点表结点 
typedef struct VertexNode{
	VertexType data;	//顶点域,存储顶点信息
	EdgeNode *firstedge;	//边表头指针 
}VertexNode,AdjList[MAXVEX];

typedef struct {
	AdjList adjList;
	int numNodes,numEdges;	//顶点数和边数 
}GraphAdjList;


//建立图的邻接表结构
void CreateALGraph(GraphAdjList *G){
	int i,j,k;
	EdgeNode *e;
	cout<<"输入顶点数和边数:"<<endl;
	cin>>G->numNodes>>G->numEdges;
	
	cout<<"请输入顶点信息"<<endl; 
	for(i=0;i<G->numNodes;i++){
		cin>>G->adjList[i].data;
		G->adjList[i].firstedge=NULL;
	} 
	
	for(k=0;k<G->numEdges;k++){
		cout<<"输入边(vi,vj)上的顶点序号:"<<endl;
		cin>>i>>j;
		e=(EdgeNode *)malloc(sizeof(EdgeNode));	//向内存申请空间,申请边表结点
		e->adjvex=j;
		e->next=G->adjList[i].firstedge;	//将e的指针指向当前顶点指向的结点
		G->adjList[i].firstedge=e;	//将当前顶点的指针指向e
		e=(EdgeNode*)malloc(sizeof(EdgeNode));	//向内存申请空间,生成边表结点
		e->adjvex=i;
		e->next=G->adjList[j].firstedge;	//将e的指针指向当前顶点指向的结点
		G->adjList[j].firstedge=e; 
	}
} 

void DispGraphAdjList(GraphAdjList *G)
{
	int i;
	EdgeNode *p;
	cout<<"图的邻接表表示如下"<<endl;
	printf("%6s%8s%12s\n","编号","顶点","相邻边编号");
 
	for(i=0;i< G->numNodes;i++)
	{
		printf("%4d %8c",i,G->adjList[i].data);
		for(p=G->adjList[i].firstedge;p!=NULL;p=p->next)
			printf("%4d",p->adjvex);
		printf("\n");
	}
}
int main(void)
{    
	GraphAdjList G;    
	CreateALGraph(&G);
	DispGraphAdjList(&G);
	
	return 0;
}

第二题

已知一个有向图如下图所示,试给出图的邻接矩阵和邻接表存储示意图(画图,分别用矩阵和数组链表图表示),并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写两种表示方法的存储结构、相关基本操作,并在主函数中创建该图。

#include<iostream>
using namespace std;

//定点类型 
typedef char VertexType;
//边上权值类型
typedef int EdgeType;
//最大顶点数
#define MAXVEX 100

//邻接矩阵表示法 
typedef struct {
	VertexType vexs[MAXVEX];	//顶点表
	EdgeType arc[MAXVEX][MAXVEX];	//邻接矩阵
	int numNodes;	//顶点数
	int numEdges;	//边数 
	
}MGraph;


//

//无向网图邻接矩阵表示法
void CreateMGraph(MGraph &G){
	int i,j,k,w;
	
	cout<<"请输入顶点数和边数:"<<endl;
	cin>>G.numNodes>>G.numEdges;
	
	//输入顶点信息,建立顶点表
	cout<<"请输入顶点信息:"<<endl;
	
	for(i=0;i<G.numNodes;i++){
		
		cin>>G.vexs[i];
		
	} 
	
	//初始化邻接矩阵
	for(k=0;k<G.numEdges;k++){
		cout<<"输入边(vi,vj)上的下表i,下表j:"<<endl;
		cin>>i>>j;
		G.arc[i-1][j-1]=1;
	} 
} 

void PrintMGraph(MGraph G){
	for(int i=0;i<G.numNodes;i++){
		for(int j=0;j<G.numNodes;j++){
			cout<<G.arc[i][j]<<" ";
		}
		cout<<endl;
	}
} 


int main(){
	MGraph G;
	CreateMGraph(G);
	PrintMGraph(G);
	
	return 0;
}
#include<iostream>
using namespace std;

#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"


#define MAXVEX 100 // 最大顶点数

typedef int Status;	//Status是函数的类型,其值是函数结果状态代码,如OK等
typedef char VertexType; //顶点类型应由用户定义 
typedef int EdgeType; // 边上的权值类型应由用户定义

// 边表结点  
typedef struct EdgeNode
{
	int adjvex;    // 邻接点域,存储该顶点对应的下标 
	//EdgeType info;		// 用于存储权值
	struct EdgeNode* next; // 链域,指向下一个邻接点 
}EdgeNode;

// 顶点表结点
typedef struct VertexNode
{
	VertexType data; //顶点域,存储顶点信息
	EdgeNode* firstedge;// 边表头指针 
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numNodes;	//顶点数
	int numEdges; // 边数 
}GraphAdjList;

//在图中查找顶点v,如果存在下表,不存在返回-1 
int locateVex(GraphAdjList G, VertexType v) {
	int i;
	for (i = 0; i < G.numNodes; i++) {
		if (G.adjList[i].data == v) {
			return i;
		}
	}
	return -1;
}
// 建立图的邻接表结构
void  CreateALGraph(GraphAdjList* G)
{
	int i, j, k;

	EdgeNode* s;
	cout << "请输入图中的顶点数和边数:" << endl;
	cin >> G->numNodes >> G->numEdges;

	cout << "请输入图中的定点信息:" << endl;
	for (i = 0; i < G->numNodes; i++) {
		cin >> G->adjList[i].data;
		G->adjList[i].firstedge = NULL;
	}
	VertexType v1, v2;
	cout << "请输入边相关的信息:" << endl;
	for (k = 0; k < G->numEdges; k++) {
		
		cout << "请输入第" << k + 1 << "条边的两个端点下表:" << endl;
		cin >> v1 >> v2;
		i = locateVex(*G, v1);
		j = locateVex(*G, v2);

		if (i >= 0 && j >= 0) {
			s = (EdgeNode*)malloc(sizeof(EdgeNode));
			s->adjvex = j;
			s->next = G->adjList[i].firstedge;
			G->adjList[i].firstedge = s;
		}
	}
}

void Print(GraphAdjList G) {
	int i;
	EdgeNode* p;
	cout << "图的邻接表表示法:" << endl;
	for (i = 0; i < G.numNodes; i++) {
		cout << G.adjList[i].data << " ";
		p = G.adjList[i].firstedge;
		while (p != NULL) {
			cout << "-->" << p->adjvex+1;
			p = p->next;
		}
		cout << endl;
	}
}
int main(void)
{
	GraphAdjList G;
	CreateALGraph(&G);
	Print(G);

	return 0;
}

第三题

已知一个连通图如下图所示,分别给出一个按深度优先遍历和广度优先遍历的顶点序列(假设从顶点v1出发)。并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写相关基本操作,并在主函数中求出深度优先序列和广度优先序列。

#include<iostream>
using namespace std;

//定点类型 
typedef char VertexType;
//边上权值类型
typedef int EdgeType;

typedef int Status; 
//最大顶点数
#define MAXVEX 100
#define MAXSIZE 9 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

bool visited[MAXVEX]; // 访问标志的数组 

//邻接矩阵表示法 
typedef struct {
	VertexType vexs[MAXVEX];	//顶点表
	EdgeType arc[MAXVEX][MAXVEX];	//邻接矩阵
	int numNodes;	//顶点数
	int numEdges;	//边数 
	
}MGraph;



// 循环队列的顺序存储结构 
typedef struct
{
	int data[MAXSIZE];
	int front;    	// 头指针 
	int rear;		// 尾指针,若队列不空,指向队列尾元素的下一个位置
}Queue;

//初始化一个空队列Q
Status InitQueue(Queue *Q)
{
	Q->front=0;
	Q->rear=0;
	return  OK;
}

// 若队列Q为空队列,则返回TRUE,否则返回FALSE 
Status QueueEmpty(Queue Q)
{ 
	if(Q.front==Q.rear) /* 队列空的标志 */
		return TRUE;
	else
		return FALSE;
}

// 若队列未满,则插入元素e为Q新的队尾元素 
Status EnQueue(Queue *Q,int e)
{	
	// 队列满的判断 
	if ((Q->rear+1)%MAXSIZE == Q->front)
		return ERROR;
	Q->data[Q->rear]=e;			// 将元素e赋值给队尾 
	Q->rear=(Q->rear+1)%MAXSIZE;// rear指针向后移一位置,若到最后则转到数组头部
								  
	return  OK;
}

// 若队列不空,则删除Q中队头元素,用e返回其值 
Status DeQueue(Queue *Q,int *e)
{	
	// 队列空的判断 
	if (Q->front == Q->rear)			
		return ERROR;
	*e=Q->data[Q->front];				// 将队头元素赋值给e
	Q->front=(Q->front+1)%MAXSIZE;	// front指针向后移一位置,若到最后则转到数组头部 
								
	return  OK;
}

//无向网图邻接矩阵表示法
void CreateMGraph(MGraph &G){
	int i,j,k,w;
	
	cout<<"请输入顶点数和边数:"<<endl;
	cin>>G.numNodes>>G.numEdges;
	
	//输入顶点信息,建立顶点表
	cout<<"请输入顶点信息:"<<endl;
	
	for(i=0;i<G.numNodes;i++){
		
		cin>>G.vexs[i];
		
	} 
	
	//初始化邻接矩阵
	for(k=0;k<G.numEdges;k++){
		cout<<"输入边(vi,vj)上的下表i,下表j:"<<endl;
		cin>>i>>j;
		G.arc[i-1][j-1]=1;
		G.arc[j-1][i-1] = G.arc[i-1][j-1];
	} 
} 

void PrintMGraph(MGraph G){
	for(int i=0;i<G.numNodes;i++){
		for(int j=0;j<G.numNodes;j++){
			cout<<G.arc[i][j]<<" ";
		}
		cout<<endl;
	}
} 



//邻接矩阵深度优先递归算法
void DFS(MGraph G,int i){
	int j;
	//访问过该顶点 
	visited[i]=TRUE;
	cout<<G.vexs[i];
	for(j=0;j<G.numNodes;j++){
		if(G.arc[i][j]==1&&!visited[j]){
			DFS(G,j);	//对未访问的邻接顶点递归调用 
		}
	}
	
} 
//邻接矩阵深度遍历操作
void DFSTraverse(MGraph G){
	int i;
	for(i=0;i<G.numNodes;i++){
		//初始化所有顶点状态都是未访问过 
		visited[i]=FALSE;
	} 
	for(i=0;i<G.numNodes;i++){
		//对未访问过的顶点调用DFS 
		if(!visited[i]){
			DFS(G,i);
		}
	}
} 


//邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G){
	int i,j;
	Queue Q;
	for(i=0;i<G.numNodes;i++){
		//初始化所有顶点均为访问过 
		visited[i]=FALSE;
	}
	InitQueue(&Q);
	for(i=0;i<G.numNodes;i++){
		if(!visited[i]){
			//设置当前顶点访问过 
			visited[i]=TRUE;
			cout<<G.vexs[i];//打印当前访问过的顶点
			EnQueue(&Q,i);//将此顶点入队列 
			while(!QueueEmpty(Q)){
				//将队首元素出队列,赋值给i 
				DeQueue(&Q,&i);
				for(j=0;j<G.numNodes;j++){
					if(G.arc[i][j]==1&&!visited[j]){
						visited[j]=TRUE;
						cout<<G.vexs[j];
						EnQueue(&Q,j);
					}
				}
			} 
		}
	}
} 
int main(){
	MGraph G;
	CreateMGraph(G);
	PrintMGraph(G);
	cout<<endl;
	cout<<"深度优先遍历:"<<endl; 
	DFSTraverse(G);
	cout<<endl;
	cout<<"广度优先遍历:"<<endl; 
	BFSTraverse(G);
	return 0;
} 
#include "stdio.h"    
#include "stdlib.h"   
#include<iostream>
using namespace std;
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

typedef char VertexType; /* 顶点类型应由用户定义 */   
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

/* 邻接矩阵结构 */
typedef struct
{
	VertexType vexs[MAXVEX]; //顶点表 
	EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵,可看作边表
	int numVertexes, numEdges; //图中当前的顶点数和边数 
}MGraph;

typedef struct EdgeNode // 边表结点
{
	int adjvex;    // 邻接点域,存储该顶点对应的下标 
	int weight;		// 用于存储权值,对于非网图可以不需要 
	struct EdgeNode *next; //链域,指向下一个邻接点
}EdgeNode;

typedef struct VertexNode // 顶点表结点 */ 
{
	int in;	//顶点入度 
	char data; // 顶点域,存储顶点信息 
	EdgeNode *firstedge;// 边表头指针  
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList; 
	int numVertexes,numEdges; // 图中当前顶点数和边数
}graphAdjList,*GraphAdjList;



//循环队列的顺序存储结构 
typedef struct
{
	int data[MAXSIZE];
	int front;    	// 头指针
	int rear;		//尾指针,若队列不空,指向队列尾元素的下一个位置 
}Queue;

// 初始化一个空队列Q 
int InitQueue(Queue *Q)
{
	Q->front=0;
	Q->rear=0;
	return  OK;
}

// 若队列Q为空队列,则返回TRUE,否则返回FALSE 
int QueueEmpty(Queue Q)
{ 
	if(Q.front==Q.rear) 
		return TRUE;
	else
		return FALSE;
}

// 若队列未满,则插入元素e为Q新的队尾元素 
int EnQueue(Queue *Q,int e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	// 队列满的判断 
		return ERROR;
	Q->data[Q->rear]=e;			// 将元素e赋值给队尾 
	Q->rear=(Q->rear+1)%MAXSIZE;// rear指针向后移一位置,若到最后则转到数组头部
								 
	return  OK;
}

//若队列不空,则删除Q中队头元素,用e返回其值 
int DeQueue(Queue *Q,int *e)
{
	if (Q->front == Q->rear)		
		return ERROR;
	*e=Q->data[Q->front];				//将队头元素赋值给e 
	Q->front=(Q->front+1)%MAXSIZE;	// front指针向后移一位置,若到最后则转到数组头部 
									
	return  OK;
}




void CreateMGraph(MGraph *G)
{
	int i, j;

	G->numEdges=15;
	G->numVertexes=9;

	// 读入顶点信息,建立顶点表 
	G->vexs[0]='1';
	G->vexs[1]='2';
	G->vexs[2]='3';
	G->vexs[3]='4';
	G->vexs[4]='5';
	G->vexs[5]='6';


	for (i = 0; i < G->numVertexes; i++)
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			//初始化图
			G->arc[i][j]=0;
		}
	}

	G->arc[0][1]=1;
	G->arc[0][3]=1;

	G->arc[0][5]=1; 
//	G->arc[1][0]=1; 
	G->arc[1][2]=1; 
	
	G->arc[1][3]=1; 
	G->arc[1][4]=1; 
	
//	G->arc[2][1]=1;
	G->arc[2][4]=1;
//	G->arc[3][0]=1;
//	G->arc[3][1]=1;

	G->arc[3][4]=1;
	G->arc[3][5]=1;

//	G->arc[4][1]=1; 
//	
//	G->arc[4][2]=1; 
//	G->arc[4][3]=1;
//	
//	G->arc[5][0]=1;
//	G->arc[5][3]=1;

	
	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}

}
 
//利用邻接矩阵构建邻接表 
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
	int i,j;
	EdgeNode *e;

	*GL = (GraphAdjList)malloc(sizeof(graphAdjList));

	(*GL)->numVertexes=G.numVertexes;
	(*GL)->numEdges=G.numEdges;
	for(i= 0;i <G.numVertexes;i++) //读入顶点信息,建立顶点表   
	{
		(*GL)->adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	// 将边表置为空表 
	}
	
	for(i=0;i<G.numVertexes;i++) // 建立边表 
	{ 
		for(j=G.numVertexes-1;j>=0;j--)
		{
			if (G.arc[i][j]==1)
			{
				e=(EdgeNode *)malloc(sizeof(EdgeNode));
				
				//下面6句代码仅仅只是为了与图书中的206页图匹配,让生成的队列符合书中图示。
				//实际构建无需这样,只需理解当前就是构建一个图结构的邻接表即可
				if (i==1 && j==8) 
					e->adjvex=6;
				else if (i==1 && j==6) 
					e->adjvex=8;
				else
					e->adjvex=j;					/* 邻接序号为j */    

				//正常代码下如下
				//e->adjvex=j;					/* 邻接序号为j */   
				
				e->next=(*GL)->adjList[i].firstedge;	/* 将当前顶点上的指向的结点指针赋值给e */
				(*GL)->adjList[i].firstedge=e;		/* 将当前顶点的指针指向e */   
				(*GL)->adjList[j].in++;
				
			}
		}
	}	
}

Boolean visited[MAXSIZE]; // 访问标志的数组

// 邻接表的深度优先递归算法 
void DFS(GraphAdjList GL, int i)
{
	EdgeNode *p;
 	visited[i] = TRUE;
 	
 	cout<<GL->adjList[i].data<<endl;
	p = GL->adjList[i].firstedge;
	while(p)
	{
 		if(!visited[p->adjvex])
 			DFS(GL, p->adjvex);//对为访问的邻接顶点递归调用
		p = p->next;
 	}
}

// 邻接表的深度遍历操作 
void DFSTraverse(GraphAdjList GL)
{
	int i;
 	for(i = 0; i < GL->numVertexes; i++)
 		visited[i] = FALSE; //初始所有顶点状态都是未访问过状态 
	for(i = 0; i < GL->numVertexes; i++)
 		if(!visited[i]) //对未访问过的顶点调用DFS,若是连通图,只会执行一次
			DFS(GL, i);
}

//邻接表的广度遍历算法 
void BFSTraverse(GraphAdjList GL)
{
	int i;
    EdgeNode *p;
	Queue Q;
	for(i = 0; i < GL->numVertexes; i++){
			visited[i] = FALSE;
	}
       
    InitQueue(&Q);
   	for(i = 0; i < GL->numVertexes; i++)
   	{
		if (!visited[i])
		{
			visited[i]=TRUE;
			
			cout<<GL->adjList[i].data<<endl; 
			EnQueue(&Q,i);
			while(!QueueEmpty(Q))
			{
				DeQueue(&Q,&i);
				p = GL->adjList[i].firstedge;	// 找到当前顶点的边表链表头指针 
				while(p)
				{
					if(!visited[p->adjvex])	// 若此顶点未被访问 
 					{
 						visited[p->adjvex]=TRUE;
						cout<<GL->adjList[p->adjvex].data<<endl;
						EnQueue(&Q,p->adjvex);	// 将此顶点入队列 
					}
					p = p->next;	//指针指向下一个邻接点 
				}
			}
		}
	}
}

int main(void)
{    
	MGraph G;  
	GraphAdjList GL;    
	CreateMGraph(&G);
	CreateALGraph(G,&GL);

	cout<<"深度优先遍历:"<<endl;
	DFSTraverse(GL);
	cout<<"广度优先遍历:"<<endl;
	BFSTraverse(GL);
	return 0;
}

第四题

基于深度优先搜索算法,写出求无向图所有连通子图的算法,并求连通分量。

提示:对于无向图,从任一个顶点出发进行DFS遍历,当本次遍历完成后,其所访问的结点构成一个连通子图;如果还存在没有访问过的结点,则从中任一个结点出发进行DFS遍历,……,直到所有结点都被访问。每一次调用DFS后都得到此非连通图的一个连通子图,调用DFS的次数就是连通子图的个数。

#include<iostream>
using namespace std;

typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100 
#define TRUE 1
#define FALSE 0 
bool visited[MAXVEX];

//邻接矩阵结构
typedef struct{
	VertexType vexs[MAXVEX];	//顶点表
	EdgeType arc[MAXVEX][MAXVEX];	//邻接矩阵
	int numNodes;	//顶点数 
	int numEdges; 	//边数 
}MGraph;

//建立无向网图的邻接矩阵表示
void CreateMGraph(MGraph *G){
	int i,j,k,w;
	cout<<"请输入顶点数和边数:"<<endl;
	cin>>G->numNodes>>G->numEdges;
	
	cout<<"请输入定点信息:"<<endl;
	for(i=0;i<G->numNodes;i++){
		cin>>G->vexs[i];
	} 
	
	
	//初始化邻接矩阵 
	for(i=0;i<G->numNodes;i++){
		for(j=0;j<G->numNodes;j++){
			G->arc[i][j]=0;
		}
	}
	
	for(k=0;k<G->numEdges;k++){
		cout<<"请输入(vi,vj)的下表i和j:"<<endl;
		cin>>i>>j;
		G->arc[i][j]=1; 
		G->arc[i][j]=G->arc[j][i];
	}
}  
int count=0;

//邻接矩阵的深度优先递归算法
void DFS(MGraph G,int i){
	int j;
	visited[i]=TRUE;
	cout<<G.vexs[i]<<endl;
	for(j=0;j<G.numNodes;j++){
		if(G.arc[i][j]==1&&!visited[j]){
			//对于未访问过的邻接顶点递归调用
			
			DFS(G,j); 
			
		}
	} 
} 

//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
	int i;
	for(i=0;i<G.numNodes;i++){
		//初始化所有顶点都是未访问过的状态 
		visited[i]=FALSE;
	}
	for(i=0;i<G.numNodes;i++){
		if(!visited[i]){
			count++;
			DFS(G,i);
		}
	}
	
} 

int main(){
	MGraph G;
	CreateMGraph(&G);
	DFSTraverse(G);
	cout<<"连通子图个数:"<<count<<endl;
	return 0;
}

第五题

已知如下图所示的AOE网,顶点表示事件,弧及权重表示活动的时间(单位为天)。找出关键路径,并求出事件v3的最早开始时间,然后编程实现。

#include <stdio.h>
#include <stdlib.h>
#define  MAX_VERTEX_NUM 20//最大顶点个数
#define  VertexType int//顶点数据的类型
//typedef enum{false,true} bool;
//建立全局变量,保存边的最早开始时间
VertexType ve[MAX_VERTEX_NUM];
//建立全局变量,保存边的最晚开始时间
VertexType vl[MAX_VERTEX_NUM];
typedef struct ArcNode{
    int adjvex;//邻接点在数组中的位置下标
    struct ArcNode * nextarc;//指向下一个邻接点的指针
    VertexType dut;
}ArcNode;

typedef struct VNode{
    VertexType data;//顶点的数据域
    ArcNode * firstarc;//指向邻接点的指针
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组

typedef struct {
    AdjList vertices;//图中顶点及各邻接点数组
    int vexnum,arcnum;//记录图中顶点数和边或弧数
}ALGraph;
//找到顶点对应在邻接表数组中的位置下标
int LocateVex(ALGraph G,VertexType u){
    for (int i=0; i<G.vexnum; i++) {
        if (G.vertices[i].data==u) {
            return i;
        }
    }
    return -1;
}
//创建AOE网,构建邻接表
void CreateAOE(ALGraph **G){
    *G=(ALGraph*)malloc(sizeof(ALGraph));
   
    scanf("%d,%d",&((*G)->vexnum),&((*G)->arcnum));
    for (int i=0; i<(*G)->vexnum; i++) {
        scanf("%d",&((*G)->vertices[i].data));
        (*G)->vertices[i].firstarc=NULL;
    }
    VertexType initial,end,dut;
    for (int i=0; i<(*G)->arcnum; i++) {
        scanf("%d,%d,%d",&initial,&end,&dut);
       
        ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=LocateVex(*(*G), end);
        p->nextarc=NULL;
        p->dut=dut;
       
        int locate=LocateVex(*(*G), initial);
        p->nextarc=(*G)->vertices[locate].firstarc;
        (*G)->vertices[locate].firstarc=p;
    }
}
//结构体定义栈结构
typedef struct stack{
    VertexType data;
    struct stack * next;
}stack;

stack *T;

//初始化栈结构
void initStack(stack* *S){
    (*S)=(stack*)malloc(sizeof(stack));
    (*S)->next=NULL;
}
//判断栈是否为空
bool StackEmpty(stack S){
    if (S.next==NULL) {
        return true;
    }
    return false;
}
//进栈,以头插法将新结点插入到链表中
void push(stack *S,VertexType u){
    stack *p=(stack*)malloc(sizeof(stack));
    p->data=u;
    p->next=NULL;
    p->next=S->next;
    S->next=p;
}
//弹栈函数,删除链表首元结点的同时,释放该空间,并将该结点中的数据域通过地址传值给变量i;
void pop(stack *S,VertexType *i){
    stack *p=S->next;
    *i=p->data;
    S->next=S->next->next;
    free(p);
}
//统计各顶点的入度
void FindInDegree(ALGraph G,int indegree[]){
    //初始化数组,默认初始值全部为0
    for (int i=0; i<G.vexnum; i++) {
        indegree[i]=0;
    }
    //遍历邻接表,根据各链表中结点的数据域存储的各顶点位置下标,在indegree数组相应位置+1
    for (int i=0; i<G.vexnum; i++) {
        ArcNode *p=G.vertices[i].firstarc;
        while (p) {
            indegree[p->adjvex]++;
            p=p->nextarc;
        }
    }
}

bool TopologicalOrder(ALGraph G){
    int indegree[G.vexnum];//创建记录各顶点入度的数组
    FindInDegree(G,indegree);//统计各顶点的入度
    //建立栈结构,程序中使用的是链表
    stack *S;
    //初始化栈
    initStack(&S);
    for (int i=0; i<G.vexnum; i++) {
        ve[i]=0;
    }
    //查找度为0的顶点,作为起始点
    for (int i=0; i<G.vexnum; i++) {
        if (!indegree[i]) {
            push(S, i);
        }
    }
    int count=0;
    //栈为空为结束标志
    while (!StackEmpty(*S)) {
        int index;
        //弹栈,并记录栈中保存的顶点所在邻接表数组中的位置
        pop(S,&index);
        //压栈,为求各边的最晚开始时间做准备
        push(T, index);
        ++count;
        //依次查找跟该顶点相链接的顶点,如果初始入度为1,当删除前一个顶点后,该顶点入度为0
        for (ArcNode *p=G.vertices[index].firstarc; p ; p=p->nextarc) {
           
            VertexType k=p->adjvex;
           
            if (!(--indegree[k])) {
                //顶点入度为0,入栈
                push(S, k);
            }
            //如果边的源点的最长路径长度加上边的权值比汇点的最长路径长度还长,就覆盖ve数组中对应位置的值,最终结束时,ve数组中存储的就是各顶点的最长路径长度。
            if (ve[index]+p->dut>ve[k]) {
                ve[k]=ve[index]+p->dut;
            }
        }
    }
    //如果count值小于顶点数量,表明有向图有环
    if (count<G.vexnum) {
        printf("该图有回路");
        return false;
    }
    return true;
}
//求各顶点的最晚发生时间并计算出各边的最早和最晚开始时间
void CriticalPath(ALGraph G){
    if (!TopologicalOrder(G)) {
        return ;
    }
    for (int i=0 ; i<G.vexnum ; i++) {
        vl[i]=ve[G.vexnum-1];
    }
    int j,k;
    while (!StackEmpty(*T)) {
        pop(T, &j);
        for (ArcNode* p=G.vertices[j].firstarc ; p ; p=p->nextarc) {
            k=p->adjvex;
            //构建Vl数组,在初始化时,Vl数组中每个单元都是18,如果每个边的汇点-边的权值比源点值小,就保存更小的。
            if (vl[k]-p->dut<vl[j]) {
                vl[j] = vl[k]-p->dut;
            }
        }
    }
    for (j = 0; j < G.vexnum; j++) {
        for (ArcNode*p = G.vertices[j].firstarc; p ;p = p->nextarc) {
            k = p->adjvex;
            //求各边的最早开始时间e[i],等于ve数组中相应源点存储的值
            int ee = ve[j];
            //求各边的最晚开始时间l[i],等于汇点在vl数组中存储的值减改边的权值
            int el = vl[k]-p->dut;
            //判断e[i]和l[i]是否相等,如果相等,该边就是关键活动,相应的用*标记;反之,边后边没标记
            char tag = (ee==el)?'*':' ';
            printf("%3d%3d%3d%3d%3d%2c\n",j,k,p->dut,ee,el,tag);
        }
    }
}
int main(){
    ALGraph *G;
    CreateAOE(&G);//创建AOE网
    initStack(&T);
    TopologicalOrder(*G);
    CriticalPath(*G);
    return  0;
}

第六题

已知一个图的顶点集V和边集G分别为V={0, 1, 2, 3, 4, 5, 6, 7, 8},E={<0, 1>, <0, 2>, <1, 3>, <1, 4>, <2, 4>, <2, 5>, <3, 6>, <3, 7>, <4, 7>, <4, 8>, <5, 7>, < 6, 7>, <7, 8>},若采用邻接表存储,并且每个顶点邻接表中的边结点都是按照终点序号从大到小的次序连接的,则按照拓扑排序算法,写出得到的拓扑序列,并编程实现。


#include<iostream>
#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"
using namespace std;
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 30#define GRAPH_INFINITY 65535



//图的邻接矩阵结构 
typedef struct {
	VertexType vexs[MAXVEX];	//顶点表
	EdgeType arc[MAXVEX][MAXVEX];	//邻接矩阵,相当于边表 
	int numNodes;	//顶点数
	int numEdges;	//边数 
}MGraph; 


//图的邻接表结构
//边表结点 
typedef struct EdgeNode{
	int adjvex;	//邻接点域
	int weight;	//存储权值
	struct EdgeNode *next;	//链域,存储下一个邻接点 
}EdgeNode;


//顶点表结点
typedef struct VertexNode{
	int in;	//顶点入度 
	int data;	//顶点域,存储顶点信息
	EdgeNode *firstedge;	//边表头指针 
}VertexNode,AdjList[MAXVEX];

typedef struct {
	AdjList adjList;
	int numVertexes;	//顶点数 
	int numEdges;	//边数 
}graphAdjList,*GraphAdjList;

void CreateMGraph(MGraph *G){
	G->numNodes=9;
	G->numEdges=8;
	//初始化顶点
	//V={0, 1, 2, 3, 4, 5, 6, 7, 8}
	for(int i=0;i<G->numNodes;i++){
		G->vexs[i]=i;
	} 
	//<0, 1>, <0, 2>, <1, 3>, <1, 4>, <2, 4>, <2, 5>, <3, 6>, <3, 7>, <4, 7>, <4, 8>, <5, 7>, < 6, 7>, <7, 8>
	for (int i = 0; i < G->numNodes; i++)/* 初始化图 */
	{
		for ( int j = 0; j < G->numNodes; j++)
		{
				G->arc[i][j]=0;
		}
	}
	
	G->arc[0][1]=1;
	G->arc[0][2]=1;
	G->arc[1][3]=1;
	G->arc[1][4]=1;
	G->arc[2][4]=1;
	G->arc[2][5]=1;
	G->arc[3][6]=1;
	G->arc[3][7]=1;
	G->arc[4][7]=1;
	G->arc[4][8]=1;
	G->arc[5][7]=1;
	G->arc[6][7]=1;
	G->arc[7][8]=1; 
}


// 利用邻接矩阵构建邻接表 
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
	int i,j;
	EdgeNode *e;

	*GL = (GraphAdjList)malloc(sizeof(graphAdjList));

	(*GL)->numVertexes=G.numNodes;
	(*GL)->numVertexes=G.numEdges;
	for(i= 0;i <G.numNodes;i++) /* 读入顶点信息,建立顶点表 */
	{
		(*GL)->adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	/* 将边表置为空表 */
	}
	
	for(i=0;i<G.numNodes;i++) /* 建立边表 */
	{ 
		for(j=0;j<G.numNodes;j++)
		{
			if (G.arc[i][j]!=0 && G.arc[i][j]<GRAPH_INFINITY)
			{
				e=(EdgeNode *)malloc(sizeof(EdgeNode));
				e->adjvex=j;					/* 邻接序号为j */   
				e->weight=G.arc[i][j];
				e->next=(*GL)->adjList[i].firstedge;	/* 将当前顶点上的指向的结点指针赋值给e */
				(*GL)->adjList[i].firstedge=e;		/* 将当前顶点的指针指向e  */  
				(*GL)->adjList[j].in++;
				
			}
		}
	}
	
}
//拓扑排序,若GL无回路,则输出拓扑排序序列并返回1,若有回路返回0
int TopologicalSort(GraphAdjList GL)
{    
	EdgeNode *e;    
	int i,k,gettop;   
	int top=0;  // 用于栈指针下标  
	int count=0;// 用于统计输出顶点的个数  
	int *stack;	// 建栈将入度为0的顶点入栈   
	stack=(int *)malloc(GL->numVertexes * sizeof(int) );    

	for(i = 0; i<GL->numVertexes; i++)                
		if(0 == GL->adjList[i].in) // 将入度为0的顶点入栈         
			stack[++top]=i;    
	while(top!=0)    
	{        
		gettop=stack[top--];        
		printf("%d -> ",GL->adjList[gettop].data);        
		count++;        //输出i号顶点,并计数     
		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
		{            
			k=e->adjvex;            
			if( !(--GL->adjList[k].in) )  //将i号顶点的邻接点的入度减1,如果减1后为0,则入栈             
				stack[++top]=k;        
		}
	}   
	printf("\n");   
	
	if(count < GL->numVertexes)        
		return ERROR;    
	else       
		return OK;
}


int main(void)
{    
	MGraph G;  
	GraphAdjList GL; 
	int result;   
	CreateMGraph(&G);
	CreateALGraph(G,&GL);
	result=TopologicalSort(GL);
	cout<<"result:"<<result<<endl;


	return 0;
}

第七题

如下图所示的有向网络,利用Dijkstra算法求从顶点v1到其他各顶点的最短路径(要求写出如教材所示的Dijkstra算法的执行过程),并编程验证。

#include<iostream>
using namespace std;


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535

typedef struct{
	int vexs[MAXVEX];
	int arc[MAXVEX][MAXVEX];
	int numVertexes;
	int numEdges;
}MGraph;

typedef int Patharc[MAXVEX];	//用于存储最短路径下表的数组 
typedef int ShortPathTable[MAXVEX]; //用于存储到各点最短路径的权值和


//按照图中所示构造 
void CreateMGraph(MGraph *G)
{
	int i, j;


	G->numEdges=11;
	G->numVertexes=6;

	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		G->vexs[i]=i;
	}

	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			if (i==j)
				G->arc[i][j]=0;
			else
				G->arc[i][j] = G->arc[j][i] = 65535;
		}
	}

	G->arc[0][1]=45;
	G->arc[0][2]=15; 
	G->arc[0][4]=15; 
	G->arc[1][4]=15; 
	G->arc[2][0]=10; 
	G->arc[2][1]=10;
	G->arc[2][3]=60;
	G->arc[3][1]=30;
	G->arc[3][5]=20; 



//	for(i = 0; i < G->numVertexes; i++)
//	{
//		for(j = i; j < G->numVertexes; j++)
//		{
//			G->arc[j][i] =G->arc[i][j];
//		}
//	}

} 

void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{    
	int v,w,k,min;    
	int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */
	for(v=0; v<G.numVertexes; v++)    /* 初始化数据 */
	{        
		final[v] = 0;			/* 全部顶点初始化为未知最短路径状态 */
		(*D)[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */
		(*P)[v] = -1;				/* 初始化路径数组P为-1  */       
	}

	(*D)[v0] = 0;  /* v0至v0路径为0 */  
	final[v0] = 1;    /* v0至v0不需要求路径 */        
	/* 开始主循环,每次求得v0到某个v顶点的最短路径 */   
	for(v=1; v<G.numVertexes; v++)   
	{
		min=65535;    /* 当前所知离v0顶点的最近距离 */        
		for(w=0; w<G.numVertexes; w++) /* 寻找离v0最近的顶点 */    
		{            
			if(!final[w] && (*D)[w]<min)             
			{                   
				k=w;                    
				min = (*D)[w];    /* w顶点离v0顶点更近 */            
			}        
		}        
		final[k] = 1;    /* 将目前找到的最近的顶点置为1 */
		for(w=0; w<G.numVertexes; w++) /* 修正当前最短路径及距离 */
		{
			/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
			if(!final[w] && (min+G.arc[k][w]<(*D)[w]))   
			{ /*  说明找到了更短的路径,修改D[w]和P[w] */
				(*D)[w] = min + G.arc[k][w];  /* 修改当前路径长度 */               
				(*P)[w]=k;        
			}       
		}   
	}
}


int main()
{   
	int i,j,v0;
	MGraph G;    
	Patharc P;    
	ShortPathTable D; /* 求某点到其余各点的最短路径 */   
	v0=0;
	
	CreateMGraph(&G);
	
	ShortestPath_Dijkstra(G, v0, &P, &D);  

	printf("最短路径如下:\n");    
	for(i=1;i<G.numVertexes;++i)   
	{       
		printf("v%d - v%d : ",v0,i);
		j=i;
		while(P[j]!=-1)
		{
			printf("%d ",P[j]);
			j=P[j];
		}
		
		printf("\n");
	}    
	printf("\n源点到各顶点的最短路径长度为:\n");  
	for(i=1;i<G.numVertexes;++i)        
		printf("v%d - v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);     
	return 0;
}

第八题

应用Floyd算法,编程求下图所示有向图的每对顶点之间的最短路径(写出相应的矩阵),并求该图的中心点。并利用Warshall算法,编程求该图的传递闭包(矩阵)。

第九题

下图是一个无向带权图,请给出该图的邻接矩阵,并分别按Prim算法和Kruskal算法求最小生成树(包括算法代码和画图)。

#include<iostream>
using namespace std;
 
#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define GRAPH_INFINITY 65535


typedef struct
{
	int arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;

//按照图构造 
void CreateMGraph(MGraph *G)
{
	int i, j;

	G->numEdges=8;
	G->numVertexes=6;

	for (i = 0; i < G->numVertexes; i++)
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			if (i==j)
				G->arc[i][j]=0;
			else
				G->arc[i][j] = G->arc[j][i] = GRAPH_INFINITY;
		}
	}

	G->arc[0][1]=6;
	G->arc[0][2]=3; 
	G->arc[1][3]=1; 
	G->arc[1][5]=5; 
	G->arc[2][3]=6; 
	G->arc[2][4]=6; 
	G->arc[3][5]=5;  
	G->arc[4][5]=2;

	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}

}

// Prim算法生成最小生成树 
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];		/* 保存相关顶点下标 */
	int lowcost[MAXVEX];	/* 保存相关顶点间边的权值 */
	lowcost[0] = 0;/* 初始化第一个权值为0,即v0加入生成树 */
			/* lowcost的值为0,在这里就是此下标的顶点已经加入生成树 */
	adjvex[0] = 0;			/* 初始化第一个顶点下标为0 */
	for(i = 1; i < G.numVertexes; i++)	/* 循环除下标为0外的全部顶点 */
	{
		lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */
		adjvex[i] = 0;					/* 初始化都为v0的下标 */
	}
	for(i = 1; i < G.numVertexes; i++)
	{
		min = GRAPH_INFINITY;	/* 初始化最小权值为∞, */
						/* 通常设置为不可能的大数字如32767、65535等 */
		j = 1;k = 0;
		while(j < G.numVertexes)	/* 循环全部顶点 */
		{
			if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
			{	
				min = lowcost[j];	/* 则让当前权值成为最小值 */
				k = j;			/* 将当前最小值的下标存入k */
			}
			j++;
		}
		printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */
		lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
		for(j = 1; j < G.numVertexes; j++)	/* 循环所有顶点 */
		{
			if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j]) 
			{/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
				lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
				adjvex[j] = k;				/* 将下标为k的顶点存入adjvex */
			}
		}
	}
}

int main(void)
{
	MGraph G;
	CreateMGraph(&G);
	MiniSpanTree_Prim(G);
  
	return 0;
 
}
#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */

#define MAXEDGE 20
#define MAXVEX 20
#define GRAPH_INFINITY 65535

typedef struct
{
	int arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;

typedef struct
{
	int begin;
	int end;
	int weight;
}Edge;   /* 对边集数组Edge结构的定义 */

/* 构件图 */
void CreateMGraph(MGraph *G)
{
	int i, j;

	/* printf("请输入边数和顶点数:"); */
	G->numEdges=8;
	G->numVertexes=6;

	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			if (i==j)
				G->arc[i][j]=0;
			else
				G->arc[i][j] = G->arc[j][i] = GRAPH_INFINITY;
		}
	}

	G->arc[0][1]=6;
	G->arc[0][2]=3; 
	G->arc[1][3]=1; 
	G->arc[1][5]=5; 
	G->arc[2][3]=6; 
	G->arc[2][4]=6; 
	G->arc[3][5]=5;  
	G->arc[4][5]=2;

	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}

}
/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)
{
	while ( parent[f] > 0)
	{
		f = parent[f];
	}
	return f;
}



/* Kruskal算法生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{
	int i, n, m;
	Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */
	int parent[MAXVEX];	/* 定义一数组用来判断边与边是否形成环路 */
	
	/* 此处省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码*/

	for (i = 0; i < G.numVertexes; i++)
		parent[i] = 0;					/* 初始化数组值为0 */
	for (i = 0; i < G.numEdges; i++)	/* 循环每一条边 */
	{
		n = Find(parent,edges[i].begin);
		m = Find(parent,edges[i].end);
		if (n != m) /* 假如n与m不等,说明此边没有与现有的生成树形成环路 */
		{/* 将此边的结尾顶点放入下标为起点的parent中。表示此顶点已经在生成树集合中 */
			parent[n] = m;
			printf("(%d, %d) %d\n", edges[i].begin, 
				edges[i].end, edges[i].weight);
		}
	}
}


int main(void)
{
	MGraph G;
	CreateMGraph(&G);
	MiniSpanTree_Kruskal(G);
	return 0;
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇