关于图的操作

实验目的：
（1）掌握图的邻接矩阵和邻接表存储方式；
（2）掌握图的遍历算法；
（3）掌握图的实际应用——最短路径算法。

实验要求：
（1）采用邻接矩阵/邻接表建立图；
（2）采用深度优先/广度优先搜索方式遍历图；
（3）编程实现Dijkstra最短路径算法。

实验代码：

#include
#include
using namespace std;
#define MaxInt 100
#define MVNum 100
typedef struct
{
    char vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum,arcnum;
}AMGraph;

int LocateVex(AMGraph &G,char v)
{
    for(int i=0;i
        if(G.vexs[i]==v)
        {
            return i;
        }
    }
}
int CreateUDN(AMGraph &G)//用邻接矩阵创建无向网
{
    cout<<"输入顶点数及边数："<>G.vexnum>>G.arcnum;
    cout<<"输入顶点："<
        cin>>G.vexs[i];
    }
    for(int i=0;i
        for(int j=0;j
            G.arcs[i][j]=MaxInt;
        }
    }
    for(int k=0;k
        cout<<"输入一条边依附的顶点及权值："<>v1>>v2>>w;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        G.arcs[i][j]=w;
        G.arcs[j][i]=G.arcs[i][j];
    }
    cout<<"邻接矩阵创建无向网成功"<
    int adjvex;
    struct ArcNode *nextarc;
    //OtherInfo info;
}ArcNode;
typedef struct VNode
{
    char data;
    ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct
{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;


int LocateVex(ALGraph &G,char v)
{
    for(int i=0;i
        if(v==G.vertices[i].data) return i;
    }
}
int CreateUDG(ALGraph &G)
{
    cout<<"输入顶点数及边数："<>G.vexnum>>G.arcnum;
    cout<<"输入顶点："<
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }
    cout<<"输入每一条边依附的两个顶点："<
        char v1,v2;
        cin>>v1>>v2;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        ArcNode *p1=new ArcNode;
        p1->adjvex=j;
        p1->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p1;
        ArcNode *p2=new ArcNode;
        p2->adjvex=i;
        p2->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p2;
    }
    cout<<"邻接表创建无向图成功"<
    cout<
        if((G.arcs[v][w]!=0)&&(!visited[w])) DFS_AM(G,w,visited);
    }
}

void ShortestPath_DIJ(AMGraph &G,int v0)
{
    int n=G.vexnum;
    bool S[n];
    int D[n];
    int Path[n];
    for(int v=0;v
        S[v]=false;
        D[v]=G.arcs[v0][v];
        if(D[v]
        cout<
        cout<
        cout<
        int Min=MaxInt;
        int v;
        for(int w=0;w
            if(!S[w]&&D[w]
                v=w;
                Min=D[w];
            }
        }
        S[v]=true;
        for(int w=0;w
            if(!S[w]&&(D[v]+G.arcs[v][w]
                D[w]=D[v]+G.arcs[v][w];
                Path[w]=v;
            }
        }
    }
    for(int i=0;i
        cout<<"v0到v"<
	for(int i=0;i
		if(G.arcs[u][i]!=0)
		{
			return i;
		}
	}
	
}
int NextAdjVex(AMGraph &G,int u,int w)
{
		for(int i=w+1;i
		if(G.arcs[u][i]!=0)
		{
			return i;
		}
	}
}
int BFS(AMGraph &G,int v)
{
    cout<false};
    visited[v]=true;
    queue Q;
    Q.push(v);
    while(!Q.empty())
    {
    	int u=Q.front();
    	Q.pop();
        for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
        {
            if(!visited[w])
                {
                    cout<

int w;

printf("%c ", G.vertices[v].data);

visited[v] = 1;

ArcNode *p = new ArcNode;

p = G.vertices[v].firstarc;

while (p)

{

w = p->adjvex;

if (!visited[w]) DFS_AL(G, w,visited);

p = p->nextarc;

}

}

int main()
{
    ALGraph G;
    CreateUDG(G);
    cout<<"采用深度优先搜索方式遍历图：" <0};
	DFS_AL(G,0,visited);
   
    
    return 0;
}