測試樣例
請輸入圖頂點個數(shù)!
6
請輸入連通的兩個點，以輸入0 0結(jié)束!
1 2
1 3
2 4
5 6
6 3
4 3
0 0
你輸入的圖為:
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 1 0 1
0 1 1 0 0 0
0 0 0 0 0 1
0 0 1 0 1 0
請輸入你的操作類型：
退出 0
圖的邊數(shù) 1
任何兩個頂點是否相連 2
求一個頂點的度是多少 3
1
圖的邊數(shù)為: 6
請輸入你的操作類型：
退出 0
圖的邊數(shù) 1
任何兩個頂點是否相連 2
求一個頂點的度是多少 3
2
請輸入兩個頂點的位置!
1 3
頂點1與頂點3相連!
請輸入你的操作類型：
退出 0
圖的邊數(shù) 1
任何兩個頂點是否相連 2
求一個頂點的度是多少 3
2
請輸入兩個頂點的位置!
1 6
頂點1與頂點6不相連!
請輸入你的操作類型：
退出 0
圖的邊數(shù) 1
任何兩個頂點是否相連 2
求一個頂點的度是多少 3
3
請輸入頂點：
3
頂點3的度為：3
請輸入你的操作類型：
退出 0
圖的邊數(shù) 1
任何兩個頂點是否相連 2
求一個頂點的度是多少 3
0
Press any key to continue
代碼如下
 #include<stdio.h>
#include<stdlib.h>
typedef struct ArcNode
   {
 int adjves;
//int weight;
struct ArcNode * nextarc;
 }ArcNode;
typedef struct
{
int data;
ArcNode firstarc;
}AdjList;
typedef struct
{
AdjList *vertices;
int vexnum, arcnum;
}ALGraph;
ALGraph alg;
int str[100][100] = {0};
/**//////////////////////////////////////void initail();//初始化鄰接表
void insert(int i, int j);//向鄰接表插入一條邊
void printAlg();//打印鄰接表
void DfsTraverseALG(int i);//深優(yōu)遍歷
void DfsALG(int i, int *visit);/**////深優(yōu)遍歷主體 void printMgraph();//打印矩陣
int Arcs(int i);//求某個頂點的度
bool isArc(int, int);//某兩個點是否相連
int getArcnumOfGraph();//獲得圖的邊數(shù)
int main()
{
int i, j, k;
scanf("%d", &(alg.vexnum));
initail();
while (1)
  {
printf("->");
scanf("%d%d", &i, &j);//按題意輸入的點序號都大于0
if (i == 0 && j == 0)
{
break;
 }
insert( i, j);
}
printAlg();
printf("DfsTraverseALG:\n");
DfsTraverseALG(1);
printf("請輸入你的操作類型：\n");
printf("退出 0\n");
printf("圖的邊數(shù) 1\n");
printf("任何兩個頂點是否相連 2\n");
printf("求一個頂點的度是多少 3\n");
while (1)
{
scanf("%d", &k);
if (k == 0)
{
break;
}
else if (k == 1)
{
printf("圖的邊數(shù)為:%d\n", getArcnumOfGraph());
}
else if (k == 2)
{
printf("請輸入兩個頂點的位置!\n");
scanf("%d%d", &i, &j);
if (isArc(i - 1, j))
{
printf("頂點%d與頂點%d相連!\n", i, j);
}
else
{
printf("頂點%d與頂點%d不相連!\n", i, j);
}
}
else if (k == 3)
{
printf("請輸入頂點：\n");
scanf("%d", &i);
printf("頂點%d的度為:%d\n",i, Arcs(i - 1));
}
else
{
printf("輸入錯誤，請重新輸入\n");
}
}
system("pause");
return 0;
}
void initail()
{
int n = alg.vexnum;
alg.arcnum = 0;
int i;
alg.vertices = (AdjList*)malloc(n * sizeof(AdjList));
for (i = 0; i < n; i++)
{
alg.vertices[i].firstarc.nextarc = NULL;
alg.vertices[i].data = i + 1;
}
}
void insert(int i, int j)
{
i--;
j--;
ArcNode *p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjves = j + 1;
p->nextarc = alg.vertices[i].firstarc.nextarc;//復(fù)制鄰接表頂點的鄰接點
alg.vertices[i].firstarc.nextarc = p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjves = i + 1;
p->nextarc = alg.vertices[j].firstarc.nextarc;//復(fù)制鄰接表頂點的鄰接點
alg.vertices[j].firstarc.nextarc = p;
alg.arcnum++;//邊數(shù)加一
}
void printAlg()
{
int i;
ArcNode *p;
for (i = 0; i < alg.vexnum; i++)
{
printf("%d:\t", i + 1);
p = alg.vertices[i].firstarc.nextarc;
while (p != NULL)
{
printf("%d\t", p->adjves);
p = p->nextarc;
}
printf("\n");
}
}
/**//////////////////////////////////////////////////void DfsTraverseALG(int i)
{
int j, n = alg.vexnum;
int *visit = (int*)malloc(alg.vexnum * sizeof(int));
i--;
for (j = 0; j < alg.vexnum; j++)
{
visit[j] = 0;
}
for (j = 0; j < alg.vexnum; j++)
{
if (visit[j] == 0)
{
DfsALG(i, visit);
}
}
printf("\n");
printMgraph();/**///////////////////
free(visit);
}
void DfsALG(int i, int *visit)
{
ArcNode *p;
int j;
visit[i] = 1;
printf("%d\t", alg.vertices[i].data);
p = alg.vertices[i].firstarc.nextarc;
while (p != NULL)
{
j = p->adjves - 1;
str[i][j] = 1;
if (visit[j] == 0)
{
DfsALG(j, visit);
}
p = p->nextarc;
}
}
void printMgraph()
{
int i, j;
printf("Mgraph:\n");
for (i = 0; i < alg.vexnum; i++)
{
for (j = 0; j < alg.vexnum; j++)
{
printf("%d ", str[i][j]);
}
printf("\n");
}
}
/**///////////////////////////////////////////////
int Arcs(int i)
{
int j = 0;
ArcNode *p = alg.vertices[i].firstarc.nextarc;
while (p != NULL)
{
j++;
p = p->nextarc;
}
return j;
}
bool isArc(int i, int j)
{
ArcNode *p = alg.vertices[i].firstarc.nextarc;
while (p != NULL)
{
if (p->adjves == j)
{
return true;
}
p = p->nextarc;
}
return false;
}
int getArcnumOfGraph()
{
return alg.arcnum;
}
|