本文共 1459 字，大约阅读时间需要 4 分钟。
邻接表到邻接矩阵
5000(ms)
10000(kb)
2329 / 7285
假设无向图G采用邻接表存储，编写一个算法输出邻接矩阵。
输入
第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1）。第二行表示顶点0可直接到达的顶点编号，其他行定义相同。
输出
输出图G的邻接矩阵。整数矩阵大小为n*n，表示图的邻接关系。数字为0表示不邻接，1表示邻接。
样例输入
51 3 40 2 31 3 40 1 2 40 2 3
样例输出
0101110110010111110110110
#include #include #include using namespace std;#define INF 32767//定义无穷typedef struct{ int no;//顶点的编号 int info;//顶点的其他信息 }VerType;//顶点的类型typedef struct{ int edges[100][100];//邻接矩阵数组 int n,e;//顶点数，边数 VerType vexs[100];//存放顶点信息 }MatGraph;//完整的图邻接矩阵类型//邻接表存储方法typedef struct ANode{ int adjv;//该边的邻接点编号 struct ANode *next;//指向下一条边的指针}ArcNode;//边结点的类型typedef struct Vnode{ int info;//顶点的其他信息 ArcNode *first;//指向第一个边结点 }VNode;//邻接表的头结点类型typedef struct{ VNode adjl[100];//邻接表的头结点数组 int n,e;//图中的顶点数和边数 }AdjGraph;//完整的图邻接表类型 void CreateAdj(AdjGraph *&G,int n)//创建图的邻接表{ int i,d; char c; ArcNode *p; for(i=0;i adjl[i].first=NULL; for(i=0;i adjv=d;//存放邻接点 p->next=NULL;//头插法 if(G->adjl[i].first==NULL) G->adjl[i].first=p; else{ ArcNode *q=G->adjl[i].first; p->next=q; G->adjl[i].first=p; } if(c=='\n'){ break; } } G->n=n;} //邻接表到邻接矩阵void LTM(AdjGraph *G,MatGraph &g) { int i; ArcNode *p; for(i=0;i n;i++){ p=G->adjl[i].first; while(p!=NULL){ g.edges[i][p->adjv]=1; p=p->next; } } g.n=G->n;}int main(){ AdjGraph *G; G=(AdjGraph *)malloc(sizeof(AdjGraph)); MatGraph g; cin>>G->n; g.edges[100][100]={0}; CreateAdj(G,G->n); LTM(G,g); for(int i=0;i
转载地址：http://jmshn.baihongyu.com/