1.
#include<stdio.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 100
typedef int VertexType;
//表结点
typedef struct ArcNode{
int adjVex;//邻接域
struct ArcNode *nextArc;
}ArcNode;
//头结点
typedef struct VNode{
VertexType data;
ArcNode *firstArc;
}VNode,AdjList[MAX_VERTEX_NUM];
//以邻接表存储的图
typedef struct ALGraph{
AdjList vertices;
int vexNum,arcNum;
}ALGraph;
//创建一个以邻接表形式存储的有向图
void createALGraph(ALGraph &G,VertexType vList[],int vListLength,VertexType arcList[][2],int arcListLength){
for(int i=0;i<vListLength;i++){//先将顶点信息存入邻接表
G.vertices[i].data=vList[i];
G.vertices[i].firstArc=NULL;
}
for(int i=0;i<arcListLength;i++){//将每一条边存入邻接表
VertexType v=arcList[i][0];
VertexType w=arcList[i][1];
ArcNode *pArcNode=(ArcNode *)malloc(sizeof(ArcNode));
pArcNode->adjVex=w;
pArcNode->nextArc=G.vertices[v].firstArc;//头插法
G.vertices[v].firstArc=pArcNode;//头插法
}
G.vexNum=vListLength;
G.arcNum=arcListLength;
}
int main(){
VertexType vList[4]={0,1,2,3};//顶点集
VertexType arcList[4][2]={{0,1},{0,2},{0,3},{1,2}};//边集
ALGraph G;
createALGraph(G,vList,4,arcList,4);
return 0;
}
2.
//有一个以邻接表存储的有向图G,求其各个结点的度
void getDegree(ALGraph G,int degree[]){
for(int i=0;i<G.vexNum;i++){//遍历邻接表的每一条链
VertexType v=G.vertices[i].data;
ArcNode *pArcNode=G.vertices[i].firstArc;//当前链中的第一个结点
while(pArcNode != NULL){//遍历当前链中的每一个结点
VertexType w=pArcNode->adjVex;
degree[v]+=1;//v出度加1
degree[w]+=1;//w入度加1
pArcNode=pArcNode->nextArc;//指针后移
}
}
}
3.
//DFS
int visited[MAX_VERTEX_NUM]={0};
void DFS(ALGraph G,VertexType v){
visited[v]=1;
printf("%d ",v);
ArcNode *pArcNode=G.vertices[v].firstArc;
while(pArcNode != NULL){
VertexType w=pArcNode->adjVex;
if(visited[w]==0){
DFS(G,w);
}
pArcNode=pArcNode->nextArc;
}
}
void DFSTraverse(ALGraph G){
for(int iVertex=0;iVertex<G.vexNum;iVertex++){
if(visited[iVertex]==0){
DFS(G,iVertex);
}
}
}
11.
//拓扑排序
int visited[MAX_VERTEX_NUM]={0};
VertexType vexList[MAX_VERTEX_NUM]={0};
int vexListLength=0;
void DFS(ALGraph G,VertexType v){
visited[v]=1;
ArcNode *pArcNode=G.vertices[v].firstArc;
while(pArcNode != NULL){
VertexType w=pArcNode->adjVex;
if(visited[w]==0){
DFS(G,w);
}
pArcNode=pArcNode->nextArc;
}
vexList[vexListLength]=v;
vexListLength++;
}
void printVexList(VertexType vexList[],int vexListLength){
for(int i=vexListLength-1;i>=0;i--){
printf("%d ",vexList[i]);
}
printf("\n");
}
void getTopoSort(ALGraph G){
for(int iVertex=0;iVertex<G.vexNum;iVertex++){
if(visited[iVertex]==0){
DFS(G,iVertex);
}
}
printVexList(vexList,vexListLength);
}