#include<stdio.h>
#include<stdlib.h>
#define MaxVertices 100 //假設包含100個頂點
#define MaxWeight 65535 //不鄰接時為65535，但輸出時用 "∞"
typedef struct { //包含權的鄰接矩陣的的定義
int Vertices[MaxVertices]; //頂點資訊的陣列
int Edge[MaxVertices][MaxVertices]; //邊的權資訊的陣列
int numV; //當前的頂點數
int numE; //當前的邊數
}AdjMatrix;
typedef struct ANode
{
int adjvex;
struct ANode* nextarc;
// InfoType info;
}ArcNode;
typedef struct Vnode
{
int data;
ArcNode* firstarc;
}VNode;
typedef VNode AdjList[MaxVertices];
typedef struct
{
AdjList adjlist;
int numv, nume;
}ALGraph;
void MatToList(AdjMatrix G, ALGraph* g)
{
int i, j, numv = G.numV;
ArcNode* p;
g = (ALGraph*)malloc(sizeof(ALGraph));
for (i = 0; i < numv; i++)
g->adjlist[i].firstarc = NULL;
for (i = 0; i < numv; i++)
for (j = numv - 1; j >= 0; j--)
if (G.Edge[i][j] != 0)
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = g->adjlist[i].firstarc;
g->adjlist[i].firstarc = p;
}
g->numv =G.numV; g->nume = G.numE;
}
void CreateGraph(AdjMatrix* G) //圖的生成函式
{
int n, e, vi, vj, w, i, j;
// printf("請輸入圖的頂點數和邊數（以空格分隔）：");
// scanf("%d %d",&n,&e);
n = 6;
e = 10;
G->numV = n; G->numE = e;
for (i = 0; i < n; i++) //圖的初始化
for (j = 0; j < n; j++)
{
if (i == j)
G->Edge[i][j] = 0;
else
G->Edge[i][j] = MaxWeight;
}
/* for(i=0;i<G->numV;i++) //將頂點存入陣列中
{
printf("請輸入第%d個頂點的資訊(整型):",i+1);
scanf("%d",&G->Vertices[i]);
}*/
G->Vertices[0] = 0;
G->Vertices[1] = 1;
G->Vertices[2] = 2;
G->Vertices[3] = 3;
G->Vertices[4] = 4;
G->Vertices[5] = 5;
// printf("\n");
/* for(i=0;i<G->numE;i++)
{
printf("請輸入第%d條邊的資訊i,j,w(以空格分隔):",i+1);
scanf("%d %d %d",&vi,&vj,&w);
//若為不帶權值的圖，則w輸入1
//若為帶權值的圖，則w輸入對應權值
G->Edge[vi][vj]=w;//①
//G->Edge[vj-1][vi-1]=w;//②
//無向圖具有對稱性的規律，通過①②實作
//有向圖不具備此性質，所以只需要①
}*/
G->Edge[0][1] = 5;
G->Edge[1][2] = 4;
G->Edge[2][0] = 8;
G->Edge[0][3] = 7;
G->Edge[3][2] = 5;
G->Edge[2][5] = 9;
G->Edge[5][4] = 1;
G->Edge[4][3] = 5;
G->Edge[3][5] = 6;
G->Edge[5][0] = 3;
}
void printGraph(ALGraph g)
{
int i;
ArcNode* p;
printf("輸出圖的鄰接表為：");
for (i = 0; i < g.numv; i++)
{
printf("\n%4d", g.adjlist[i].data);
p = g.adjlist[i].firstarc;
while (p != NULL)
{
printf("-->%d", p->adjvex);
p = p->nextarc;
}
}
printf("\n");
}
void DispGraph(AdjMatrix G) //輸出鄰接矩陣的資訊
{
int i, j;
printf("\n輸出頂點的資訊:\n");
for (i = 0; i < G.numV; i++)
printf("%8d", G.Vertices[i]);
printf("\n輸出鄰接矩陣:\n");
printf("\t");
for (i = 0; i < G.numV; i++)
printf("%8d", G.Vertices[i]);
for (i = 0; i < G.numV; i++)
{
printf("\n%8d", i);
for (j = 0; j < G.numV; j++)
{
if (G.Edge[i][j] == 65535)
printf("%8s", "∞");
else
printf("%8d", G.Edge[i][j]);
}
printf("\n");
}
}
int main()
{
AdjMatrix G;
ALGraph g;
CreateGraph(&G);
DispGraph(G);
MatToList(G,&g);
printGraph(g);
return 0;
}
uj5u.com熱心網友回復：
你的問題是什么
uj5u.com熱心網友回復：
可以麻煩你寫個有向帶權值的鄰接表么？謝謝
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/60181.html
標籤：C語言