紧急求助！！采用邻接表存储的prim算法
请人才帮忙编写采用邻接表存储的prim算法.请帮忙补写prim算法，先谢过
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 100
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
int info; //该弧相关信息的指针
}ArcNode;
typedef struct VNode
{
char data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX];
typedef struct{
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和弧数
}ALGraph;
int LocateVex(ALGraph G,char u)//查找顶点u的序号
{
int i;
for(i=0;i <G.vexnum;i++)
{
if(u==G.vertices[i].data)
return i;
}
if(i==G.vexnum)
{
cout < < "error u! " < <endl;
exit(1);
}
return 0;
}
void CreateUDG(ALGraph &G) //建立无向图的邻接表
{
int i,j,k,w;
char v1,v2;
ArcNode *p;
cout < < "输入无向图的顶点数和边数： ";
cin> > G.vexnum> > G.arcnum;
cout < < "输入顶点： ";
for(i=0;i <G.vexnum;i++)
{
cin> > G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
cout < < "输入一条边依附的顶点和权： " < <endl;
for(k=0;k <G.arcnum;k++)
{
cin> > v1> > v2> > w;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode *)malloc(sizeof(ArcNode));
p-> adjvex=j;
p-> info=w;
p-> nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
p=(ArcNode *)malloc(sizeof(ArcNode));
p-> adjvex=i;
p-> info=w;
p-> nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p;
}
}
void printG(ALGraph G) //输出该图的各顶点和邻接表
{
int i;
ArcNode *p;
cout < < "图的各顶点为： ";
for(i=0;i <G.vexnum;i++)
cout < <G.vertices[i].data;
cout < <endl;
cout < < "图的邻接表为： " < <endl;
for(i=0;i <G.vexnum;i++)
{
cout < <i < < " " < <G.vertices[i].data;
p=G.vertices[i].firstarc;
while(p)
{
cout < < "-> " < <p-> adjvex;
p=p-> nextarc;
}
cout < <endl;
}
}
void Vdu(ALGraph G) //计算各顶点的度
{
int i,j;
int du[100];
ArcNode *p;
for(i=0;i <G.vexnum;i++)
du[i]=0;
for(i=0;i <G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
du[i]++;
p=p-> nextarc;
}
}
cout < < "图中各顶点的度为： " < <endl;
for(j=0;j <G.vexnum;j++)
cout < <G.vertices[j].data < < "的度是： " < <du[j] < <endl;
}
void main()
{
ALGraph G1;
CreateUDG(G1);
printG(G1);
Vdu(G1);
getch();
}
[解决办法]
没听过这个算法，帮顶。
[解决办法]
package graph;
public class Graph {
private int length;
private GraphList[] list;
private int[][] weight;
private int[][] lightSide;
private int[] replaceValue;
private int endNode;
private int count;
public Graph(int length) {
this.length = length;
list = new GraphList[length];
weight = new int[length][length];
lightSide = new int[length][length];
replaceValue = new int[length];
for (int i = 0; i < length; i++) {
replaceValue[i] = i;
for (int j = 0; j < length; j++) {
weight[i][j] = 9999;
}
}
}
public void dfs(int v,int u) {
int[] ajd = new int[length];
int ajdlength = list[v].getAjd(ajd);
list[v].visitable = true;
System.out.print(v + " ");
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
dfs(w,u);
}
}
}
//// 深度优先遍历
//public void dfsTravel() {
//for (int i = 0; i < length; i++) {
//list[i].visitable = false;
//}
//for (int i = 0; i < length; i++) {
//if (!list[i].visitable) {
//dfs(i);
//}
//}
//}
// 广度优先遍历
public void bfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
bfs();
}
private void bfs() {
Queue queue = new Queue();
for (int index = 0; index < length; index++) {
if (!list[index].visitable) {
queue.addQueue(index);
list[index].visitable = true;
System.out.print(index + " ");
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
System.out.print(w + " ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}
}
}
/**
* Dijkstra
*
* @param v
* @param u
* @return int
*/
public int shortPath(int v, int u) {
int[] shortPath = new int[length];
boolean[] weightFound = new boolean[length];
int[] previous = new int[length];
for (int i = 0; i < length; i++) {
// 趋近无穷
shortPath[i] = 9999;
previous[i] = 9999;
weightFound[i] = false;
}
shortPath[v] = 0;
weightFound[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!weightFound[w]) {
if (shortPath[w] > shortPath[temp] + weight[temp][w]) {
shortPath[w] = shortPath[temp] + weight[temp][w];
previous[w] = temp;
}
}
}
int minWeightNode = 0;
for (int i = 0; i < length; i++) {
if (!weightFound[i]) {
minWeightNode = i;
for (int j = 0; j < length; j++) {
if (!weightFound[j]) {
if (shortPath[j] < shortPath[minWeightNode]) {
minWeightNode = j;
}
}
}
break;
}
}
if (!weightFound[minWeightNode]) {
weightFound[minWeightNode] = true;
queue.addQueue(minWeightNode);
}
}
//记录经过的边
Stack stack = new Stack();
int s = u;
while (previous[s] != 9999) {
stack.push(s);
s = previous[s];
}
stack.push(v);
while (stack.stackTop.link != null) {
int from = stack.top();
stack.pop();
int to = stack.top();
System.out.print(from + "==>" + to + ", ");
}
return shortPath[u];
}
/**
* 佛洛伊德最短路径
*
* @param v
* @return int[]
*/
public int[] floydShortPath(int v) {
// 初始化矩阵
int[][] spath = new int[length][length];
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (i == j) {
spath[i][j] = 0;
} else {
spath[i][j] = weight[i][j];
}
}
}
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
for (int k = 0; k < length; k++) {
if (spath[i][j] + spath[k][i] < spath[j][k]) {
spath[j][k] = spath[i][j] + spath[k][i];
}
}
}
}
int[] resultArray = new int[length];
for (int i = 0; i < length; i++) {
resultArray[i] = spath[v][i];
}
return resultArray;
}
// 长度
public void length() {
System.out.println(length);
}
public boolean isEmpty() {
return length == 0;
}
// 添加节点
public void addGraph(int info) {
for (int i = 0; i < length; i++) {
if (list[i] == null) {
GraphList g = new GraphList();
g.addNode(info);
list[i] = g;
break;
}
}
}
// 添加边
public void addSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
weight[vfrom][vto] = value;
}
// 打印图
public void print() {
for (int i = 0; i < length; i++) {
GraphNode current = list[i].first;
while (current != null) {
System.out.print(current.info + " ");
current = current.link;
}
System.out.println();
}
}
// 普里姆最小生成树
public void primMST(int v) {
boolean[] visited = new boolean[length];
for (int i = 0; i < length; i++) {
visited[i] = false;
for (int j = 0; j < length; j++) {
lightSide[i][j] = 9999;
}
}
visited[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
lightSide[temp][w] = weight[temp][w];
}
// 找到最小边
int minSide = 0;
int vfrom = 0;
int vto = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (visited[i] && visited[j]) {
continue;
}
minSide = lightSide[i][j];
vfrom = i;
vto = j;
for (int k = 0; k < length; k++) {
for (int l = 0; l < length; l++) {
if (visited[k] && visited[l]) {
continue;
}
if (lightSide[k][l] < minSide) {
minSide = lightSide[k][l];
vfrom = k;
vto = l;
}
}
}
break;
}
}
//将最小边的节点vto设为true，并输出vto
if (!visited[vto]) {
visited[vto] = true;
System.out.print(vfrom + "==>" + vto + ", ");
queue.addQueue(vto);
}
}
}
// 克鲁斯卡尔最小生成树
public void kruskalMST() {
int m = 0;
while (m < length - 1) {
// 找到最小边
int minSide = 0;
int vfrom = 0;
int vto = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (replaceValue[i] == replaceValue[j]) {
continue;
}
minSide = weight[i][j];
vfrom = i;
vto = j;
for (int k = 0; k < length; k++) {
for (int l = 0; l < length; l++) {
if (replaceValue[k] == replaceValue[l]) {
continue;
}
if (weight[k][l] < minSide) {
minSide = weight[k][l];
vfrom = k;
vto = l;
}
}
}
break;
}
}
if (replaceValue[vfrom] != replaceValue[vto]) {
System.out.print(vfrom + "==>" + vto + ", ");
for (int i = 0; i < length; i++) {
if (replaceValue[i] == replaceValue[vfrom]) {
replaceValue[i] = replaceValue[vto];
}
}
m++;
}
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
System.out.println("create graph start");
for (int i = 0; i < 5; i++) {
graph.addGraph(i);
}
//graph.addSide(0, 1, 16);
graph.addSide(0, 3, 2);
graph.addSide(0, 4, 3);
graph.addSide(3, 4, 7);
graph.addSide(3, 1, 12);
//graph.addSide(4, 1, 10);
graph.addSide(4, 3, 5);
graph.addSide(4, 2, 4);
graph.addSide(2, 1, 3);
//graph.addSide(1, 2, 5);
graph.print();
System.out.println("create graph end");
graph.dfs(0, 2);
}
}
java写的
