题目

已知一个无向图如下图所示，试给出该图的邻接矩阵和邻接表存储示意图（画图，分别用矩阵和数组链表图表示），并编程分别实现该图的邻接矩阵表示和邻接表显示表示，要求编写两种表示方式的存储结构和相关基本操作，并在主函数创造此图

代码

邻接矩阵表示法

#include <iostream>
#define maxValue max
#define E 50
#define V 20
using namespace std;
typedef struct{
   
	char vexlist[V];//顶点集
	int edge[E][E];//矩阵表
	int n,e;//矩阵的顶点数目，边数
}MTGraph;

void CreateMGraph(MTGraph *G){
   
	int i,j;
	//输入图的点数和边数
	cout<<"please cin the mount of point and edge:";
	cin>>G->n;
	cin>>G->e;
	//输入顶点信息
	cout<<"please cin the information of each point:";
	for(i=0;i<G->n;i++){
   
		cin>>G->vexlist[i];
	}

	//邻接矩阵初始化
	for(i=0;i<G->n;i++){
   
		for(j=0;j<G->n;j++){
   
			G->edge[i][j]=0;
		}
	}
	//输入图中边的节点（i，j),此处权值为1
	cout<<"输入图中每条边的节点（i，j),i和j不等:";   //应判断i和j不等，并重新输入 
	for(int k=0;k<G->e;k++) {
   
		cin>>i;
		cin>>j;
		while(i==j){
   
		    cout<<"i not equal to j! cin again!"; 
		    cin>>i;
		    cin>>j;
		}
		G->edge[i-1][j-1] =1;
		G->edge[j-1][i-1] =1;
	}
}
  
MTGraph NewNode(MTGraph *G,char x){
     //添加顶点 
    G->vexlist[G->n] =x;
	for(int i=0;i<=G->n;i++){
   
		G->edge[G->n][i]=0;
		G->edge[i][G->n]=0;
	}
    ++G->n;
	return *G;
}

void delNode(MTGraph *G,char x){
    //删除字符为特定值的顶点 
	//遍历点的数据，如有有执行删除操作
	for(int i=0;i<G->n;i++){
   
		if(G->vexlist[i] == x){
   
			cout<<"find "<<x<<endl;
			//删除顶点集
			for(int j=i;j<G->n-1;j++){
   
				G->vexlist[j] =G->vexlist[j+1]; //数组，把x后面的顶点向前挪一位 
			}
			G->vexlist[G->n-1] =0;
			cout<<"already del point! "<<x<<endl;
			//删除边集
			for(int ins=i;ins<G->n;ins++){
   
				if(ins==G->n-1){
                 //如果删除的顶点是最后一个顶点，"删除"边表中最后一行和最后一列 
					for(int k=0;k<G->n;k++){
   
						G->edge[ins][k] =0;
						G->edge[k][ins] =0;
					}
				}
				for(int k=0;k<G->n;k++){
               
					G->edge[ins][k] =G->edge[ins+1][k];
					G->edge[k][ins] =G->edge[k][ins+1];
				}
				G->edge[ins][ins]=G->edge[ins+1][ins+1];//矩阵对角线上的元素都为0
			}
			//点的数量减一
			--G->n;
			break;
		}
		if(i=G->n)
			cout<<"not find "<<x<<endl;
	}

}

void setSucc(MTGraph *G,char x1,char x2){
     //未判断顶点x1和x2之间是否有边的存在，参数是顶点的字符，不用自己找顶点的编号 
	int i,j;
	for(int k=0;k<G->n;k++){
   
		if(G->vexlist[k] ==x1){
   
			i=k;
		}
		if(G->vexlist[k] ==x2){
   
			j=k;
		}
	}
	G->edge[i][j] =1;
	G->edge[j][i] =1;
}

void delSucc(MTGraph *G,char x1,char x2){
   
	int i,j;
	for(int k=0;k<G->n;k++){
   
		if(G->vexlist[k] ==x1){
   
			i=k;
		}
		if(G->vexlist[k] ==x2){
   
			j=k;
		}
	}
	G->edge[i][j] =0;
	G->edge[j][i] =0;
}

