无向图——邻接表和邻接矩阵的实现

邻接矩阵

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define ms(a) memset(a,0,sizeof(a))
#define N 50
//节点中包括边的个数，顶点的个数，邻接矩阵 
struct node{
	int vn=0;               //顶点 vertex 
	int en=0;				//边   edge 
	int matrix[N][N];
}; 

// 创建图 
void Creategraph(node &G){
	int vn_;
	int en_;
	cout<<"请输入顶点个数和边的个数："<<endl;
	cin>>vn_>>en_;
	G.en=en_;
	G.vn=vn_;
	int e1,e2;
	//循环输入各边 
	while(en_--){  
		cin>>e1>>e2;
		G.matrix[e1][e2]=G.matrix[e2][e1]=1;
	}
}

//打印图的邻接矩阵 
void Print(node G){
	cout<<"顶点个数为："<<G.vn<<endl;
	cout<<"边的个数为："<<G.en<<endl;
	cout<<"邻接矩阵为："<<endl;
	for(int i=1;i<=G.vn;i++){
		for(int j=1;j<=G.vn;j++){
			cout<<G.matrix[i][j]<<" ";
		}
		cout<<endl;
	}
}

int main(){
	node G;
	ms(G.matrix); 
	Creategraph(G);
	Print(G);
	return 0;
}

邻接表

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define ms(a) memset(a,0,sizeof(a))
#define N 30
// 边的结构体 
struct edgenode{
	int data;
	edgenode* next=NULL;
};
// 顶点的结构体 
struct vertexnode{
	int data;
	edgenode* firstedge=NULL;
};
//图的结构体 
struct graph{
	int vertexnum;
	int edgenum;
	vertexnode list[N];
};
//创建图 
void Creategraph(graph &G){
	int en_,vn_;
	cout<<"请输入顶点和边的个数："<<endl;
	cin>>vn_>>en_;
	G.edgenum=en_;
	G.vertexnum=vn_;
	for(int i=1;i<=G.vertexnum;i++){
		G.list[i].data=i;
	}
	int e1,e2;
	while(en_--){
		cin>>e1>>e2;
		edgenode *E1=new edgenode;
		E1->data=e1;
		edgenode *E2=new edgenode;
		E2->data=e2;
		edgenode* tem;
		//把 e1 接在 e2 后面 
		tem=G.list[e2].firstedge;
		if(tem==NULL){
			G.list[e2].firstedge=E1;
		}
		else{
			while(tem->next!=NULL){
				tem=tem->next;
			} 
			tem->next=E1;
		}
		//把 e2 接在 e1 后面 
		tem=G.list[e1].firstedge;
		if(tem==NULL){
			G.list[e1].firstedge=E2;
		}
		else{
			while(tem->next!=NULL){
				tem=tem->next;
			}
			tem->next=E2;
		}
	}
}

//打印图的邻接表 
void Print(graph G){
	cout<<"顶点个数为："<<G.vertexnum<<endl;
	cout<<"边的个数为："<<G.edgenum<<endl;
	cout<<"邻接表为："<<endl;
	edgenode* tem;
	for(int i=1;i<=G.vertexnum;i++){
		tem=G.list[i].firstedge;
		cout<<G.list[i].data<<" -> ";
		while(tem!=NULL){
			cout<<tem->data<<" -> ";
			tem=tem->next;
		}
		cout<<endl;
	} 
}

int main(){
	graph G;
	Creategraph(G);
	Print(G);
	return 0;
}