#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MaxVex 10 //假设当前顶点数最多为10个
int visited[MaxVex]; //用来存放当前顶点是否遍历过
//*****定义邻接矩阵****
typedef struct{
char vexs[MaxVex]; //顶点集
int arcs[MaxVex][MaxVex]; //邻接矩阵
int vexnum,arcnum; //点和边
}MGraph;
//输出图的邻接矩阵
void PrintMGraph(MGraph MG){
int i,j;
if(MG.vexnum<=0) //如果顶点的个数不合法，什么也不返回
return;
for(i=0; i<MG.vexnum; i++) //如果顶点数在合法范围，则输出顶点集
printf("%c",MG.vexs[i]);
printf("\n"); //换行
for(i=0; i<MG.vexnum; i++){ //输出邻接矩阵
for(j=0; j<MG.vexnum; j++)
printf("%d",MG.arcs[i][j]);
printf("\n");
}
}
//若G中存在v,则返回该顶点在图中位置,否则返回-1
int LocateVex(MGraph G, char v){
int i;
for(i=0; i<G.vexnum; i++){
if(G.vexs[i]==v) //遍历顶点数组，若顶点数v存在则返回
return i;
}
return -1;
}
//返回顶点v的第一个邻接点位置,否则返回-1
int FisrtAdjVertex(MGraph G, int v)
{
//--------补充代码--Start------
for(int i=0;i<G.vexnum;i++){ //在顶点v所在行搜寻，寻找其值为1的（即有连线的顶点）并返回那个顶点所在位置
if(G.arcs[v][i]==1)return i;
}
return -1;
//--------补充代码--End-------
}
//返回顶点v相对于w的下一个邻接点位置,否则返回-1
int NextAdjVertex(MGraph G, int v, int w)
{
//--------补充代码--Start------
for( int i=w+1;i<G.vexnum;i++){ // i初始值为w右侧，i在v行遍历，若第v，w+1个位置为1，则说明v与w下一个临界点为i
if(G.arcs[v][i]==1)return i;
}
return -1;
//--------补充代码--End-------
}
//邻接矩阵存储方式建立无向图
void CreateMGraph(MGraph &G)
{
/*
step 1.输入图中顶点总数与边的总数
step 2.输入图中顶点信息，存放到G.vexs[i]数组中
step 3.初始化邻接矩阵中所有值为0
step 4.输入边的信息，修改邻接矩阵中相对应的元素值
*/
//--------补充代码--Start------
char c;
scanf("%d %d",&G.vexnum,&G.arcnum); //定义零界点的点和边数
getchar();
for (int i = 0; i < G.vexnum;) {
scanf("%c", &c);
if (c != ' ') { //输入顶点
G.vexs[i] = c;
i++;
}
}
for(int i=0;i<MaxVex;i++){
for(int j=0;j<MaxVex;j++){
G.arcs[i][j]=0; //初始化为空表
}
}
for(int i=0;i<G.arcnum;i++){
char c1,c2;
int a,b;
getchar();
scanf("%c %c",&c1,&c2);
a=LocateVex(G,c1);
b=LocateVex(G,c2);
G.arcs[a][b]=1;
G.arcs[b][a]=1;
}
//--------补充代码--End-------
}
//从第i个顶点开始深度遍历
void DFSMGraph(MGraph G,int i)
{
//--------补充代码--Start------
int w;
printf("%c",G.vexs[i]);
visited[i]=1;
for(w=FisrtAdjVertex(G,i); w>=0; w=NextAdjVertex(G,i,w)){
if(visited[w]==0)
DFSMGraph(G, w);
//--------补充代码--End-------
}
}
//从第i个顶点开始广度遍历
void BFSMGraph(MGraph G,int i) {
//--------补充代码--Start------
int Queue[G.vexnum];
int front=0,rear=0,j=0;
printf("%c",G.vexs[i]);
visited[i]=1;
Queue[rear]=i;
rear++;
while(front<rear){
i=Queue[front];
front++;
for(j=0; j<=G.vexnum; j++){
if ((G.arcs[i][j]==1) && (visited[j]==0)) {
printf("%c",G.vexs[j]);
visited[j]=1;
Queue[rear]=j;
rear++;
}
}
}
//--------补充代码--End-------
}
//主函数
int main()
{
int i,select,vex;
char start;
MGraph MG;
MG.vexnum=MG.arcnum=0;
while(scanf("%d",&select)!=EOF)
{
if(select==1){//输出图
PrintMGraph(MG);
}
else if(select==2){//建立无向图
CreateMGraph(MG);
}
else if(select==3){//深度遍历
getchar();
scanf("%c",&start);//遍历的起始顶点
vex = LocateVex(MG, start);
for(i=0; i<MG.vexnum; i++)
visited[i] = 0;
DFSMGraph(MG,vex);
printf("\n");
}
else if(select==4){//广度遍历
getchar();
scanf("%c",&start);//遍历的起始顶点
vex = LocateVex(MG, start);
for(i=0; i<MG.vexnum; i++)
visited[i] = 0;
BFSMGraph(MG,vex);
printf("\n");
}
}
return 0;
}
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MaxVex 10 //假设当前顶点数最多为10个
int visited[MaxVex]; //用来存放当前顶点是否遍历过
//******定义邻接表******
typedef struct ArcNode{ //边结点
int adjvex; //邻接点在数组中的位置
int weight; //边的权重(>0)
struct ArcNode *nextarc; //指向下一个边结点的指针
}ArcNode;
typedef struct VNode{ //表头结点
char data;
ArcNode *firstarc;
}VNode;
typedef struct{ //邻接表
VNode vexs[MaxVex];
int vexnum,arcnum;
}ALGraph;
//若G中存在v,则返回该顶点在图中位置,否则返回-1
int LocateVex(ALGraph G, char v){
//--------补充代码--Start------
int i;
for(i=0;i<G.vexnum;i++){
if(G.vexs[i].data==v)
return i;
}
return -1;
//--------补充代码--End------
}
//建立邻接表存储方式的无向图
void CreateALGraph(ALGraph &G)
{
/* 1.输入图中顶点总数与边的总数
2.输入图中顶点信息
3.输入边的信息，建立边结点，插入到相对应数组元素后的边表中（注：无向图中每条边需要插入两个边结点）。*/
int i,j,k;
char v1,v2;
ArcNode *p, *q;
int w;
scanf("%d %d",&G.vexnum,&G.arcnum);
getchar();
for(i=0; i<G.vexnum; i++)
{
scanf("%c",&G.vexs[i].data);
G.vexs[i].firstarc=NULL;
getchar();
}
for(k=0; k<G.arcnum; k++){//构造邻接矩阵
scanf("%c %c %d",&v1,&v2,&w);
//确定v1和v2在G中的位置
i=LocateVex(G, v1);
j=LocateVex(G, v2);
//在i顶点后面插入表结点(头插)
p=G.vexs[i].firstarc;
q=(ArcNode*)malloc(sizeof(ArcNode));
q->adjvex=j;
q->weight=w;
q->nextarc=p;
G.vexs[i].firstarc=q;
getchar();
}
}
//深度遍历邻接表
void DFSALGraph(ALGraph G,int i)
{
//--------补充代码--Start------
ArcNode *p;
printf("%c",(G.vexs[i].data));
visited[i]=1;
p=G.vexs[i].firstarc;
while(p){
if (visited[p->adjvex]==0)
DFSALGraph(G, p->adjvex);
p=p->nextarc;
}
//--------补充代码--End------
}
//计算图中所有边的权值之和
int GetGraphWeight(ALGraph G)
{
//--------补充代码--Start------
int weight=0;
ArcNode *p;
for(int i=0;i<G.vexnum;i++){
p=G.vexs[i].firstarc;
while(p!=NULL){
weight+=p->weight;
p=p->nextarc;
}
}
return weight;
//--------补充代码--End------
}
//计算图中出度大于入度的结点个数
int GetNode(ALGraph G)
{
//--------补充代码--Start------
int i,j,count=0;
for(i=0;i<G.vexnum;i++){
int in=0,out=0;
ArcNode *p;
p=G.vexs[i].firstarc;
while(p!=NULL){
out++;
p=p->nextarc;
//printf("%d",out);
}
for(j=0;j<G.vexnum;j++){
if(i!=j){
p=G.vexs[j].firstarc;
while(p!=NULL){
if(p->adjvex==i)
in++;
p=p->nextarc;
}
}
}
//printf(" %d %d %d ",i,out,in);
if(out>in)count++;
}
return count;
//--------补充代码--End------
}
//主函数
int main()
{
int i,select,vex;
char start;
ALGraph G;
G.vexnum=G.arcnum=0;
while(scanf("%d",&select)!=EOF)
{
if(select==1){//建立有向网
CreateALGraph(G);
}
else if(select==2){//深度遍历
getchar();
scanf("%c",&start);//遍历的起始顶点
vex = LocateVex(G, start);
for(i=0; i<G.vexnum; i++)
visited[i] = 0;
DFSALGraph(G,vex);
printf("\n");
}
else if(select==3){//求权和
getchar();
printf("%d\n",GetGraphWeight(G));
}
else if(select==4){//求结点数
getchar();
printf("%d\n",GetNode(G));
}
}
return 0;
}