结构体定义
//定义
//邻接矩阵
typedef struct MGraph{
char vex[MAXSIZE];
int edge[MAXSIZE][MAXSIZE];
int vexnum,edgenum;
}MGraph;
//带权重的邻接矩阵
struct MGraphW{
//储存的顶点表
char vex[MAXSIZE];
//路径矩阵,只不过改成权重了
int weight[MAXSIZE][MAXSIZE];
//存储顶点与边的个数
int vexnum,arcnum;
};
//邻接表
typedef struct ArcNode{
int adjvex,weight;
struct ArcNode *next;
}ArcNode;
typedef struct VNode{
char value;
ArcNode *first;
}VNode,AdjList[MAXSIZE];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
习题
//邻接矩阵->邻接表
ALGraph MGToALG(MGraph g){
ALGraph ag;
ag.vexnum = g.vexnum;
ag.arcnum = g.edgenum;
ArcNode *p,*q;
for(int i=0;i<g.vexnum;i++){
ag.vertices[i].value = g.vex[i];
ag.vertices[i].first = NULL;
for(int j=0;j<g.vexnum;j++){
if(g.edge[i][j]!=0){
q = (ArcNode*)malloc(sizeof(ArcNode));
q->adjvex = j;
q->next = NULL;
if(ag.vertices[i].first == NULL){
ag.vertices[i].first = q;
p = q;
}else{
p->next = q;
p = q;
}
}
}
}
return ag;
}
//邻接表->邻接矩阵
MGraph ALGToMG(ALGraph a){
MGraph g;
g.edgenum = a.arcnum;
g.vexnum = a.vexnum;
ArcNode *p;
int v;
for(int i=0;i<g.vexnum;i++){
for(int j=0;j<g.vexnum;j++){
g.edge[i][j] = 0;
}
}
for(int i=0;i<a.vexnum;i++){
g.vex[i] = a.vertices[i].value;
p = a.vertices[i].first;
while(p){
v = p->adjvex;
g.edge[i][v] = 1;
p = p->next;
}
}
return g;
}
//2012统考真题，是否存在EL路径
int isExistEL(MGraph G){
int degree,i,j,count = 0;
for(i=0;i<G.vexnum;i++){
degree = 0;
for(j=0;j<G.vexnum;j++){
if(G.edge[i][j]!=0)degree++;
}
if(degree%2!=0)count++;
}
if(count==0 || count==2)return 1;
else return 0;
}
//(不熟) 广度优先搜索 - 邻接矩阵
void BFSM(MGraph G,int v,int visited[]){
int Queue[MAXSIZE],rear = -1,front = -1;
printf("%c",G.vex[v]);
Queue[++rear] = v;
visited[v] = 1;
while(rear!=front){
v = Queue[++front];
for(int i=0;i<G.vexnum;i++){
if(G.edge[v][i]!=0 && visited[i]==0){
printf("%c",G.vex[i]);
visited[i] = 1;
Queue[++rear] = i;
}
}
}
}
void BFSMGraph(MGraph G){
int visited[G.vexnum];
for(int i=0;i<G.vexnum;i++){
visited[i] = 0;
}
for(int i=0;i<G.vexnum;i++){
if(!visited[i])BFSM(G,i,visited);
}
}
//(不熟) 广度优先搜索 - 邻接表
void BFSALG(ALGraph G,int v,int visited[]){
int Queue[G.vexnum],rear = -1,front = -1,vex;
printf("%c",G.vertices[v].value);
ArcNode *p = G.vertices[v].first;
visited[v] = 1;
Queue[++rear] = v;
while(rear != front){
v = Queue[++front];
p = G.vertices[v].first;
while(p){
vex = p->adjvex;
if(!visited[vex]){
Queue[++rear] = vex;
printf("%c",G.vertices[vex].value);
visited[vex] = 1;
}
p = p->next;
}
}
}
void BFSALGraph(ALGraph G){
int visited[G.vexnum];
for(int i=0;i<G.vexnum;i++){
visited[i]=0;
}
for(int i=0;i<G.vexnum;i++){
if(!visited[i])BFSALG(G,i,visited);
}
}
//深度优先搜索 -- 邻接矩阵
void DFSMG(MGraph G,int v,int visited[]){
visited[v] = 1;
printf("%c",G.vex[v]);
for(int i=0;i<G.vexnum;i++){
if(G.edge[v][i]!=0 && visited[i]==0){
DFSMG(G,i,visited);
}
}
}
void DFSMGraph(MGraph G){
int visited[G.vexnum];
for(int i=0;i<G.vexnum;i++){
visited[i]=0;
}
for(int i=0;i<G.vexnum;i++){
if(!visited[i])DFSMG(G,i,visited);
}
}
//深度优先搜索 -- 邻接表
void DFSALG(ALGraph G,int v,int visited[]){
visited[v] = 1;
printf("%c",G.vertices[v].value);
ArcNode *p = G.vertices[v].first;
while(p){
v = p->adjvex;
if(!visited[v])DFSALG(G,v,visited);
p = p->next;
}
}
void DFSALGraph(ALGraph G){
int visited[G.vexnum];
for(int i=0;i<G.vexnum;i++){
visited[i]=0;
}
for(int i=0;i<G.vexnum;i++){
if(!visited[i])DFSALG(G,i,visited);
}
}
//判断无向图是否是一棵树
//思路：DFS遍历图，要想无向图是一棵树，则顶点数加一等于边数
//辅助DFS函数
void DFSTU(ALGraph G,int v,int &node,int &edge,int visited[]){
visited[v] = 1;
node++;
ArcNode *p = G.vertices[v].first;
while(p){
edge++;
int k = p->adjvex;
if(!visited[k])DFSTU(G,k,node,edge,visited);
p = p->next;
}
}
int isTree(ALGraph G){
int visited[G.vexnum];
for(int i=0;i<G.vexnum;i++){
visited[i]=0;
}
int node=0,edge=0;
DFSTU(G,0,node,edge,visited);
if(node == G.vexnum && G.vexnum*2-1 == edge)return true;
else return false;
}
//(不熟)深度优先的非递归算法
void DFSALGN(ALGraph G,int v,int visited[]){
printf("%c",G.vertices[v].value);
int Stack[MAXSIZE],top = -1,k;
ArcNode *p;
Stack[++top] = v;
while(top!=-1){
v = Stack[top];
p = G.vertices[k].first;
while(p){
k = p->adjvex;
if(!visited[k]){
visited[k] = 1;
printf("%c",G.vertices[k].value);
Stack[++top] = k;
break;
}
p = p->next;
}
if(!p)top--;
}
}
//广度判断图中是否存在i到j的路径
bool isExistPath(ALGraph G,int i,int j){
int visited[G.vexnum],k;
for(int t=0;t<G.vexnum;t++){
visited[t] = 0;
}
int Queue[MAXSIZE],rear = -1,front = -1;
Queue[++rear] = i;
visited[i] = 1;
while(rear!=front){
i = Queue[++front];
ArcNode *p = G.vertices[i].first;
while(p){
k = p->adjvex;
if(!visited[k]){
if(k == j)return true;
visited[k] = 1;
Queue[++rear] = k;
}
p = p->next;
}
}
return false;
}
//深度优先实现上述算法
void isExistPathByDFS(ALGraph G,int i,int j,bool &exist,int visited[]){
if(i == j)exist =true;
visited[i] = 1;
ArcNode *p = G.vertices[i].first;
while(p){
int k = p->adjvex;
if(!visited[k]){
isExistPathByDFS(G,k,j,exist,visited);
}
p = p->next;
}
}
bool isExistPathBD(ALGraph G,int i,int j){
int visited[G.vexnum];
for(int k=0;k<G.vexnum;k++){
visited[k] = 0;
}
bool is = false;
isExistPathByDFS(G,i,j,is,visited);
return is;
}
//输出从i到j的所有简单路径
void printAlliToJPath(ALGraph G,int i,int j,int &deep,int path[],int visited[]){
visited[i] = 1;
path[deep] = i;
deep++;
if(i == j){
for(int i=0;i<deep;i++){
printf("%c ",G.vertices[i].value);
}
}
ArcNode *p = G.vertices[i].first;
while(p){
int k = p->adjvex;
if(!visited[i])printAlliToJPath(G,k,j,deep,path,visited);
p = p->next;
}
visited[i] = 0;
}
//BFS (不熟)求解单源最短路径 （不带权）
void getMinPathByBFS(ALGraph G,int v,int dis[],int path[],int visited[]){
for(int i=0;i<G.vexnum;i++){
visited[i] = 0;
dis[i] = INF;
path[i] = -1;
}
dis[v] = 0;
int Queue[G.vexnum],rear = -1,front = -1,k;
Queue[++rear] = v;
while(rear!=front){
v = Queue[++front];
ArcNode *p = G.vertices[v].first;
while(p){
k = p->adjvex;
if(!visited[k]){
dis[k] = dis[v] + 1;
path[k] = v;
visited[k] = 1;
Queue[++rear] = k;
}
p = p->next;
}
}
}
//(不熟)迪杰斯特拉算法(求最短路径)
void Dijkstra(ALGraph G,int v,int dis[],int path[],int visited[]){
for(int i=0;i<G.vexnum;i++){
visited[i]=0;
path[i] = -1;
dis[i] = INF;
}
visited[v] = 1;
dis[v] = 0;
path[v] = 0;
ArcNode *p = G.vertices[v].first;
int k,min,minindex;
while(p){
k = p->adjvex;
dis[k] = p->weight;
path[k] = v;
p = p->next;
}
for(int i=0;i<G.vexnum-1;i++){
min = INF;
for(int j=0;j<G.vexnum;j++){
if(min>dis[j]){
min = dis[j];
minindex = j;
}
}
visited[minindex] = 1;
p = G.vertices[minindex].first;
while(p){
k = p->adjvex;
if(!visited[k] && dis[k] > p->weight + dis[minindex]){
dis[k] = p->weight + dis[minindex];
path[k] = minindex;
}
p = p->next;
}
}
}
//弗洛伊德算法
void Floyd(MGraph G,int a[][],int path[][]){
for(int i=0;i<G.vexnum;i++){
for(int j=0;j<G.vexnum;j++){
a[i][j] = G.edge[i][j];
path[i][j] = -1;
}
}
for(int k=0;k<G.vexnum;k++){
for(int i=0;i<G.vexnum;i++){
for(int j=0;j<G.vexnum;j++){
if(a[i][j]> a[i][k] + a[k][j]){
path[i][j] = k;
a[i][j] = a[i][k]+a[k][j];
}
}
}
}
}
//得到所有节点的入度
void getAllNodesIndegree(ALGraph G,int indegree[]){
for(int i=0;i<G.vexnum;i++){
ArcNode *p = G.vertices[i].first;
while(p){
int k = p->adjvex;
indegree[k]++;
p = p->next;
}
}
}
//(不熟)拓扑排序，判断有向连通图是否有环
bool isCricle(ALGraph G){
int stack[MAXSIZE],top=-1,indegree[MAXSIZE],toSequence[MAXSIZE],count=0,v;
for(int i=0;i<G.vexnum;i++){
indegree[i] = 0;
}
getAllNodesIndegree(G,indegree);
for(int i=0;i<G.vexnum;i++){
if(indegree[i]==0)stack[++top] = i;
}
while(top!=-1){
v = stack[top--];
toSequence[count++] = v;
ArcNode *p = G.vertices[v].first;
while(p){
int k = p->adjvex;
if((--indegree[k]==0)){
indegree[k]--;
stack[++top] = k;
}
p = p->next;
}
for(int i=0;i<G.vexnum;i++){
printf("%c",G.vertices[toSequence[i]].value);
}
}
return G.vexnum == count;
}
//逆拓扑排序
void reverseTopo(ALGraph G,int v,int i,int visited[],int sequence[]){
visited[v] = 1;
ArcNode *p = G.vertices[v].first;
while(p){
int k = p->adjvex;
if(!visited[k]){
i++;
reverseTopo(G,k,i,visited,sequence);
}
sequence[i] = k;
p = p->next;
}
}
//(不熟)i到j之间长度为length的路径
void printLengthPath(ALGraph G,int i,int j,int length,int d,int path[],int visited[]){
path[d] = i;
if(d == length && i==j){
for(int x=0;x<length;x++){
printf("%c ",G.vertices[x].value);
}
}
visited[i] = 1;
ArcNode *p = G.vertices[i].first;
while(p){
int k = p->adjvex;
if(!visited[k]){
d++;
printLengthPath(G,k,j,length,d,path,visited);
}
p = p->next;
}
visited [i] = 0;
}
//求解i到j之间长度最长的路径 边带权
void getLengthPath(ALGraph G,int i,int j,int length,int d,int path[],int visited[],int max,int maxpath[]){
path[d] = i;
if(length > max && i == j){
max = length;
for(int x=0;x<d;x++){
maxpath[x] = path[x];
}
}
visited[i] = 1;
ArcNode *p=G.vertices[i].first;
while(p){
int k = p->adjvex;
if(!visited[k]){
d++;
length = length + p->weight;
getLengthPath(G,k,j,length,d,path,visited,max,maxpath);
p = p->next;
}
}
visited[i] = 0;
}
//判断有向图内是否有根节点
//思路：深度优先搜索走了一遍，且节点个数等于深搜的节点数，那么整个图无额外的连同向量，必有根节点
void DFSR(ALGraph G,int v,int visited[],int &count){
visited[v] = 1;
ArcNode *p = G.vertices[v].first;
while(p){
int k = p->adjvex;
if(!visited[k]){
count++;
DFSR(G,k,visited,count);
}
p = p->next;
}
}
bool isRoot(ALGraph G){
int visited[G.vexnum];
for(int i=0;i<G.vexnum;i++){
visited[i] = 0;
}
int count = 0;
for(int i=0;i<G.vexnum;i++){
DFSR(G,i,visited,count);
if(count==G.vexnum)return true;
}
return false;
}
