这里将一个无向图用邻接表和邻接矩阵表示。
输入:顶底个数n,图中的各个边(用两个顶点表示)。
输出:这个无线图的邻接矩阵和邻接表,其中邻接表中的链接按元素大小升序排列。
先给出一个例子说明。假设有无向图如下,则其邻接矩阵和邻接表如提示框中所示(其实就是下面程序的输出)。
下面是程序的代码:
#include <stdio.h>
#include <stdlib.h>
//图的表示,输入节点个数和边,构造图的邻接矩阵和邻接表
//邻接表中的链表节点
struct vNode{
int value;
struct vNode* next;
};
//向邻接表中插入一个数据,并保证邻接表的有序性
void insertIntoAdjVertics(struct vNode** adjVertics,int start,int end){
struct vNode* node = (struct vNode*)malloc(sizeof(struct vNode));
struct vNode* head = adjVertics[start];
node->value = end;
node->next = NULL;
if(head == NULL){
adjVertics[start] = node;
return;
}
if(head->next==NULL&&head->value>end){
node->next = head;
adjVertics[start] = node;
return;
}
while(head->next!=NULL && head->next->value<end){
head = head->next;
}
if(head->next==NULL){
head->next = node;
return;
}
node->next = head->next;
head->next = node;
}
//打印邻接矩阵
void displayNeighborMatrix(int** neighborMatrix,int n){
int i,j;
printf("\n");
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%d ",neighborMatrix[i][j]);
}
printf("\n");
}
}
//打印邻接表
void displayAdjVertice(struct vNode** adjVertics,int n){
int i;
for(i=0;i<n;i++){
struct vNode* head = adjVertics[i];
printf("%d: ",i);
while(head!=NULL){
printf("->%d ",head->value);
head = head->next;
}
printf("\n");
}
}
int main() {
int n,i,j;
int** neighborMatrix;
struct vNode** adjVertics;
int start,end;
printf("input vertex number: ");
scanf("%d",&n);
//初始化邻接矩阵
neighborMatrix = (int**)malloc(sizeof(int*)*n);
for(i=0;i<n;i++){
neighborMatrix[i] = (int*)malloc(sizeof(int)*n);
for(j=0;j<n;j++){
neighborMatrix[i][j] = 0;
}
}
adjVertics = (struct vNode**)malloc(sizeof(struct vNode*)*n);
for(i=0;i<n;i++){
adjVertics[i] = NULL;
}
//输入定点,格式为 1 2
printf("input start and end vertex, format 1 2, stop by -1. \n");
while(1){
scanf("%d",&start);
if(start==-1){
break;
}
scanf("%d",&end);
neighborMatrix[start][end] = 1; //对称矩阵
neighborMatrix[end][start] = 1;
insertIntoAdjVertics(adjVertics,start,end);
insertIntoAdjVertics(adjVertics,end,start);
}
displayNeighborMatrix(neighborMatrix,n);
printf("-------------\n");
displayAdjVertice(adjVertics,n);
return EXIT_SUCCESS;
}