void print(MTGraph *G){
   
	cout<<"all information of the graph:\n ";
	int i,j;

	for(i=0;i<G->n;i++){
   
		cout<<G->vexlist[i]<<" ";
	}
	cout<<endl;
	cout<<"the data of the matrix:\n";
	for(i=0;i<G->n;i++){
   
		for(j=0;j<G->n;j++){
   
			cout<<G->edge[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main(){
   
	MTGraph *G1 =new MTGraph();
	CreateMGraph(G1);
	print(G1);

	cout<<"add element 8:\n";
	NewNode(G1,'8');
	print(G1);

	cout<<"delete element 1:\n";
	delNode(G1,'1');
	print(G1);

	cout<<"add edge between 2 and 6\n";
	setSucc(G1,'2','6');
	print(G1);
	return 0;
}

邻接表表示法

#include <iostream>
using namespace std;
#define NumVertices 11 //顶点个数

typedef char VertexData; 	//顶点数据类型
typedef int EdgeData; 		//边上权值类型

typedef struct node {
    		//边表结点
	int adjvex; 			//邻接点域(下标)
	//EdgeData cost; //边上的权值
	struct node *next; 		//下一边链接指针
} EdgeNode;

typedef struct {
    			//顶点表结点
	VertexData vertex; 		//顶点数据域
	EdgeNode * firstedge; 		//边链表头指针
} VertexNode;

typedef struct {
    			//图的邻接表
	VertexNode vexlist [NumVertices];
	int n, e; 			//图中当前的顶点个数与边数
} AdjGraph;

AdjGraph CreateGraph (AdjGraph *G) {
   //未判断顶点的个数是否超出最大顶点数，以及边数是否小于最大边数 
	cout<<"输入顶点个数和边数:";
	cin >> G->n >> G->e; 	//1.输入顶点个数和边数
	int i;
	int head,tail;

	cout<<"输入顶点信息:";
	for ( i = 1; i <= G->n; i++) {
    	//2.建立顶点表
		cin >> G->vexlist[i].vertex; 	//2.1输入顶点信息
		G->vexlist[i].firstedge = NULL; //2.2边表置为空表
	} 

	cout<<"逐条边输入,建立边表:\n";
	for ( i = 1; i <= G->e; i++) {
    	//3.逐条边输入,建立边表
	
	    cout<<"请输入第"<<i<<"条边的起始点，终止点";
		cin >> tail >> head; 	//3.1输入(变量说明省了,无向图，顺序无所谓)

		EdgeNode * p = new EdgeNode; 	//3.2建立边结点
		p->adjvex = head;
		p->next = G->vexlist[tail].firstedge; 	//3.4链入第tail 号链表的前端
		G->vexlist[tail].firstedge = p;
		
		p = new EdgeNode;
		p->adjvex = tail;
		p->next = G->vexlist[head].firstedge; 	//链入第head 号链表的前端
		G->vexlist[head].firstedge = p;         //无向图中增加一条边需要在边表中添加两个结点 
	}

	return *G;

} //时间复杂度：O(2e+n)

AdjGraph SetSucc(AdjGraph *G){
     //建立新边，未检查是否为重复边，未检查顶点是否存在 
	int x;
	int y;
	cout<<"在哪两点之间添加边：";
	cin>>x>>y;

	EdgeNode *p=new EdgeNode;
	p->adjvex = x;
	p->next = G->vexlist[y].firstedge; 	//3.4链入第tail 号链表的前端
	G->vexlist[y].firstedge = p;
	
	p = new EdgeNode;
	p->adjvex = y;
	p->next = G->vexlist[x].firstedge; 	//链入第head 号链表的前端
	G->vexlist[x].firstedge = p;

	G->e++;
	return *G;
}
void print(AdjGraph *G){
   
	for(int i=1;i<=G->n;i++){
   
		cout<<G->vexlist[i].vertex<<"-->";
        EdgeNode *temp =G->vexlist[i].firstedge;
		while(temp!=NULL){
   
			
			cout<<temp->adjvex<<"-->";
			//G->vexlist[i].firstedge =G->vexlist[i].firstedge->next;
			temp=temp->next;
		}
		cout<<"NULL\n";
	}
}
int main(){
   
	AdjGraph *g =new AdjGraph();
	*g =CreateGraph(g);
	print(g);

	*g =SetSucc(g);
	print(g);
	return 0;
}

综合代码

#include <iostream>
#include <string>
using namespace std;

#define NumVertices 10 // 顶点个数
typedef string VertexData;  // 顶点数据类型
typedef struct node  // 边表结点
{
   
    int adjvex;  // 邻接点域（下标
    node* next;  // 下一边链接指针
}EdgeNode;
typedef struct  // 顶点表结点
{
   
    VertexData vertex;  // 顶点数据域
    EdgeNode* firstedge;  // 边链表头指针
}VertexNode;
typedef struct  // 图的邻接表
{
   
    VertexNode vexlist[NumVertices];
    int n, e;  // 图中当前的顶点个数与边数
}AdjGraph;
void CreateGraph(AdjGraph& G)
{
   
    cout << "顶点个数：";
    cin >> G.n;
    cout << "顶点边数：";
    cin >> G.e;
    for (int i = 0; i < G.n; ++i)  // 2.建立顶点表
    {
   
        G.vexlist[i].vertex = "v" + to_string(i + 1);
        G.vexlist[i].firstedge = NULL;  // 边表置为空表
    }
    for (int i = 0; i < G.e; ++i)  // 3.逐条边输入,建立边表
    {
   
        int head, tail;
        cout << "第" << i + 1 << "条边的两个顶点：";
        cin >> head >> tail;  // 输入
        --head;
        --tail;
        EdgeNode* p = new EdgeNode{
    head, G.vexlist[tail].firstedge };  // 建立、设置边结点，链入第 tail 号链表的前端
        G.vexlist[tail].firstedge = p;
        p = new EdgeNode{
    tail, G.vexlist[head].firstedge };  // 链入第 head 号链表的前端
        G.vexlist[head].firstedge = p;
    }
}
void PrintGraph(AdjGraph G)
{
   
    for (int i = 0; i < G.n; ++i)
    {
   
        VertexNode tmp = G.vexlist[i];
        cout << "顶点表：" << tmp.vertex << " 边表：";
        while (tmp.firstedge)
        {
   
            cout << G.vexlist[tmp.firstedge->adjvex].vertex << ' ';
            tmp.firstedge = tmp.firstedge->next;
        }
        cout << endl;
    }
}

typedef struct
{
   
    int n, e;
    VertexData vertex[NumVertices];
    bool a[NumVertices][NumVertices];
}AdjMatrix;
void CreateMatrix(AdjMatrix& M)
{
   
    cout << "顶点个数：";
    cin >> M.n;
    cout << "顶点边数：";
    cin >> M.e;
    for (int i = 0; i < M.n; ++i)  // 2.建立顶点表
    {
   
        M.vertex[i] = "v" + to_string(i + 1);
    }
    for (int i = 0; i < M.n; ++i)
    {
   
        for (int j = 0; j < M.n; ++j)
        {
   
            M.a[i][j] = false;
        }
    }
    for (int i = 0; i < M.e; ++i)  // 3.逐条边输入,建立边表
    {
   
        int head, tail;
        cout << "第" << i + 1 << "条边的两个顶点：";
        cin >> head >> tail;  // 输入
        --head;
        --tail;
        M.a[head][tail] = true;
        M.a[tail][head] = true;
    }
}
void PrintMatrix(AdjMatrix M)
{
   
    for (int i = 0; i < M.n; ++i)
    {
   
        cout << M.vertex[i] << ' ';
    }
    cout << endl;
    for (int i = 0; i < M.n; ++i)
    {
   
        for (int j = 0; j < M.n; ++j)
        {
   
            cout << M.a[i][j] << ' ';
        }
        cout << M.vertex[i] << endl;
    }
}

int main()
{
   
    /*AdjGraph adjGrapth{}; CreateGraph(adjGrapth); PrintGraph(adjGrapth);*/

    AdjMatrix adjMatrix{
   };
    CreateMatrix(adjMatrix);
    PrintMatrix(adjMatrix);
}