邻接表和矩阵的组合。
例如给下图建立邻接矩阵和邻接表并输出之
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define MAX_VERTEX_NUM 20 // 这是一个邻接矩阵和邻接表的组合
#define ERROR 0
#define OK 1
#define INFINITY 0
typedef struct EdgeNode //边表节点
{
int adjvex;
int info;
struct EdgeNode *next;
}EdgeNode;
typedef struct VertexNode //顶点节点
{
int date;
EdgeNode *firstedge;
}VertexNode,AdjList[MAX_VERTEX_NUM];
typedef struct ArcCell //矩阵的信息
{
int adj;
int *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct //图的相关信息
{
AdjList adjList;
AdjMatrix arcs; // juzheng
int numNodes,numEdges;
}GraphAdList;
int LocateVex(GraphAdList *G,int a)
{
for(int i=0;i<G->numNodes;i++)
{
if(a==G->adjList[i].date)
return i;
}
return ERROR;
}
void CreateALGraph(GraphAdList *G)
{
EdgeNode *e;
scanf("%d%d",&G->numNodes,&G->numEdges);
for(int i=0;i<G->numNodes;i++)
{
scanf("%d",&G->adjList[i].date);
G->adjList[i].firstedge=NULL;
}
for(int n=0;n<G->numNodes;n++)
for(int m=0;m<G->numNodes;m++)
{
G->arcs[n][m].adj=INFINITY;
G->arcs[n][m].info=NULL;
}
for(int k=0;k<G->numEdges;k++)
{
int n1,n2,w;
int v1,v2;
scanf("%d%d%d",&v1,&v2,&w);
n1=LocateVex(G,v1); n2=LocateVex(G,v2);
G->arcs[n1][n2].adj=w;
G->arcs[n2][n1].adj=w;
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=v2;
e->next=G->adjList[v1].firstedge;
G->adjList[v1].firstedge=e;
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=v1;
e->next=G->adjList[v2].firstedge;
G->adjList[v2].firstedge=e;
}
}
void DisGraphAdjList(GraphAdList *G)
{
EdgeNode *p;
printf("图的邻接表表示如下\n");
printf("%6s%8s%12s\n","编号","顶点","相邻边编号");
for(int i=0;i<G->numNodes;i++)
{
printf("%4d %8d",i,G->adjList[i].date);
for(p=G->adjList[i].firstedge;p!=NULL;p=p->next)
printf("%4d",p->adjvex);
printf("\n");
}
}
int main()
{
GraphAdList G;
CreateALGraph(&G);
for(int i=0;i<G.numNodes;i++)
{
for(int j=0;j<G.numNodes;j++)
{
printf("%4d",G.arcs[i][j].adj); // 输出矩阵
}
printf("\n\n");
}
DisGraphAdjList(&G); //输出邻接表
return 0;
}
具体情况改变具体的数据类型。
