²      难点陈说

自身初步化邻接表数据极度 假设还会有任何主题材料也请补助改一下 20C
#include”stdio.h”
#include”stdlib.h”
#define MAX_VERTEX_NUM 20
#define InfoType int
#define VertexType char
#define MaxSize 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define SElemType int
#define Status int
#define OVERFLOW -1
typedef struct
{
SElemType base;
SElemType
top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{
S.base = (SElemType)malloc(STACK_INIT_SIZE sizeof(SElemType));
if
exit;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 1;
}
Status GetTop(SqStack S, SElemType &e)
{
if (S.base == S.top)return 0;
e = (S.top – 1);
return 1;
}
Status Push(SqStack &S, SElemType e)
{
if (S.top – S.base == 0)
{
S.base = (SElemType
)realloc(S.base, (STACK_INIT_SIZE +
STACKINCREMENT) * sizeof(SElemType));
if exit;
S.top = S.base + S.stacksize;
S.stacksize = STACK_INIT_SIZE + STACKINCREMENT;
}
= e;
return 1;
}
Status Pop(SqStack &S, SElemType &e)
{
if (S.base == S.top) return 0;
e =
–S.top;
return 1;
}
Status StackEmpty(SqStack S)
{
if (S.top – S.base == 0)
return 1;
else
return 0;
}
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int weight;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertex;
int vexnum, arcnum;
int kind;
}ALGraph;

学业:用邻接表达成图的深度与广度优先遍历。(做出来的遍历结果连串卓殊卡塔尔国

扩张拓扑排序算法,实行学科学习安排的赞助制订。三个学员在二个学期能够并且学习多门课程,同生龙活虎学期的各门课程之间必需空中楼阁程序关系,制订课程布置使学生可以在最短期内学完全部课程。

int indegree[MaxSize];
int ve[MaxSize];//定义事件最新生儿窒息生 (vertex earliestState of Qatar
int vl[MaxSize];//定义事件最晚发生 (vertex lastestState of Qatar
void CreateDGAOV(ALGraph *G)
{
int i, j, k;
ArcNode *e;
printf(“输入顶点和边:n”);
scanf_s(“%d,%d”, &G->vexnum, &G->arcnum);
getchar();
printf(“请开首化极点n”);
for (i = 0; i < G->vexnum; i++)
{
printf(“输入极点字符:n”);
scanf_s(“%c”, &G->vertex[i].data);
G->vertex[i].firstarc = NULL;

次第如下:

源程序:

getchar();
}
for (k = 0; k < G->arcnum; k++)
{
printf(“输入边上的极限序号:n”);
scanf_s(“%d,%d”, &i, &j);
e = (ArcNode)malloc(sizeof;
e->adjvex = j;
e->nextarc = G->vertex[i].firstarc;
G->vertex[i].firstarc = e;
}
}
Status CreateDGAOE(ALGraph
G)
{

/*邻接表表示的图的吃水优先搜索和广度优先搜索程序*/
#include <stdio.h>
#define maxvertexnum 100
#define queuesize 100
#define null 0

#include<stdio.h>
#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100
澳门新葡萄京所有网站,typedef int VertexType;
typedef struct node{
    int adjvex;
    struct node *next;
}EdgeNode;
typedef struct vnode{
    VertexType vertex;
    char name[20];
    EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef enum{
   FALSE,TRUE
}Boolean;
typedef struct{
    AdjList adjlist;
    int n,e;
}ALGraph;
typedef int DataType;
typedef struct stacknode{
    DataType data;
    struct  stacknode  *next;
}StackNode;
typedef struct{
    StackNode *top;
}LinkStack;
void InitStack(LinkStack *S)
{
 S->top=NULL;
}
int StackEmpty(LinkStack *S)
{
 return S->top==NULL;
}
void Push(LinkStack *S,DataType x)
{
 StackNode *p;
 p=(StackNode *)malloc(sizeof(StackNode));
 p->data=x;
 p->next=S->top;
 S->top=p;
}
DataType Pop(LinkStack *S)
{
 DataType x;
 StackNode *p=S->top;
 if (StackEmpty(S))
    printf(“Stack underflow!”);
 x=p->data;
 S->top=p->next;
 free(p);
 return x;
}
void CreateALGraph(ALGraph *G)
{int i,j,k;
 EdgeNode *s;
 printf(“nEnter n & e:n”);
 scanf(“%d%d”,&G->n,&G->e);
 printf(“Enter the courses’ number & name:n”);
 for (i=0;i<G->n;i++)
   {
    scanf(“%d%s”,&G->adjlist[i].vertex,G->adjlist[i].name);
    G->adjlist[i].firstedge=NULL;
   }
 printf(“Enter edge:n”);
 for (k=0;k<G->e;k++)
   {
    scanf(“%d%d”,&i,&j);
    s=(EdgeNode *)malloc(sizeof(EdgeNode));
    s->adjvex=j;
    s->next=G->adjlist[i].firstedge;
    G->adjlist[i].firstedge=s;
   }
}
void NonPreFirstTopSort(ALGraph *G)
{
 int indegree[MaxVertexNum],i,j,count=0,k=1,flag,t;
 LinkStack S;
 EdgeNode *p;
 Boolean B[MaxVertexNum];
 for(i=0;i<G->n;i++)
   {
    indegree[i]=0;
    B[i]=FALSE;
   }
 for(i=0;i<G->n;i++)
    for(p=G->adjlist[i].firstedge;p;p=p->next)
       indegree[p->adjvex]++;
 InitStack(&S);
 while(count<G->n)
  {
   printf(“The %d term:”,k++);
   for(i=0;i<G->n;i++)
      if(indegree[i]==0 && B[i]==FALSE)
        {
  printf(“(%d %s)  
“,G->adjlist[i].vertex,G->adjlist[i].name);
  B[i]=TRUE;
         count++;
  Push(&S,i);
        }
   printf(“n”);
   while(!StackEmpty(&S))
    {
     i=Pop(&S);
     for(p=G->adjlist[i].firstedge;p;p=p->next)
      {
       j=p->adjvex;
       indegree[j]–;
      }
    }
   flag=0;
   for(t=0;t<G->n;t++)
      for(p=G->adjlist[t].firstedge;p;p=p->next)
  if(indegree[p->adjvex]==0 && B[p->adjvex]==FALSE)
          {
           flag=1;
           break;
          }
   if(flag==0 && count<G->n)
    {
     printf(“nThe Graph is not a DAG .n”);
     return;
    }
 }
}
void main()
{
 ALGraph *G;
 void CreateALGraph(ALGraph *G);
 void NonPreFirstTopSort(ALGraph *G);
 CreateALGraph(G);
 NonPreFirstTopSort(G);
}

VNode v1, v2;int i, j, sign1, sign2;int value;printf("创建AOEn");printf("请输入顶点数和边数:");scanf_s("%d,%d", &G->vexnum, &G->arcnum);getchar();printf("请初始化顶点n");for (i = 0; i < G->vexnum; i++){ printf("输入顶点字符:n"); scanf_s("%c", &G->vertex[i].data); G->vertex[i].firstarc = NULL; getchar();}printf("请初始化弧n");printf("输入格式:顶点1 顶点2 权值(表示顶点1邻接到顶点2)nn");for (i = 0; i < G->arcnum; i++){ ArcNode *p, *q; sign1 = -1; sign2 = -1; scanf_s("%c%c%d", &v1.data, &v2.data, &value); getchar(); for (j= 0; j< G->vexnum; j++) { if (v1.data == G->vertex[j].data) sign1 = j; if (v2.data == G->vertex[j].data) sign2 = j; } p = malloc(sizeof; if  exit; p->nextarc = NULL; p->weight = value; p->adjvex = sign2; q = G->vertex[sign1].firstarc; if  G->vertex[sign1].firstarc = p; else { while (q->nextarc != NULL) q = q->nextarc; q->nextarc = p; }}return 1;

typedef struct
{
 int front,rear,count,data[queuesize];
}cirqueue; 
typedef int vertextype; 

}
void FindInDegree(ALGraph G卡塔尔//总结各种节点的入度;
{
ArcNode *p;
int i, k;
for (i = 0; i < G.vexnum; i++)
indegree[i] = 0;
for (i = 0; i < G.vexnum; i++)
{
p = G.vertex[i].firstarc;
while (p != NULL)
{
k = p->adjvex;
indegree[k]++;
p = p->nextarc;
}
}
}
int TopologicalSort(ALGraph &G卡塔尔(قطر‎//拓扑排序的落到实处
{
int i, k, count = 0;
SqStack S;
ArcNode *p;
FindInDegree;
InitStack;
printf(“TopologicalSort:”);
for (i = 0; i < G.vexnum; i++卡塔尔(قطر‎//将入度为0的终端的下标号压入顺序栈S
if (!indegree[i])
Push;
while (!StackEmpty//假若栈不为空
{
Pop;//弹出栈顶存储的极端的下标号
printf(“%3c”, G.vertex[i].data卡塔尔(قطر‎;//输出下标号为i的终端中的数据;
count++;//每弹出三遍,count就加后生可畏,全部输出后应当是vexnum的值,可由那些来剖断G有未有环;
for (p = G.vertex[i].firstarc; p; p =
p->nextarc卡塔尔(قطر‎//令p指向极点的firstarc也正是指向终点节点后的首先个边结点,等到p指向NULL时循环截止
{
k = p->adjvex;//令k指向p节点的下标号;
if (–indegree[k] == 0卡塔尔(قطر‎//先将这几个节点的入度-1倘诺=0,那么就将它入栈
Push;
}
}
if (count < G.vexnum)
{
printf(“The directed graph has a loopn”);
return 0;
}
else
return 1;
}
Status TopologicalOrder(ALGraph G, SqStack &T)
{
SqStack S;
ArcNode *p;
int i, x, k, count = 0;

/*图的邻接表的边结点定义*/
typedef struct node
{
 int adjvex; 
    struct node *next; 
}edgenode;

FindInDegree;InitStack;for (i = 0; i < G.vexnum; i++)//将时间最早发生初始化 ve[i] = 0;for (i = 0; i < G.vexnum; i++)//将入度为0的顶点入栈;{ if (indegree[i] == 0) Push;}while (!StackEmpty{ Pop; Push;//将弹出来的顶点下标压入栈T count++; for (p = G.vertex[x].firstarc; p; p = p->nextarc)//注意p指向的是边节点 { k = p->adjvex; if (--indegree[k] == 0) { Push; } if (ve[x] + (p->weight) > ve[k])//取最早完成时间里的最大值 { ve[k] = ve[x] + (p->weight); } } if (count < G.vexnum) return 0; else return 1;}

/*图的邻接表表示的终端结点定义*/
typedef struct vnode
{
 vertextype vertex; 
    edgenode *firstedge; 
}vertexnode; 

}
Status CriticalPath(ALGraph G)
{
int i, k, x;
int ee, el;
ArcNode *p;
SqStack T;
InitStack;
TopologicalOrder;
for (i = 0; i < G.vexnum; i++)
vl[i] = ve[G.vexnum – 1];
while (!StackEmpty
{
Pop;
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
if (vl[x] > vl[k] – p->weight卡塔尔国//取最晚时间中最小值
vl[x] = vl[k] – p->weight;
}
}
for (i = 0; i < G.vexnum; i++);
{
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
ee = ve[i];
el = vl[k] – p->weight;
}
printf(“Criticalpath:<%d,%d>length:%dn”, i, k, p->weight);
}
return 1;
}
int main()
{
//ALGraph G;
//CreateDGAOV;
//TopologicalSort;
//printf;
ALGraph N;
CreateDGAOE;
CriticalPath;
return 0;
}

typedef vertexnode adjlist[maxvertexnum]; 

/*定义图的邻接表*/ 
typedef struct
{
 adjlist adjlist;
    int n; 
    int e; 
}algraph;

typedef enum
{
 FALSE,TRUE
}boolean;
boolean visited[maxvertexnum]; 

/*构造建设图g的邻接表表示*/
void createalgraph(algraph *g)
{
 int i,j,k;
    int flag;
    edgenode *s;
    printf(“ncreat:n”);
    printf(“digraph–0n”);
    printf(“undigraph–1n”);
    scanf(“%d”,&flag);
    printf(“input n,en”);
    scanf(“%d,%d”,&g->n,&g->e);
    printf(“input nodes:n”);
    for(i=0;i<g->n;i++)
    {
     scanf(“%d”,&(g->adjlist.vertex));
        g->adjlist
.firstedge=null;
    }
    for(k=0;k<g->e;k++)
    {
     printf(“input i,j(0~n-1):n”);
        scanf(“%d,%d”,&i,&j);
        s=(edgenode *)malloc(sizeof(edgenode));
        s->adjvex=j;
        s->next=g->adjlist.firstedge;
        g->adjlist
.firstedge=s;
        if (flag)
        {
         s=(edgenode *)malloc(sizeof(edgenode));
            s->adjvex=i;
            s->next=g->adjlist[j].firstedge;
            g->adjlist[j].firstedge=s;
        }
   }
}**

void dfs(algraph *g,int i)
{
 edgenode *p;
    printf(“nvisit vertex:%d”,g->adjlist.vertex);
    visited
=TRUE;
    p=g->adjlist.firstedge;
    while(p)
    {
     if (!visited[p->adjvex])
        dfs(g,p->adjvex);
        p=p->next;
    }
}**

/*对以邻接表表示的图g举行深度优先寻找*/
void dfstraverse(algraph *g)
{
 int i;
    for(i=0;i<g->n;i++)
    visited=FALSE;
    for(i=0;i<g->n;i++)
    if(!visited
)
    dfs(g,i);
    printf(“n”);
}**

void bfs(algraph *g,int k)
{
 int i,j;
    cirqueue *q;
    edgenode *p;
    q=(cirqueue *)malloc(sizeof(cirqueue));
    q->rear=q->front=q->count=0;
    printf(“nvisit vertex:%d”,g->adjlist[k].vertex);
    visited[k]=TRUE;
    q->data[q->r